AHC042振り返り
はじめに
AtCoder Heuristic Contest 042に参加した。制限時間4時間のAHCとしては「短期間」に分類されるもので、正直言うと苦手な部類であるが、今回も振り返ってみる。
問題
問題は節分ということで「鬼を追い出す」問題。盤面上の駒を行か列単位で動かせるので、全部の鬼を
入力の作成方法を読むと、初期状態において鬼は、必ず1つも福を追い出さずに追い出すができる方向を持っているとある。このため、例をみるのように、鬼を追い出してから元に戻せば、必ず福を1つも追い出さずにすべての鬼を追い出すことができる。
ただ、「元に戻す」コストがかかるので、元に戻さずにできる方法を考える。
解法
どの鬼を追い出すか?
盤面が与えられた時に、どの鬼から追い出すかを考えてみる。一度に沢山の鬼を追い出した方が良さそうである。
下図の真ん中の鬼を追い出した時、上に追い出すと福が1つ追い出される。下に追い出すと鬼が2つ追い出される。ここで全ての方向について (追い出された福の数, -追い出された鬼の数) とすると、上下左右は
鬼を基準とした移動方向
すべての盤上のある鬼に対して、4つの移動方向の上記tupleを導出し、小さい順に鬼を追い出すことを考える。これにより、追い出される福が小さく、追い出される鬼が多いtupleが選ばれる。
福をどかす
福をどかす
進行方向に福がいる場合、その福をどかしてから動かせば良い。例えば、上図の鬼を左方向に追い出す時、同じ行の福が落ちてしまう。そこで、同じ行の福を、その列を上か下かに動かして、道を明けるようにする。上図の場合、上に動かすと別の福が追い出されてしまうし、下に動かしても別の福が邪魔をしてしまう。このような場合には、今の鬼の動きを捨て、前節で求めた次の鬼の動きを候補とした。
これをすべての鬼を追い出すまで繰り返す。厳密には、福をどかすことができずに、解がでてこないパターンもありそうな気はするが、今回の150パターンは問題なかった。
ちなみにここで、「操作」について勘違いにしたのに気づいた。「3列目を上方向に2マス移動させる」という形式で指定できると勘違いしていた。
実際には「3列目を上方向に移動させる」という操作しかできないので、2マス移動させるときはこの操作を2回実施する必要がある。この勘違いは微妙に効いてきていて、1操作ずつでのビームサーチまでたどり着くことができなかった。
ビームサーチをする
実は前節までで残り30分。コンテストの時間フルに取り組めなかったためだが、仕方ない。「どの鬼を追い出すのか」が複数候補あるので、ここをビームサーチに変更した。なんとか時間ギリギリに完成させたが、点数としてはビームサーチの有無で1000点も変わらず、最終結果は457,000点台だった。トップが468,000点台なので、そんなに差がないようにも思えるが、300番以上は違うので大きな差である。
seed 0の結果
おわりに
今回、ほぼ決定的に解いてしまったが、上位は1手ずつ分けての、焼きなまし、山登り、ビームサーチっぽかったです。今回、鬼ベースで次の手を決めたため、それぞれの状態を「鬼の位置」と「盤面の状態」の2つで管理するようにした。このため、盤面を変更する時に鬼の位置も整合性を保つ必要があり、少しコードが複雑になった。順位としては約360番なので悪くはなかったと思うが、もっと上位を目指したい。
Discussion