Topcoder Marathon Match Round90の参加日記

TopcoderのMarathonMatchは、過去3回参加していずれも上位3割くらいの結果に終わっている。よって目標は上位2割。

 

  • これまでの反省点まとめ
  1. 問題をちゃんと読む
  2. 紙と鉛筆で考えてから組む。いきなり実装しない
  3. Web等を参考にしすぎない。アルゴリズムは自分で考え、完全に理解したものを使う
  4. ローカルのバッチ環境は早めに構築する
  5. ビジュアライザも早めに作る(または改造する)。なるべくデバッグ・調査しやすいように
  6. 定数組み合わせがありそうならバッチを作る。手でやらない
  7. パラメタ調整にExampleケースは使わない。ケースが少なすぎる
  8. テスタのコードを読むべき
  9. 序盤はパフォーマンスより素直なデータ構造を優先する

 

  •  問題概要

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16495&pm=14094

  1. 二次元の迷路が与えられる。各セルは壁かEmpty
  2. Emptyセルに、色付きボールがランダムに置かれている
  3. 各色、ボール数と同じだけ、Emptyセルにも色がついている
  4. ボールは東西南北いずれかの方向に弾くことができる。はじかれたボールは、他のボールか、壁(迷路の端も壁)に当たると止まる。
  5. それぞれのボールを、なるべく同じ色のセルに入れる手順を回答する
  6. 手順の最大数は、ボールの数x20
  7. 迷路のサイズは、縦横それぞれ10~60
  8. 色の数は1~10
  9. 壁は迷路内の10~30%
  10. ボールの数は、Emptyセルの5%~20%
  11. 同じ色のセルに入っているボールは1点、違う色のセルに入っているボールは0.5点。平均点が最終得点になる
  12. 制限時間10秒

 

  • 方針と結果

ボールごと、点数の低い順に、よい点数となる次の手をDFSで求めていった。DFSの深さは15。ただし、同色のセルに到着したらそこで探索を打ち切った。

点数は色セルとの位置で決定している。点数の高い順に

  1. 同色セル
  2. 色セルから距離1(次に別ボールがゴールしやすいので)
  3. 色セルから距離2(同上)
  4. 色セルから水平に線を引いた時の上下のセル(別ボールを導きやすいので)
  5. 色セルから垂直に線を引いた時の左右のセル(同上)

3~5は壁のあるところまで。

かなり時間が余るので、初期配置から何度も繰り返して、ベストのものを回答した。

結果はスコアが82.20で、26位/76人(暫定)の定位置。

https://community.topcoder.com/longcontest/?module=ViewStandings&rd=16495

 

ちなみに上位20人は90点超え、1位にいたっては99点をたたき出していた。

 

上位者の方針(ForumとTweetより)

  1. Targetを指定してのBFSが多い。ボールもひとつづつやっているようだ
  2. 単純なBFSではなく、他のボールが邪魔な時は、それをどかして戻すことで次の盤面を増やしている(決定論的BFS?)
  3. Targetの優先順位を行っていた。ゴールさせづらいものを先に実行している
  4. 1位の人は、BFSではなく、Target周辺のボール数個でビームサーチをしたらしい
  5. Targetから逆向きにボールを探索する方法をとった方もいた(最小コストのパスを算出→これを満足させるのに必要な壁を別ボールで作る)

 

4のエッセンス部分のみ実装し、50秒で走らせてみたところ(高速化していないので)、Seed1~10の平均で約90のスコアがでた。

https://bitbucket.org/yambe2002/topcoder-marathon-match-round90/src/0fe148b270f91c488dd9a6ef2f365e01ad0fe127/?at=practice%20-%20beam%20search

 

  •  反省
  1. 早いうちにGreedy解を返すコードが完成したのはよかったが、これをいきなり改造し始めたのが悪手だった(サーチ方式を変えてみたり、パラメタ調整してみたり・・・)。検討不足の状態でただ方法を試しても時間の無駄
  2. Visualizerでもっと遊んでみるべきだった。検討が想像ベースになってしまっていた