AtCoder Heuristic Contest 042 お疲れ様でした。467,474点で16位です。軽めに解説記事を書いていきます。
問題概要
鬼は外！福は内！
解法
「ある行・列に鬼を集めて一気に運び出す」を1回の遷移としたビームサーチを行いました。操作1回を1回の遷移としたビームサーチだと、上手く評価関数を設計しないと良い動きにならないように思え、何かしら意味のあるひとかたまりの動きを1回の遷移とした方が良さそうに思えたためです。*1
いい感じの鬼の集め方を求めるため、DPを行っています。福を能動的に動かすことはしませんでした。*2
ビームの持ち方
ビームサーチのキー（ターン）や評価関数を何にするかの選択肢として、ビームの遷移回数・手数・鬼の数など様々なものが考えられますが、今回は手数をビームサーチのキーとし、鬼の数を評価関数としました。
1回の遷移に 手かかるとき、ビームの状態は
ターン目から
ターン目に遷移することになります。
これを0ターン目から順に進めていき、最初に鬼の数が0匹になったものが見つかったら解として出力します。
遷移の作成
「ある行・列に鬼を集めて一気に運び出す」操作の最小手数をDPを使って求めます。なお、このとき福が盤面の外に出てしまうような操作は許容しません。
例えば 列目から上方向に出荷する場合について考えます。
上から
行目までを使って、鬼を
匹運び出すときの最小手数 とします。
行目を左右に動かして鬼を持ってくるのに必要な最小手数を
*3 とすると、
- DPの初期化:
- DPの遷移:
- (
行目を左右に動かさない,
- (
のように求めることができます。
これを各列の上下方向・各行の左右方向について求めるとたくさん遷移の候補が出てきますが、かなり無駄な遷移も出てきてしまう *4 ので、良さげな遷移のみを残すことにします。 を鬼を運び出すコスパとして、そのコスパの良い（小さい）5個のみを有効な遷移としました。
その他
評価関数を鬼の数だけで決めているので、ビームの中が評価値の同じ状態で溢れることになります。実装にも依りますがそのままだと多様性が失われるため、シャッフルしてごまかしています。
ビーム幅は200くらいでした。コピーコストに対してDPが重いのと、自作の差分更新ビームサーチが1ターン先までの遷移にしか対応していないため、普通に状態をコピーするビームサーチを行っています。
重複盤面の除去のためにハッシュを用いますが、特に工夫せず盤面をZobrist Hashでハッシュ化しています。*5
感想
解法はサラッと書いていますが、コンテスト中はバグらせまくってなかなか辛かったです……。ともあれ無事提出までは漕ぎ着けたので良かったなと。上下左右それぞれ手書きは不可能だったので、copilotくんにかなり手伝ってもらいました。
ビームサーチ勢の中ではそれなりに良い遷移を設計できたのではないかと思うのですが、焼きなましは頭になかったですね……。言われてみれば確かに一昨年の企業対抗戦のように焼けそうで、これを思い付けなかったのはちょっと悔しいです。とはいえ1ページ目には入れたのでまあ悪くはないかなと思います。
今年は短期コンの数が倍増しているので、いろんなバリエーションの問題に取り組めそうですね。今からとても楽しみです！
