TopCoderマラソンマッチのはじめかた

TopCoderマラソンマッチは、1-2週間ぐらいの長期間で、正解を出すのではなく、より良い性能のプログラムを書き、高スコアを出すことを競うコンテストです。短時間マッチのSRM(シングルラウンドマッチ)とは違った魅力があります。

ただ、SRMと比べると、参加方法がわかりにくいです。公式の解説はあるのですが、マラソンマッチをやったことがない方向けに、おおまかな参加方法を書きました。

まずTopCoder自体に参加したことのない方は、TopCoderへの登録が必要です。http://www.topcoder.com/の右上の"sign up"から登録を。うまくいかなければTwitterの@nico_shindanninまでご連絡ください。

また、この記事では、マラソンマッチの攻略法については述べません。特別なアルゴリズムの知識はなくても参加できます。ただ、TCO World Finalsに進出した方々による、とても良い記事がありますので、知りたい方はこれらを参考にしてください。
2012-05-02 - TopCoderの学習のお時間 - TopCoder部 by tomerunさん
マラソンマッチの取り組み方 – システム工房コルン by colunさん

マラソンマッチ トップページ

こちらの古い方(http://community.topcoder.com/longcontest/)のトップページを使って説明します。
*1f:id:shindannin:20141004231115p:plain

右側には、現在開催されているコンテストが表示されます。

  • discuss : フォーラムです。問題の変更・公式テスターのバグ修正など、とても重要な連絡がされることがあるので、マメにチェックしてください。
  • standings : 現在までの仮順位が表示されます。
  • Problem : 問題文です。
  • Register/Submit : 自分の解答コードを提出します。
  • Start Time, End Time : 時間が表示されます。日本標準時ではなく、東部標準時で表示されるので、注意してください。

左側にも、いくつか機能があります。現在無くなっているので、リンクを追加しました。

  • Match Archive : 過去のマラソンマッチの結果があります。他の人の提出コードも見れます。
  • Practice : 練習ページです。過去のマラソンマッチの問題で練習できます。Practice内でも、standingsで順位をみたり、submitで提出できます。自分の好きなときにできて締切もないので、活用しましょう。
  • Queue Status : 現在、結果を待っている人がいるかが分かります。

コンテストの流れ

開催中のコンテストに参加する場合の流れです。Practiceで練習するときには関係ありません。

ルール

  • 個人戦です。他の人と相談してはいけません
  • コードは自分で書く必要があります。ただし、問題によっては、特殊ルールで、外部ライブラリ使用可能だったり、他人のコードが使用可能ということもあるので、問題を良く読みましょう。
  • コンテスト期間中は、ネタバレ禁止です。コードをさらすのはもちろん、観察・考察をさらす(「こうやると○○点取れそうとか」「このアルゴリズムを試してみよう」)のも禁止です。
  • 残念ながら、賞金がもらえるマッチは、年齢制限(18歳以上)があるときが多いです。

スケジュール

スケジュールは以下のようなかんじです。

開始 → コード提出期間(3日~1ヶ月)→ コード提出終了・採点(1日~5日)→ 採点終了・順位確定

  • 突然始まるマッチもかなり多いです。TopCoderからのお知らせメールなどはマメにチェックしてください。
  • マラソンマッチの期間は1週間が一番多いですが、3日~1ヶ月ぐらいまでと幅広いです。
  • コード提出期間内には、standingsのリンクで、仮順位が分かります。スコアを上げて、上の順位を目指しましょう。
  • コード提出期間本採点終了後に、順位が確定します。結果に応じてレーティングが上下したり、上位に入れば賞金がもらえたりします。

問題文

多くの問題では、問題文のページ公式テスターのページと、2つのページがあります。どちらも読む必要があります。公式テスターのページへのリンクは、以下のように問題文のページにまぎれてあるので、絶対に見逃さないようにしましょう。
f:id:shindannin:20180505103020p:plain

SRMと違って、英語を読む時間はじっくりあるので、ちゃんと読みましょう。特にメモリ制約・制限時間は毎回異なりますし、間違うと0点になるので、必ずチェックしましょう。あと、どうしても問題の意味が分からないなら、以下で述べる公式テスターを先に実行してみるのも良いかもしれません。

スコアの算出方法も書いてあります。他の参加者との相対スコアか、絶対スコアかなど、細かいことまで書いてあります。スコアで順位が決まるので、とても大事です。必ずチェックしてください。

コーディングとオフライン実行環境

問題の解答のコーディングだけではなく、問題の解答をオフライン実行する環境が必要になってきます。一番よくある形は以下のとおりですが、公式テスター/ビジュアライザが無い場合もあります。その場合は問題文ページを良く読んでください。


公式テスターのページは、[A][B][C]を取り扱っています。以下のようなページになっています。
f:id:shindannin:20180505100444p:plain
また、[B]と[C]の各言語ごとの例をダウンロードとすると、コードは以下のようになっています。
f:id:shindannin:20180505100440p:plain

[A] 公式テスター(ビジュアライザ)

  • 公式テスターを使うと、自分のパソコンで、オフラインで自分の解答の得点を確認したり、ビジュアルつきで実行結果が見れます
  • 公式テスターはほぼ常にJavaです。Java runtimeかSDKを予めダウンロードしておいてください。
  • まずは公式テスターのページ上部 Executable JAR of the visualizer からダウンロードしてきましょう。
  • 実行は、コマンドラインから行います。公式テスターのページの下の方に説明があります。
  • 実行する場合は、[B][C]のコードを書いてコンパイルをして、実行ファイルを作る必要があります。その実行ファイルのパスを、コマンドラインの引数として渡します("..\..\Release\marathon_main.exe"の部分)
  java -jar Tester.jar -exec "..\..\Release\marathon_main.exe"
  • 公式テスターのソースコードもダウンロードできます。もし改良したい場合は、これを書き換え、javacでコンパイルしましょう。

[B] main

  • [A]と標準入出力で、データのやりとりをします。
  • [B]と[C]はJava,C++,C#,VB,Pythonのどれか好きなものを使えますが、同じ言語を使ってください。
  • 上記の各言語ごとの例を丸ごと使えば、問題ないでしょう。書き換えることはないと思います。

難しくはないのですが、1つでも入出力を間違えると、全く動作しないので、公式テスターのページをよく読んで、正確に書いてください。Javaから実行されるコードになるので、間違えたときエラーメッセージもJavaで出るので、どこで間違えたのかデバッグがしづらく、ハマりやすいです。

[C] クラス

  • 上記の各言語ごとの例から、はじめましょう。
  • Topcoder SRMと同じように、ここに自分の解答コードを書きます。
  • よくあるハマる例として、[C]で標準入出力を使ってはいけません。[B]が動かなくなります。つい、デバッグの際にprintfとか書きたくなりますがダメです。何かログを表示させたいなら、標準エラー出力か、ファイル出力を使いましょう。
  • また、次に述べる"Submit"で提出するときは、すべてのログ出力コードは消した方がよいです。プログラムの実行時間が遅くなるだけなので。

提出

Submitボタンを押すと、以下の画面に移動します。
f:id:shindannin:20180505102645p:plain

まず、画面右上で、言語を選択しましょう。そして、[C]のクラスのみを貼り付けて提出します。[B]は入れてはいけません。(なお、TopCoderでは、提出時に、複数ファイルのコードを提出するということはできません。よって1つのテキストにまとめて提出する必要があります。最大の難点です…。)

提出には"Test Example"と"Submit"の2種類あります。

  • Test Example
    • 実行するケース数は少ないです。通常のマラソンマッチだと10ケース程度です。
    • 1ケースごとの得点・実行時間・ログ出力が見れます。(Standingsページで、自分のExample提出回数のところをクリックします)
    • Standingsのスコアには反映されません。
    • 1度"Test Example"で提出したら、次の"Test Example"での提出までは15分待たないといけません。
  • Submit
    • 実行するケース数はやや多めです。通常のマラソンマッチだと100ケース程度です。
    • 100ケースの平均得点が見れます。
    • Standingsのスコアに反映されます。仮順位も変動します。
    • 1度"Submit"で提出したら、次の"Submit"での提出までは2時間待たないといけません。

通常は、まず"Test Example"で提出してみて、オフラインの結果と同じになるかをチェックします。もし良さげであれば"Submit"で同じコードを提出、何かおかしければ修正して"Test Example"でもう1度提出、というふうにすると思います。
提出が受理され、実行が終わると、TopCoderからメールが届きます。1度提出すると、15分間or2時間提出できません。最終的な順位は、一番最後に"Submit"で提出したコード決まります。例えば、残り時間2時間以内で、誤って0点のコードを提出したら、もう再提出はできませんので、0点確定です。締切ギリギリの提出は避けることをお勧めします。

マラソンマッチが終了したら

  • メインメニュー左側のMatch Archiveから、最終順位を見ることができます。また、他の参加者のコードは、右のほうにあるSubmissionの数字をクリックすると、過去の提出も含め、全て見ることができます。復習にぜひ活用してください。
  • discussのリンクから行けるフォーラムに行きましょう。
    • "Post your approach"というスレッドが立っていることがあります。ここで、他の人の解法を知ることができます。非常に勉強になるので、ぜひ見に行ってください。また、自分の解法を書くのも良いと思います。
    • 賞金つきマッチでは、たまに「追加マッチ」の情報が載っていることがあります。チェックしましょう。
  • 賞金つきマッチで入賞したら、賞金を受け取る手続きをして、もらいましょう。しないと、消えるのでご注意ください。


以上です。さぁ、みんなで楽しいマラソンマッチライフを!

*1:もう1つの新しいトップページ(http://www.topcoder.com/challenges/data/active/?pageIndex=1) は工事中で、結局古い方へリンクがつながってたり、新しい方から提出できないなどの問題も起きているので、古い方の画面を使って説明したいと思います。