AtCoder Heuristic Contest 011 参加記 (6位)

AtCoder Heuristic Contest 011 に参加しました。
結果は 6 位でした。

解法を大雑把に言うと、「盤面と操作列を同時にビームサーチで探索する」です。

せっかくなので、時系列順にやったことをまとめてみます（問題概要は省略します）。

第一実装：最終盤面、操作列の順に作って大きさ $n^2-1$ の木を作る

最終的に上位とやり合うためには、大きさ $n^2-1$ の木（完全解と呼ぶ）を作らなければならないと推測されたので、まず完全解を作ることから考えました。そこで、

完全解となる有効な最終盤面を1つ構築 -> その盤面になるような操作列を構築

の順で構築して完全解を作ることを第一実装の目標としました。

完全解となる有効な最終盤面を作る

Web 版のツールを使って手作業で何かヒントを得ようとしましたがサッパリ分からなかったので、乱拓 DFS で盤面を作ることをまず考えました。
ここで、「完成図が1つの木になっている」条件と「スライドパズルで遷移可能である」条件の2つを考えなければいけませんが、先に「スライドパズルで遷移可能である」条件を考えておきます。

スライドパズルで遷移可能である条件

manabitimes.jp

高校数学（？）によると、各タイルに番号を振って 1 対 1 の対応付けを行った後は、「置換のパリティと空きマスの移動距離のパリティが一致している」ことが遷移可能の条件です。
ここで、仮に適当に盤面を作ってタイルに番号をテキトーに振った時に、上記のパリティ条件が成立しなかったとします。
このとき、タイルの種類は 15 種類であることから同じ種類のタイルが必ず 2 つ以上あるため、2 枚の同じ種類のタイルの番号を入れ替えることで、盤面の図はそのままでパリティ条件を満たすことが出来ます。
よって、最終状態の図を 1 つ固定した場合、その図を作るような操作列は必ず作れることが分かります。操作列のことは考えず、盤面の木をどうやって作るかを考えれば良いことが分かりました。

何枚かタイルを置いた時点での完成図が 1 つの木になるための必要条件

盤面を左上から順に乱拓 DFS でタイルを埋めて木を作る際に枝刈りするために、木になるための必要条件を考えました。
まず、線がタイルや盤面の境界で切れてはいけないことがまず考えられます。こちらは、毎回タイルを置く際にチェックすることが容易です。
次に、サイクルがないこと，非連結にならないことが必要条件で考えられます。
これらについては、第一実装では巻き戻し操作ありの Union-Find (My-Algorithm/UnionFind_reverse.hpp at master · kopricky/My-Algorithm · GitHub) を使うことで対応しました。この段階では、盤面に非連結な孤立した木がないかは1段全て埋めるごとに確認していました。

乱拓 DFS では、テキトーに残っているピースからランダムに選択することを行い、各箇所について 7 回までチャレンジして無理だったら 1 つ前の箇所に戻るようにしました（※戻る操作の際に Union-Find の巻き戻しを行います）。

このようにして、試しに実装してみると、高速に盤面を見つけられることが分かりました！これで少なくとも完全解は出来そうです。

固定した盤面を生成する操作列を作る

最終盤面を固定した場合に、どうやってそれを達成するかを考える必要がありました。
第一実装では下図のように番号付けすることで、 $n \times n$ のスライドパズルと見なすことにしました。

初期盤面で番号を振る必要があり、各タイルについて最終盤面とのユークリッド距離の総和が小さくなるようにしたいので、最小重みマッチングで決めました。このとき、パリティ条件が合わない場合はテキトーに同種の 2 つのタイルについて番号を swap しました。

$n \times n$ のスライドパズルが解ければ良いところまで来ました。
貪欲に揃えることを考えたくなりますが、テキトーな順で 1 枚ずつ揃えようとすると、例えば上図で 1~5 まで揃えたときにどうやって 6 を埋めるかみたいな話がかなり面倒に見えました。
そこで、(1,2), (3,4), (5,6)... のように 2 枚ずつ埋めることにしました（ただし、 $n$ が奇数の時や最下部などは端からいい感じに置けるような順にしました）。
2 枚ずつ埋めるのは ( 1 枚目のタイルの位置，2 枚目のタイルの位置，空のマスの位置) の 3 つを管理する BFS で最短路とその経路を計算することが可能です。
また $n$ が奇数の場合、右下の $3 \times 3$ については最後まで放置して計算することにしました（ $9!$ の状態を持つ最短路計算）。

以上を実装して提出したところ、35,937,271 点で（4 位, 2日目時点）でした。
(いい感じだ～と思いながらも、周りもどんどん上がっていくんだろうなと恐怖していました)

第二実装：盤面をピースに分けて貪欲に作る～表引き編～

次の実装でも、第一実装と同じく、盤面を決定->操作列を決定の順で構築しました。

盤面を決定するところでは、非連結判定の枝刈りをより強くしました。
その時点でまだ埋めていない場所に隣接し、かつ線が埋めていない場所に伸びているような場所を管理することで、1枚置くごとに非連結判定ができるようにしました。

最も大きな変更は操作列を決定する箇所です。
第一実装では毎回 BFS で操作列を計算しましたが、あらかじめ表を作ることで、毎回の計算をしなくて済むようになり高速化できます。
まず、最初に下図 ( $n=8,9$ の例) のように盤面を複数枚のタイル（ピースと呼ぶ）ごとに分割します。

dp[何個目のピースを埋めているか][動かすタイル集合の位置][空白の位置] = (動かすのにかかる最短手数，次に動かす方向) とすると、これは BFS と同様に計算が出来ます。
ただし、表が持てるサイズならば3枚，4枚も同時に動かすことにしました。

第一実装では先に各タイルに番号を振っていましたが、それをやめて、最も最短手数が短いようなタイル集合を毎回動かすことに変えました。
ただし、 $n$ が偶数の場合は右下の $3 \times 3$ になったら、 $n$ が奇数の場合は右下の $4 \times 4$ になったら、パリティ条件を満たすように番号を振りました。

以上を実装し、制限時間一杯まで「盤面を決定->操作列を決定」を繰り返し最短なものを答えとすると、40,524,660 点 (6日目時点) と大台の 40M を超えることが出来ました。

第三実装：ビームサーチを導入する～初めてのビームサーチ～

第二実装を終えた段階で、これを高速化してもあまり性能は出なさそうという気がしたので、新たなフレームワークを導入することにしました。

ビームサーチの亜種 (chokudai サーチと呼ばれる？) を使って、盤面の決定と操作列の決定を同時に探索することにしました。
（ビームサーチに関しては tsukammo さんの記事競技プログラミングにおけるゲーム木探索の面白さ - Qiita を参考にさせていただきました）

状態としては、
（現在の手数，現在の操作列，現在の決めた盤面，union-findの情報，その他諸々）
を管理して、現在の手数を比較のためのキーとして用いて、盤面と操作列を同時にビームサーチしました。
このとき、第三実装で定めたピースごとに盤面を決定し、操作列を第三実装と同様の貪欲で決定しました。また、各状態からはランダムに 6 通りまで有効な遷移先へと遷移することにしました。

これを実装したところ効果は絶大で、43,134,292 点 (7日目時点) と第三実装と比較して 3M も増加することが出来ました。

第四実装：要らない情報は持たない～そして限界切り詰めバトルへ～

最後に、高速化してビームサーチの幅を増やすために、無駄な情報を状態として持たないように変更を加えました。

最終的に持った状態は
（現在の手数，残りの各タイルの枚数，操作列，現在の盤面，フロンティアの情報）
となりました。
ここで、フロンティア法と同様のテクニックを用いました。 *1

もう少し丁寧に説明すると、下図のように、まだ置いていない場所に線が伸びているようなタイルについて、連結成分の番号を保持します。この番号をタイルを置くごとに更新していきます。

このようにすると、次の図のように、サイクルを検出できます。

（同様に、非連結な孤立した木が出来てしまっているかなども判定できます。）

これにより、UnionFind の情報を持つのは不要になり、持つ情報を減らすことが出来ました。

その他の高速化として、周りの接続の状況を考えると、盤面に置くタイルの候補は高々4 通りしかないので、乱拓をする際にその 4 通りから選ぶように変更しました。

以上の高速化を加えて、各状態からの遷移を 10 通りまで選ぶことにすると、 43,499,848 点（5 位, pretest 時点）となりました。

結果：

最初に述べたように、システムテストの結果は 6 位でした。
点数の分布は以下のようになっていました（<=780000 のところは全て出力が上手く行っていないケースで、何も出力していません）

AHC011 - Sliding Tree Puzzle - Statistics を参考にさせていただくと、
$n=10$ のケースでは全体 3 位でかなりいい感じのようでしたが、最後まで戦っていた $n=6$ などの小さいケースではあまりスコアが伸びていませんでした。
上位は焼きなましをしていた（？）ようなので、そのあたりで大きく差をつけられたようです。

特に、最後の 30 分で、出力が間に合っていないケースなどが見つかり、途中結果を出力するかしないかだけで順位を1つ落としたように見えたのが一番残念でした。

ただ、長期コンテストで 6 位は望外な結果なので嬉しかったです。

問題も最後まで面白く取り組めて楽しかったです。

知見と反省点：

最後に今回初めて知ったことや感じたことなどをまとめておきます。

最終提出までに、 1000 ケースくらいやって生成してテストしておくべきだった（100ケースでチューニングすると落ちるケースに気づけない）
パラメータ調整は不十分だった。手元で調整するための環境を整えるべき。
AtCoder のジャッジは手元より遅いので時間計測はかなり気をつけないといけない。
大量にメモリを vector などで確保するとメモリ解放に時間がかかって TLE することがある (200 msくらいかかることもあった)。
初手乱拓 DFS は結構良い、ビームサーチも実装してみるもんだ
長期コンはとにかく何でもかんでも実装した方が良い（実装したくないという心との戦い）
焼きなましはやっぱり強い

*1:フロンティア法は、数え上げお姉さんで有名な Zero-suppressed Binary Decision Diagram (ZDD) という列挙に強いデータ構造を構築する手法として知られています(解説スライド: https://hs-nazuna.github.io/tdzdd-manual/fbs-inst.pdf)。競プロ文脈だと ZDD が絡まない場合にも表現として使われますが、正しい表現なのかは私にはよく分かりません ( ZDD 関連で修論を書いたのに・・・)。

第一実装：最終盤面、操作列の順に作って大きさ の木を作る