TopcoderのMarathonMatchは、過去3回参加していずれも上位3割くらいの結果に終わっている。よって目標は上位2割。
- これまでの反省点まとめ
- 問題をちゃんと読む
- 紙と鉛筆で考えてから組む。いきなり実装しない
- Web等を参考にしすぎない。アルゴリズムは自分で考え、完全に理解したものを使う
- ローカルのバッチ環境は早めに構築する
- ビジュアライザも早めに作る(または改造する)。なるべくデバッグ・調査しやすいように
- 定数組み合わせがありそうならバッチを作る。手でやらない
- パラメタ調整にExampleケースは使わない。ケースが少なすぎる
- テスタのコードを読むべき
- 序盤はパフォーマンスより素直なデータ構造を優先する
- 問題概要
https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16495&pm=14094
- 二次元の迷路が与えられる。各セルは壁かEmpty
- Emptyセルに、色付きボールがランダムに置かれている
- 各色、ボール数と同じだけ、Emptyセルにも色がついている
- ボールは東西南北いずれかの方向に弾くことができる。はじかれたボールは、他のボールか、壁(迷路の端も壁)に当たると止まる。
- それぞれのボールを、なるべく同じ色のセルに入れる手順を回答する
- 手順の最大数は、ボールの数x20
- 迷路のサイズは、縦横それぞれ10~60
- 色の数は1~10
- 壁は迷路内の10~30%
- ボールの数は、Emptyセルの5%~20%
- 同じ色のセルに入っているボールは1点、違う色のセルに入っているボールは0.5点。平均点が最終得点になる
- 制限時間10秒
- 方針と結果
ボールごと、点数の低い順に、よい点数となる次の手をDFSで求めていった。DFSの深さは15。ただし、同色のセルに到着したらそこで探索を打ち切った。
点数は色セルとの位置で決定している。点数の高い順に
- 同色セル
- 色セルから距離1(次に別ボールがゴールしやすいので)
- 色セルから距離2(同上)
- 色セルから水平に線を引いた時の上下のセル(別ボールを導きやすいので)
- 色セルから垂直に線を引いた時の左右のセル(同上)
3~5は壁のあるところまで。
かなり時間が余るので、初期配置から何度も繰り返して、ベストのものを回答した。
結果はスコアが82.20で、26位/76人(暫定)の定位置。
https://community.topcoder.com/longcontest/?module=ViewStandings&rd=16495
ちなみに上位20人は90点超え、1位にいたっては99点をたたき出していた。
上位者の方針(ForumとTweetより)
- Targetを指定してのBFSが多い。ボールもひとつづつやっているようだ
- 単純なBFSではなく、他のボールが邪魔な時は、それをどかして戻すことで次の盤面を増やしている(決定論的BFS?)
- Targetの優先順位を行っていた。ゴールさせづらいものを先に実行している
- 1位の人は、BFSではなく、Target周辺のボール数個でビームサーチをしたらしい
- Targetから逆向きにボールを探索する方法をとった方もいた(最小コストのパスを算出→これを満足させるのに必要な壁を別ボールで作る)
4のエッセンス部分のみ実装し、50秒で走らせてみたところ(高速化していないので)、Seed1~10の平均で約90のスコアがでた。
- 反省
- 早いうちにGreedy解を返すコードが完成したのはよかったが、これをいきなり改造し始めたのが悪手だった(サーチ方式を変えてみたり、パラメタ調整してみたり・・・)。検討不足の状態でただ方法を試しても時間の無駄
- Visualizerでもっと遊んでみるべきだった。検討が想像ベースになってしまっていた