2012-05-02 - TopCoderの学習のお時間

これまで20回以上MarathonMatchに参加して得てきた、MarathonMatchに取り組むにあたってのノウハウをまとめてみます。

これを全部やる必要があるわけじゃないので（一番重要なのは期間いっぱい楽しみつつ継続して取り組むこと）、部分的にでも参考にしてもらえたら。

ローカルで十分なのでgitのローカルリポジトリ使うのが楽なのでは。MercurialとかBazaarとかがどうなのかはよく知りません。

自分の場合は、デスクトップとノートの両方で扱いたいという事情があったので、プライベートリポジトリを無料で作れるbitbucketにリポジトリを作ってそこで同期させました。

注：自分がMarathonに参加しているあいだは見えなくなります

触るのは自分1人だけだし、提出すればTopCoderのサーバーにソースは保管されるものではありますが、やっぱり安心感が違う。

あと、しっかりコミットコメントを書いておくと、どの提出の時に何の変更を入れたかがあとから確認できるので良いです。

試したことやTODO、思いついたアイディアなどはテキストに書き残しておきます。

ちょっと考えたけど忘れてしまって、しっかり検討・実装しないまま終わるアイディアというのが意外とよく出てくるので。

参加記を書くときにも地味に役立ちます。

Marathonが開始して、問題を読んで次にすることは、公式に提供されるビジュアライザのソースコードを読むことです。

テストケース生成やスコア計算のコードから、方針を考えるヒントが得られることもあります。

問題文には記載されていないテストケース生成の詳細が、戦略の重要な一部となる例もありました。

ビジュアライザのソースコードを読んだ後にやることが、次のようなカスタマイズです。

標準入出力経由ではなく、直接自分の作るクラスを呼び出すようにする
- 自分がJavaを使っているのは、このように直接呼び出す形にしてデバッグやログ取りをやりやすくできるというのが大きい
テスト結果は、スコアだけではなくそれ以外の色々な情報（経過時間とか、問題サイズとか）を保持するクラスを返すようにする
- テスト結果を分析するのに必要
- 例：https://bitbucket.org/tomerun/marathon/src/f0364c37432d/TCO12R1/Visualizer.java#cl-608
- 出力はこんな感じになります https://bitbucket.org/tomerun/marathon/src/f0364c37432d/TCO12R1/res1.txt
起動オプションを追加し、seedの範囲を指定して一度に多くのテストケースを走らせられるようにする
- 範囲を指定した場合はマルチスレッドで実行されるようにする
- 例：https://bitbucket.org/tomerun/marathon/src/f0364c37432d/TCO12R1/Visualizer.java#cl-535
- "-begin"と"-end"というオプションを追加し、TestThreadというクラスでテストを分割して実行している
- この場合、staticフィールドがスレッド間で影響して変な結果になるということのないよう気をつけないといけない

Java以外の言語の人は、標準入出力でやるか、ちょっと手間をとってビジュアライザを移植するかしてください。

場合によりますが、独自にUIを工夫することで、方針を考えやすくなったり、結果を分析する効率が上がったりします。

独自ビジュアライザがよく作られている例

ただ、これだけに時間を掛けまくっても仕方ないので、バランスを考えて。

サーバーに提出するExampleTestでは、個数が少ないので偏りが出てしまい、結果が改善しているかどうかの確認にはあまり使えません。

代わりにローカルでできるだけたくさんテストしましょう。

ExampleTestは、主に高速化が期待通りできているかの確認に使っています。

ローカルとサーバーとで動作環境が違うので、ローカルで速くしたと思ってもサーバーではそうなっていなかったり、その逆があったりします。

あとは、ローカルとサーバーの速度の違いを調べるのにも。制限時間がサーバー上で10秒なのがローカルは4秒相当だったりするので。

テストケースは、ビジュアライザに毎回生成させると時間がかかることがあるので、最初に全部ファイルに落として、そこから読み込むようにしています、

また、問題サイズが小さいところだけとか、大きいところだけとかでテストしたいことがあるので、テストケースのパラメタを意図的に操作します。

ビジュアライザのコードを改変して、seed1001-2000の範囲などで、問題サイズがランダムではなくseedの番号に比例して作られるようにします。

こうしておくと、Nが小さいところだけテストしたい場合はseed1001からseed1200までをやる、というふうにできます。

テストの実行は次のようなサイクルでやっています。

「これはいけるかも」という変更を入れる
まず、問題サイズを指定しない100ケースのテストを走らせる（seed 1-100）
前回サブミット時の結果と比較する
改善が見られなければ最初に戻る
明らかな改善があれば、サイズ別に整理したテストを1000ケース走らせて結果を確認する（seed 1001-2000）
- 本当に1000個も必要なのか、というのは微妙だけど、サイズが小さいやつに限定して調べるといった場合にも十分なテストケースの数を確保するため、これくらいやってます
変なところがなかったらFull Submit
「Nが大きいところでだけ弱くなってる」とか「一部極端に悪くなったケースがある」のような気になるところがあったら、調整しなおす