AHC 011 参加記 - sankantsuのブログ

問題概要

$N \times N$ の盤面が与えられ，各タイルには4方向のうち1つ以上に線が伸びた図形が描かれている．空きマスを適当に移動させることでタイルの絵をつなげて，できるだけ大きい木がつくられるようにしたい．

結果

プレテストで最終44位

マラソン参加2回目(長期は1回目)のわりには健闘できたのではないかと思う．今回は大きさ $N^ 2 - 1$ の木を完成させられるかどうかという点が大きな分岐点となっているように感じており，完成させるためのアイデアを比較的はやく思いつくことができたところが良かったと考えている．

追記: システムテスト後の最終順位は 42位 (2,321,975,585 点, 1問あたり 773991点) ．TLEなどで下がらなくて良かった．

コード

github.com

いくつかのファイルに分けて実装している．提出したソースは， solve.cc を oj-bundle で展開したものである．

方針

今回用いた方針は，おおまかには以下のようになる．

完成盤面を生成
現在の盤面から完成盤面に一致させるようにパズルを動かす

まず，完成盤面の生成の方法について簡単に説明する．

はじめに，問題文にある盤面生成と同じ方法でランダムに木をつくる．ここでつくった木は，ほとんどの場合初期盤面と各タイルの数が一致しないので当然そのままでは完成盤面として使うことはできない．そこで，枝を適当に付け替えることによって初期盤面とタイルの数が一致するように変形させる．枝の付け替えというのは，木に適当に一本辺を追加して閉路をつくったあと閉路内の辺を一本削除してタイルの数が初期盤面に近づくようにするという操作を繰り返すことによって行った．実質的には初期解をランダムにいじって良くなったら採用するという山登り法になっている．

次に，現在の盤面から完成盤面への移動方法を考える．

各タイルに最終的な配置を事前に割り当て，この配置を実現するような経路を探索すれば良さそうである．タイル配置の割り当ては，とりあえず左上の位置から順に一番マンハッタン距離が近いタイルを割り当てる貪欲法で行った．割り当てたタイル配置が実際に解ける配置になっているかどうかは配置順の転倒数を用いて判定し，不可能な配置になっている場合は適当にタイルを入れ替えることで解消した．

経路の探索については各タイルの現在位置と目的位置とのマンハッタン距離の和を評価関数としたビームサーチで実装してみたものの，今回の盤面サイズでは時間内に解を見つけられなさそうな様子であり断念． (上位陣の解法はビームサーチが多いようであるので，配置割り当てや評価関数などもっと工夫が必要だったかもしれないと思う．)

確実に時間内に解を見つけるようにしたかったので，とりあえずタイルを端からひとつずつ愚直に運ぶという方針で実装した．ここまでで基本的にすべての入力に対して $N^ 2 - 1$ の大きさの木を完成させる手順を構築することができるようになった．

この実装をベースに手数を減らしていく工夫をいくつか行った．今回実装した手数削減に関する工夫は，主に以下の2点になる．

タイル配置の割り当てを動的に行う
同時に複数のタイルを揃える

まず変えたのはタイル配置の割り当て部分である．タイルをひとつずつ運ぶ場合には，最初からすべての配置を割り当てていく必要はなく，次に運ぶタイルさえ決まっていれば構わない．そこでタイル配置は各位置を埋める直前で動的に割り当てることにした．

また，タイルをひとつずつ運ぶのは目に見えて非効率である．タイルを複数同時に運ぶことで手数を削減したい．そこで，揃えるタイル数が少ない場合に特化したソルバをA*で実装し，これを使って2つまたは3つ単位でタイルを揃えた．

基本は上の行から順番にそろえるが，最後の3行は左から順に同時に揃える．また，最後の $3\times 4$ 領域に残る 11個のタイルは一度に一気に揃えた．

実行例をひとつ gif で貼っておく (807870点)．

考察過程

ここからは日記に近いものになる．

序盤

初日，ルールをざっと確認したあとまずは得点計算を注意してみる．得点計算を観察すると，パズルを全タイル使って完成させられるか否かで壁ができているのでまずは全タイル使ってパズルを完成させることを目指したい．タイル数は $N^ 2$ に対して許容手数は $2 N^ 3$ と比較的余裕があるように見えるので，手数はあまり気にせずパズル完成の方法を考えることに集中することにする．

1週間という長期のコンテストで比較的時間があるので，まずはビジュアライザで遊びながらいろいろ考察してみる．手でやってわかったがこのパズル，タイルを全部使い切って完成させるのはかなり難しい．デフォルトで表示される $6\times 6$ 盤面は何度かやり直して一応手で完成させることはできたが，パーツ数などをかなり注意深く考慮しないと完成は難しく，適当にぐるぐる回していてもパーツが余ってしまって完成しないのではないかという印象を持った．完成図を先に決めてしまったほうが良さそうである．

どうやったら完成図をつくれるだろうか？盤面全体をいくつかに分割して，分割どうしのつなぎ目を固定した盤面をつくれないかとか，有名な空間充填曲線 (ヒルベルト曲線など) のパーツをつくってつなぎ合わせるとか，一番上の列から列同士をつなぐ部分のパターン分けの方法をDPなどで考えられないかとか考察してみるもなかなかまとまらない．

最終的に思いついたのが，木を先に適当につくってしまいつなぎ目を適当に組み替えるというものでこれならうまくいきそうである．

とりあえずの方針が定まったので，得点計算やランダムな盤面生成，タイルの移動処理など基本的な部品から実装を進めていく．ランダムな木を生成するのは目標となる盤面の生成にも使うことになるだろう．

実装にも後から手を入れやすいよう慎重に進めていく．前回初参加したAHC010 では終了後も続けて書いていたが，最初行き当たりばったりで実装を進めていたために後から手を入れにくくなってしまい，結局後から書き直すことになった．少なくとも1週間は付き合うことになるコードなので，競プロというよりもまともなソフトウェアを書くつもりで進める．とはいえ，あまり実務経験があるわけではないのでコードの質はまだまだだとは思うけれども． AHC010 のコードのリファクタリングを通してクラスをうまく使うことで比較的すっきり書けることを学んでいたので，はじめからクラスを使いながら書いてみることにした．

月曜ぐらいまでで，一通り目標としていた最終盤面の生成や基本部品の実装を済ますことができた．

中盤

最終盤面をつくったら，どのタイルをどこに移動させるかという割り当てを決める必要がある．ここはあまりアイデアがなかったので，とりあえず端から順にタイルを見ていってその時点で一番近いものを貪欲に割り当てるという方法を採用することにした．後から考えるとタイル配置の割り当てはグラフ上のマッチング問題とみなせるが，このあたりをきちんと整理して考えられなかったのはアルゴ力の不足と感じる．

最終盤面の生成と並行して，初期盤面から最終盤面へと移動させるにはどのようなやり方を使うのかということを考えていた．自分でこの手のパズルのソルバを書いたことはあまりなかったのでやりかたをいろいろと検索してみることにする．スライドパズルといえば有名な15パズルがあり，これなら解法もいろいろと情報があるだろうと思い検索してみた．不可能配置の解消なども検索で得た知識をもとに行った．

調べた結果これらのパズルの解法としてはどうやらAやIDAといったアルゴリズムなどを使うのが定番らしいとわかったが，これまで探索アルゴリズムは普通のDFSとBFSぐらいしか実装したことがなかったので，A*などのアルゴリズムをもう少しちゃんと調べることにする．どうやらこれらはゴールまでの距離をヒューリスティクスで予測して見込みのあるものから優先的に探索する手法ということがわかった．

A*を使うならどういうヒューリスティクスで評価関数を求めるかということが重要になる．各タイルの現在位置からゴールへのマンハッタン距離の和を使うのが定番らしいとわかったので，とりあえずこれで書いてみることにした．

実際動かしてみると，どうも今回の盤面サイズではこれだけではまともに探索するのは少々厳しいようである．探索時間を減らすためビームサーチ化 (これもはじめて書いた) したりもしてみたが， $6\times 6$ ぐらいならときどきうまくいくが $10\times 10$ などは手も足も出ないという感じだった．

幸い最大手数には余裕があるので，確実にパズルを完成させられる方針で実装することにする．採用したのは，タイルを端から順に一個ずつ完成位置に埋めていくという非常に愚直な方法である．これなら複雑な探索を行う必要はないので実行時間は問題にならなさそうである．

次に埋めるタイルを移動させる手順はA*で探索させることにしたが，これは結局空きマスが運びたいタイルに向かうようにして，目標のタイルを動かした結果，最終位置との距離が縮まれば採用するだけなので非常に単純な評価関数で書ける．各行の最後の2マスは1つだけ埋めてしまうともう一方が埋められなくなるので同時に考える必要がある．ここは1つずつ順に最終位置から1マス離れた固定の場所に運んでおいて固定手順で処理することにした．タイル位置が入れ替わっているような例外ケースも手動で解いた手順を埋め込んで対処した．

ここまでの実装が済んだのが4日目の火曜日．初の有効な提出で 29,259,891 点を獲得． 33位という経験のない順位につくことができて嬉しかった．

終盤

タイルを1つずつ揃える愚直な方法でもまあまあな結果は出せていたが，改善の余地があることは明らかだった．まず，手動で手順を埋め込んでいるのもあって，右に行った直後に左に行くような明らかに非効率な動作が混ざることがあったので，これを解消する必要があった．また，実行時間にはかなり余裕があったので，制限時間内ランダムに完成図を作り直して経路探索し直すことでより良い解を見つけるだけでもだいぶましになりそうである．これらの簡単な改善を導入して提出した結果，33,255,140 点まで伸ばすことができた．

次に取り組んだのはタイル配置の動的な割り当てである．どうせタイルを一個ずつしか揃えないのなら，わざわざ最初に全部の配置を割り当てる必要はない．タイルを揃える直前に次に動かすタイルだけ都度決めるという方法に変えることにした．最後タイルが少なくなってきたときに，不可能な配置を防ぐため残っているタイルすべてに配置を割り当てる．この方法でまた多少スコアが改善し，35,255,532 点に到達した．この時点の暫定順位が27位であり，結局このコンテスト中最も良い順位となった．

ここまでで実装としてすぐに改善できる部分は終わってしまった感じがある．後は，タイルをひとつずつ揃えるかわりに2つや3つ一気に揃えることで手数を削減できるだろうと考えた．これまで使っていた実装だと探索のときに発生する盤面のコピーなどが無駄にコストが大きく非効率に感じていたため，少数の注目するタイルだけの位置を記録するソルバを書き直すことにした．ここでも使ったアルゴリズムはA*である．

盤面の1部分を揃えるコストを調べる方法として事前にパターンデータベースを作成するといった手法も調べていて知ったが，事前に計算した結果を利用するものなので今回のような提出形式には合わないと考え断念した．小規模なパターンデータベースなら工夫によっては使うことはできるかもしれないが．

A*で少数のタイルを同時に解くにあたって，評価関数に改良を加えた．具体的には，現在位置と目標位置とのマンハッタン距離に加えて，次の2つを導入した．

目標位置と同じ行(列)内でタイルの順番が入れ替わっているときにペナルティを課す．
目標位置に到達していないタイルの中で，現在の空白位置から最も遠いタイルまでの距離を足す．

1つ目は検索していて出会ったもので，いくつかの記事で Linear Conflict という名前で紹介されている． 2つ目は少数のタイルを解くという問題設定を考える上で独自に導入したものであり，タイルが何もない方向に無駄な探索をするのを防ぐ役割ができているのではないかと考えている．

これらのアイデアを使って数個のタイルを同時に解くソルバを書き，既存の1つずつ揃える実装を置き換えた．まずは2個ずつタイルを揃えるようにして，これがうまくいったあと 3個ずつ揃える実装に書き換えた． 3個揃えようとすると時々時間をかなり消費してしまいTLEの危険があったので，探索が長くなったら適当に打ち切ってフォールバックするなど行う必要があった．

揃える順番をジグザグにしてみるなど少しいじってみたりもしたが，大きな改善があったかは微妙．

探索失敗時のフォールバックの実装にやや手間がかかりここでコンテスト終了ぎりぎりに．最後の提出では 38556229点を獲得し，プレテスト44位で終了した．

欲を言えば順位表2ページ目以内になんとか入りたかったところだが，マラソン初心者にしては十分健闘したと思うし満足している．