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

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

問題文

ここから先は、今年のTopCoder Open 2014 Round 2で出題されたRectangle and Holesという問題を使って説明します。
多くの問題では、問題文のページ公式テスターのページと、2つのページがあります。どちらも読む必要があります。公式テスターのページへのリンクは、以下のように問題文のページにまぎれてあるので、絶対に見逃さないようにしましょう。
f:id:shindannin:20141004191602p:plain

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

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

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

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

f:id:shindannin:20141004175723p:plain

公式テスターのページは、[A][B]を取り扱っています。以下のようなページになっています。

f:id:shindannin:20141004195811p:plain

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

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

[B] main

  • [A]と標準入出力で、データのやりとりをします。
  • [B]と[C]はJava,C++,C#,VB,Pythonのどれか好きなものを使えますが、同じ言語を使ってください。
  • たいてい公式テスターのページに、サンプルコード(疑似コード)が書かれているので、それを自分の使用言語に書き換えなければなりません。今回の問題では、
  N = parseInt(readLine())

    for (i=0; i < N; i++)
        A[i] = parseInt(readLine())

    for (i=0; i < N; i++)
        B[i] = parseInt(readLine())

    ret = place(A, B)

    for (i=0; i < 3*N; i++)
        printLine(ret[i])

    flush(stdout)


と書かれています。これをC++に翻訳する場合、

#include <cstdio>
#include <cstdlib>
#include <vector>

using namespace std;

int main(int argc, char const* argv[])
{
	int N;
	cin >> N;

	vector <int> A(N),B(N);

	for (int i=0; i < N; i++)
	{
		cin >> A[i];
	}

	for (int i=0; i < N; i++)
	{
		cin >> B[i];
	}

	RectanglesAndHoles* obj = new RectanglesAndHoles;
	vector <int> ret = obj->place(A, B); // [C]のコードを呼ぶ部分
	delete obj;

	for (int i=0; i < 3*N; i++)
	{
		cout << ret[i] << endl; // 疑似コードはprintLineなので、改行も出力する。
	}
	cout.flush(); // flushも忘れない!

	return 0;
}

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

[C] クラス

  • 自分の解答コードを書きます。
  • ここはSRMと同じように書けばよいです。例えば今回の問題でC++で書くと以下のようになります。
#include <cstdio>
#include <cstdlib>
#include <vector>

using namespace std;

class RectanglesAndHoles
{
public: // mainから呼ばれる関数はpublicにします。
  vector <int> place(vector <int> a, vector <int> b)
  {
    const int N = a.size();
    vector <int> ret(3*N);
    
    // 自分の解答を書く
   
    return ret;
  }
};
  • よくあるハマる例として、[C]で標準入出力を使ってはいけません。[B]が動かなくなります。つい、デバッグの際にprintfとか書きたくなりますがダメです。何かログを表示させたいなら、標準エラー出力か、ファイル出力を使いましょう。
  • また、次に述べる"Submit"で提出するときは、すべてのログ出力コードは消した方がよいです。プログラムの実行時間が遅くなるだけなので。

提出

Submitボタンを押すと、以下の画面に移動します。

f:id:shindannin:20141004230653p: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) は工事中で、結局古い方へリンクがつながってたり、新しい方から提出できないなどの問題も起きているので、古い方の画面を使って説明したいと思います。