Hatena::Grouptopcoder

TopCoderの学習のお時間 RSSフィード

戦績(topcoder.com) / 戦績(competitiveprogramming.info) / 過去記事 / 日記

 | 

2012-05-02

[][]Marathon Matchでいつもやってること 00:34 はてなブックマーク - Marathon Matchでいつもやってること - TopCoderの学習のお時間


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

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


開発環境


ソース管理

もちろんソースコードはバージョン管理システムで変更を管理します。

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

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

https://bitbucket.org/tomerun/marathon/src

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


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

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


作業管理

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

例:https://bitbucket.org/tomerun/marathon/src/f0364c37432d/TCO12R1/memo.txt

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

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


Visualizer、Tester


ソースを読む

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

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

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


テストしやすくする

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

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

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


リッチにビジュアライズする

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


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


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


テスト


Example Testの使いどころ

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

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


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

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

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


ローカルテスト

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


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

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

例:https://bitbucket.org/tomerun/marathon/src/f0364c37432d/TCO12R1/Visualizer.java#cl-162

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


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

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

集計スクリプト

ローカルテストのログを2つ読み込んで比較するようなスクリプトを作っています。

https://bitbucket.org/tomerun/marathon/src/f0364c37432d/TCO12R1/compare.rb

  • テストケースごとのスコア差分を表示
  • 全体でのスコア差分の平均を表示
  • 勝敗数をカウント
  • 集計対象にするseedの範囲を指定できる

このあたりは表計算ソフトを使うのも良さそう。自分でやったことは無いですけど。



時間計測


ボトルネック解析

大体の問題で高速化は課題になるので、ボトルネックになりそうな場所に計測コードを仕込んで、どこが遅いのかを分析します。

前回、次のようなTimerクラスを作ってみたらけっこう扱いやすかったです。今後も使おう

https://bitbucket.org/tomerun/marathon/src/f0364c37432d/TCO12R1/BlackAndWhiteGame.java#cl-1133


もちろん適当なプロファイラを持ってきて使っても良いですが、サーバーとローカルとで環境が違うのであまり厳密にやっても仕方ないかも



時間計測は重い

TopCoderのサーバー上で、C++のclock()やgettimeofday()がとても遅いのは有名な話ですが、JavaのSystem.currentTimeMillis()もけっこう遅いです。

呼び出し回数が1万を超えると呼び出しの削減を考えたくなるくらい。


Full Submitのときは、必ず不要な時間計測は切るようにしましょう。

C++だったらマクロ定義を使って簡単に自動化できそうだけど、Javaだとどうやるのがベストなんだろう?

今はサブミットするたびに手で定数を書き換えています。

https://bitbucket.org/tomerun/marathon/src/f0364c37432d/TCO12R1/BlackAndWhiteGame.java#cl-10

以前は truefalse とbooleanリテラルを書いていたけど、 0==1 としたら書き換えるのが1文字で済むことに最近気づいた


アルゴリズムの方針


短時間系コンテストとの関連

MarathonSRMなどの短時間系のコンテストと全く違うのが、「最適解じゃ無くてもよい、というか最適解とか無理」という部分だと思います。

「ちゃんと良い解を得るにはどうすれば」とあまり深く考えていると、手が止まってしまって先に進まなくなりがちです。

SRMのレーティングは高いけれどもMarathonは苦手、という人は、このあたりで引っかかってるんじゃないでしょうか。


逆に、短時間系のコンテストで使うようなアルゴリズムは知らないでいいかというとそんなことはありません。

解答の一部にDPが登場することはよくありますし、探索や最短経路も頻出です。

事実、日本からの参加者をMarathonレーティング順で見ていくと、上位18人までがSRMのレーティング黄色以上、うち11人が赤経験者です。(2012-05-02現在)

https://www.otinn.com/groups/view_group.php?gid=1376&sort=14


Greedyは強い

Marathon何やったら良いかわからない」という人には「とりあえずGreedyで」と言っています。

もちろんそれだけで上位は取れませんが「この方針でこんなにスコア取れるのか」とびっくりすることは多いです。


ランダムは強い

上に同じ。

せっかく制限時間が10秒・20秒とあるのだから、計算パワーをめいっぱい使ってあげましょう。


逐次的に改善できるか

要は焼きなまし・山登り。この形にできるかどうかが大きな分かれ目になります。

焼きなましが有効であることが明らかな問題はみんなそれをやってくるので、そこまでたどり着いていなかったら勝負から蚊帳の外な感じになってしまいます。

焼きなませることが自明ではない場合にも、うまく状態の近傍を設計して逐次的改善が可能な形にできると強いです。


探索空間の削減

単純化して言ってしまうと、Marathonの問題というのは「ものすごく大きな探索空間から、いかに良さげな解を持っていそうなところだけを探れるか」です。

そこで、探索空間を減らすため、一部のパラメタを決めうってしまったり、嘘枝刈りを入れたりします。

この"嘘"の加減が重要なのですが、そのあたりが職人芸になる部分でしょうか。

 |