■ [TCO][MM]TCO12 Marathon Round1 
http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=15099&pm=11859
去年までとは選抜方法が変わったTCO予選ラウンド。
4位以内でfinal進出
問題
白か黒のマスがN*Nに並んでいる。それに加え、1つの黒マスを持っている。
盤面の上下左右どちらかから、手持ちのマスをどこかの列に押し込んでその列を1マス分ずらす。はみ出たものを新たな手持ちにする。
これを繰り返し、できるだけ少ない手数で白マスを全部連結させよ。
20<=N<=100, 5%<=白マスの割合<=40%
方針
どんな戦略をとったら良いのかよく分からないので、とりあえずマニュアルモードで遊んでみる
たとえば下から上へ一行ずつ見ていって、上の列にまだ連結していない白マスがあったら、下の列の空いているところにはめていく、
というような戦略が取れるけど、盤面の端で白がはみ出る場合の扱いが面倒で、実装しようとしたらとても難しい
そもそも、マニュアルモードでやった場合の点数が平均93-94点くらいだったけど、このとき既に1位のスコアが平均95を超えていた。
ので、人間の思考をプログラムに落とすというような方針ではなく、ランダム性・全探索性を入れて計算量使ってどうにかする方向だろうと考える
よくある方針だけれど、適当に盤面に評価関数を設定して、それが良くなるように動かしていくというのをやってみた。
評価関数の要素：
- 元々の長方形を推定して、各白マスがそれからどれだけ離れているか
- 初期状態の盤面は、白マスが長方形に固まっている状態からランダムに動かして作られているので、白マスの分布は完全にランダムではなくある程度固まってはいる
- 推定は、まず白マスが盤面上に何個あるかを数えることで長方形の縦横の長さの候補が出せ、長方形を盤面全体で動かしてみて一番多くの白マスをカバーするところが初期状態での長方形だ、とする
- ナイーブな実装だとこれだけで何秒もかかってしまうので、部分和を保存しておくDPにして計算量を落とす
- ただし、長方形への距離よりも（盤面の端への距離+長方形と盤面の端との距離）のほうが小さい白マスは、一旦盤面の外に出してから長方形と近い辺から入れ直すものとみなす。このタイプは早いうちに全部片付けておきたいので、大きなペナルティを付ける
- 各白マスについて、周囲4箇所のうち何個が白マスで繋がっているか
- 本当は白マスを全部連結させないといけないので1マスのまわりだけを見ても仕方ないが、全体の連結性を見るのは計算コストが高すぎる（1手動かしたときの差分更新が難しい）ので代用のつもり
- それでも、長方形に集めようとしている要素が効いてちゃんと全体が繋がっていくのが面白い
- 手持ちのマスが白の場合は、早く盤面の中に入れてしまいたいのでペナルティを付ける
この評価関数を使って、幅優先探索的に現在の盤面から可能な移動を何通りか試してみて、評価関数が良いものから上位数十個を残す。そして次のターンでまた同じことをやる、というふうにやった。
この方法、beam searchというらしい。 http://en.wikipedia.org/wiki/Beam_search
ここまでで、そんなに調整してないにもかかわらず平均93.55というスコアが出た。ゴールに到達すると保証されていない方針ではあるが、到達できていないのはローカルテスト1000ケース中わずか12個
ということでこれで行けそうだと思い、あとはひたすらこれを改善していった。
調整
制限時間いっぱい有効に使うためのいろいろ
- いったん解が出た後も、制限時間になるまで何度も同じ解法を繰り返す
- ある盤面から何通りか動かすとき、時間の関係で全部の列を試すわけではなくどの列を選ぶかにランダム性があるので同じ結果にはならない
- 一度解が出た後は、制限時間をあまり気にせずともよくなるので、よりよい解が出ることを目指して、次のターンのために残す盤面の数を増やす
- ローカルテストの結果、ほとんどが80点以上で70点台が1000個に1個というくらいの分布だったので、探索していて70点を下回ったときは、悪い状態にはまってしまったと見なして最初からやりなおす
高速化のためのいろいろ
- 盤面の評価値はもちろん差分更新する
- ゴールに到達したかを判定するのに、全白マスが連結しているかを確認しないといけないが、これが重い。そこで、1つも他の白マスと連結していない孤立白マスの数を覚えておいて1手動かすごとに更新する。これが0でない場合は即まだゴールに達していないと判定できる。これでこの終了判定にかかる時間が無視できるくらいになった
- 1手進めるごとに次の状態として保存しておく盤面を生成するが、そのメモリ確保でけっこうな時間を使う。最初に大きな配列を確保しておいてメモリプールとして使い回す
- 各白マスについて周囲に何個白マスがあるかは、個数ではなくビットフィールドで覚える。こうすると差分更新しやすい
- 白マスが存在する範囲のバウンディングボックスを保持しておく。どの列を動かすかの候補を列挙するとき探す範囲を狭めるのなどに使える
- 乱数はjava.util.Randomクラスを使うよりXorShiftのほうが速かった
その他の工夫
- 盤面は周囲に番兵を置いて(N+2)*(N+2)で持つと扱いやすい
- Nが小さかったり元々の長方形が細長かったりするときは、白マスが2つの塊に分かれてしまっていつまでやっても答えにたどり着けないケースがあるので、評価関数のいいものだけではなく一部ランダムに拾って残す
- 前回の移動と逆向きの移動（2手前に戻るだけ）はほとんど意味がないのでやらない
- 0点が怖いのでローカルで大量にテスト（10000ケース）した
反省など
ひたすら調整ゲーになってしまって、楽しさの点ではいまいちだった。
この方針だと答えを出せない可能性があるので、最悪0点は回避するため一瞬で実行できる自明解を用意しておくべきだった。
けど、けっこう面倒だし、順位表的にどうせそれが出てしまったらその時点で負けな感じだったのでやらなかった
最大の連結成分に連結していない白マスが残りわずかになったら、動かす列をランダムに選ぶのではなくて残っている白マスの近くだけを選ぶと良かったかもしれない。うまく実装できず見送った
時間が余った分はただ同じ解法を繰り返すだけになって、逐次的に改善する形にできなかった。そうできていればかなり良くなりそうだけど、どうやったらいいかは分からない
前回の解の半分の長さまでは同じように動かして、そこから別の乱数でやり直す、というのはやってみたけど全然良くならなかった
結果
- 暫定スコア 9584.52（100ケース）
- 暫定順位 5位/148人
- 最終スコア 288120.52（3000ケース）
- 最終順位 4位
- レーティング 2230→2285
参加者数が少なかったのは、正のスコアが取れる自明解を作りづらい問題だった、というのが一番の原因でしょう。
あと、スコアが絶対評価だから潜伏して結局提出しなかった人も少々いそう
Tシャツ狙い的には一番の穴場ラウンドだったかもしれない。
オンサイト狙い的にどうだったかはよくわからない。
去年の年末のTopCoder飲みで「TCOオンサイト行けるようがんばる」と言ったのが現実になって良かった。
Algoの方もRound3まで残ってるので期待しましょう
動画
seed1
seed2
seed3
