AHC050振り返り

はじめに

AtCoder Heuristic Contest 050に参加した。順位は500番台だったので書かない方がいいかなぁと思ったが、自分の記録のために書いておく。

問題

時期的に七夕からみかなぁと思っていたが、問題は、Gamble on Ice。ギャンブルなので777を意識したのだろうか？
スケートリンク上に、初期位置も移動方向もランダムで、岩があるまで進むロボットがいる。そのスケートリンクの上に順番に岩を置いていく問題。岩の下にロボットがいると潰されてしまう。最終的には全部岩で埋め尽くすので、ロボットは潰されるのだが、できるだけ長くロボットを潰さないでいるとスコアが高くなる問題。結構無茶苦茶な問題である。

解いてみた

データ構造

まず、それぞれのマスにロボットがいる時に、次にどこに移動するかを管理することした。これは岩の配置により一意に決まる。また、新たに岩を置いた時、移動先が変わるマスは隣の岩との間にあるマスだけになる。下の図でオレンジの枠の部分に新たに岩を置いた場合、オレンジ色のマスだけが次の移動先が変わる。

ロボットが次に移動するマスと、岩を置いた時に移動先が変わるマス

ロボットが特定のマスに存在する確率を保持しておけば、次の移動先マスに1/4ずつばら撒けば、次のターンでロボットがいる確率になる。例えば上の図で青いマスにロボットがいる確率が 4%だった時、次のターンで上下左右の矢印の先にロボットが存在する確率は等しいので、1%ずつになる。初期位置はランダムなのですべてのマスは同じ存在確率になり、岩の数$M$を使ってり$1 / (N^2 - M)$で表される。あとは岩を置いて、移動先を修正して、確率を求めて...とすれば問題のゲームを模擬できる。

どこに岩を置くのか

単純に、ロボットのいる確率が一番小さい場所に置くとしてみた。意外とうまくいってSeed0のサンプルで917,905点であった。ビジュアライザでは色が濃いマスがロボットの存在確率が高い。

ロボットの存在確率が最も低い場所に置く

山登り法を追加してみる

ここから山登りしていけば最適化されるかな？と思って実装してみた。近傍解としては岩を置く順番の入替。ただ、150個ほどの近傍解しか回せなかったので、ほぼ変わらなかった。しかも、制限時間を増やして効果を確認しようとしたところ、スコアの計算を間違ったようで、山登り法なのにスコアが下がっていた。結局ここで、時間切れ。

延長線

ロボットの存在確率の偏りを大きくする

上のビジュアライザの動きを見ていると、確率が0の場所が意外と多いように見えるので、一番存在確率が小さいマスからランダムに選択するのではなく、その中でどこを選ぶか？が大事だと思われる。その観点で上位のソースコードを見ていると、選択肢のブロック配置のまま何ターンか回してみて、存在確率の偏りが大きいものを選択する様にしているものがあった。具体的には確率の5乗の和をスコアとして利用していた。そこでそれを実装した。

整数演算で近似する。

計算量が増えてしまったので、計算速度を早くするためにロボットの存在確率をfloatで演算していた部分を整数演算で近似することとした。1/4ずつばら撒くので、初期値としてすべてのマスに$4^8$を設定した。最大値はすべてのマスのロボットが1つのマスに集中した時で$4^8 (N^2 - M) \leq 2^{27}$となり、32bitに収まる。最小値は$(4^8(N^2 - M))^{-1}$なので$10^{-8}$以下は0になってしまうが、問題なさそうな気はする。
これで実行時間は30%削減できた。

改良結果

Seed0のサンプルで984,270点と大きく点数が上がった。ただ、ローカルでは時間内に収まったが、サーバに上げるとTLEがでたので順位は不明であった。

おわりに

改良後のビジュアライザを見ると細い道ができていることがわかる。これを見て思い出したのが「勇者のくせに生意気だ」というゲーム。T字路を作ってコケを滞留させたりするゲームであるが、この問題はそれだったんだぁと思ってしまった。