Marathon Matchに参加

Marathon Matchに参加

ルール

限られた期間内で(1週間か2週間)プログラムを改良していき、どれだけ高いスコアを出せるかを競います。

次のような、1つの決まった正解が存在しなかったり、厳密に解こうとすると現実的な時間では不可能だったりといった課題が出されます。

  • 暗号解読
  • スケジューリング最適化
  • パズルゲームのスコアアタック

SRMと比べて、次のような特徴があります。

  • 使うアルゴリズムの違い。厳密解を出す必要がない(出せない)ので、ヒューリスティクスが頻出
  • 自分の都合の良いときに好きなだけの時間参加できる
  • 何度も投稿できるので「ほんの1ミスで0点」ということがなく、頑張っただけのスコアが付く

言語

JavaC++C#.NET、VB.NETPythonが使用できます。

ただし、一部の特別なコンテストでは使用できる言語が制限される場合もあります。

マラソンマッチにRegister する

コンテストが開催されているときは、Active Contestのページにコンテストが出現します。

registerと書かれたリンクから登録できます。

SRMのように事前登録制ではなく、開催期間中ならいつでも登録可能です。

コードを送信する

SRMとは違って、ブラウザからコードを送信します。

Active Contestのページのsubmitと書かれたリンクから送信画面に行けます。

Test Example

5~10個のExampleケースのテストを行います。個々のスコアと標準出力、標準エラー出力を見ることができます。一回Testしたら15分間、Testすることはできません。

Submit

Submitすると100個程度のテストケースが実行され(provisional test)、standingsに反映されます。ここで得られるスコアはSystem Test前の一時的なスコアです。

一回 Submit したらその後 2時間 Submit することはできません。

参加人数が多いときは、サーバーが混んでテストに時間がかかることがあります(ひどい場合は数時間)。テスト待ちになっている間は再提出ができないので注意しましょう。テスト待ちのキューはトップページ左のメニュー「Marathon Matches - Queue Status」から見れます。

戦略

自明解

とりあえず、「何も考えずランダムに出力してみた」みたいな単純なプログラムでもいいので提出してみましょう。だいたい順位表で真ん中ちょっと下あたりの集団に入って、他の参加者も同じようなことをやってるのが分かると思います。

やけに低いスコアしか出ていない場合は、バグがあってランタイムエラーになっていたり時間制限をオーバーしていたりする可能性が考えられるので修正しましょう。

アルゴリズムの改良

人間の思考をシミュレートさせてみたり、パラメタをいろいろ変えて試して一番いい結果になるやつを採用してみたり、時間制限の間じゅう逐次的に改善していくようなアルゴリズムにしてみたり、いろいろやってみましょう。「メタヒューリスティクス」など調べると、使える手法が見つかるかもしれません。

もちろん「検索で見つかった○○法を使ってみた」というだけでは、皆さん考えることは同じなので集団から抜け出すには至りません。上位を狙うためには、さらに問題ごとの特徴に応じた工夫が必要です。頑張って頭をひねって考えてください。

System Test

Coding Phaseが終わるとSystem Testが始まります。最後のSubmitしたコードが評価の対象になります。provisional test とは別の、より詳細なテストケースで評価されます。このテストケースでのスコアを元に最終順位が決定されます。テストの終了まではたいてい数日かかります。

テストケースによっては順位が大幅に入れ替わることも…

Visualizer , LocalTester

コードをデバッグする上でとても便利なツールです。Javaで実装されており、ローカル環境でテストができます。

Visualizerのソースコードには問題のロジックが全て記述してあるため、このコードを読むことがルール理解の助けになったりアルゴリズムを考えるヒントになったりすることもあります。

Rating

Algorithm 部門と同じで、最終順位が高ければ上がり、低ければ下がります。一回でもSubmitすればRatingの対象になります。TestだけしてSubmitしてない場合もRatingが付くので注意が必要です。

また、AMD Multicore Threadfest Competition などの一部のコンテストでは、Ratingが付きません。

Forum

問題文で仕様の詳細が全て網羅されているわけではないので、曖昧な箇所はForumで確認する必要があります。問題内容に修正が加わる場合があるのでForumはチェックしておくことをおすすめします。ネタバレな書き込みをすると失格になります。

Coding Phaseが終わった後は、とったアプローチの披露し合いで盛り上がります。