AHC011に参加しました。
問題はSliding Tree Puzzle。
スライドパズルの問題です。
得点は37.4Mで理論値の75%弱。
登録4073人、提出961人中、59位でした。（暫定テスト62位）
問題
木（グラフ的な意味で）が書いてるスライドパズルを完成させてね。
完成した場合は手数が少ないほどいいよ。
考察（初期）
基本はデカい15パズル。
同じパネルが複数あるのと、木が成立さえすればいいので解が複数ある。
MM120前後に似た問題があったような。あれは回転だったか。確か端から順に作っていって、探索が利くサイズになったら探索という解法がメジャーだった。これもそれで良いんじゃないかな。
手数上限は2 * N^3。
パネルを1マス動かすには、最大で
↓←←
→■↑
のような5手*1+動かすパネルに近づくための手数を使うので、最小のN=6でも愚直な移動が間に合いそう。Nが大きい方が余裕があるのかな。とにかく設計図さえ完成すれば手数不足になることは無さそうだ。
逆に設計図を作らず行き当たりばったりで都合よく木を作れるかというと厳しそう。
再反復化とか色々手法はあるようだけど、結局解が見つからない限り深いBFSをすることになるのでは？
A*…も良い評価関数を書いて短い手数で到達出来てこそだよなあ。基本的には隅から完成させないと局所解にはまりそうで、そういうのも評価関数に盛り込んで…辛くない？
順位表やseed=0共有を見た感じ、トップ層もN=6で100手くらいは使ってそう。流石に深すぎ。
設計図を作るには、DFSか焼きなまし…多分焼きなましかな。
設計図自体にも良し悪しはあるし、多様性を出したいなら焼きなましの方が良さそう。
（DFSは最後まで回しきれないと前半の値が偏るので）
あとはもう、一度作ってみるしかないね。
もうちょっと考察（途中で気づいたこと）
「木であること」を良い感じに利用する方法が何かあるんじゃないか？
閉路が無くて、T字や十字は枝の統合*2のためだけに使われている。
未接続の辺がある部分木を統合していくとか…はきつそうかな。
でも、葉の数が決まっていて、T字十字が枝の統合だけに使われているということは、再構築して全連結したものも閉路が生じることは無い…？全連結できたら閉路気にしなくて良いじゃん。
あとはパネルの移動なんだけど、
↑
↑
↑←←←
こういう移動をするとき、
↑←
↑←
↑←
こうした方が良い。
↓←←
→■↑
上記手順は5手かかるが、
↓←
■↑
上記手順は3手で良い。縦横ジグザグに動くとこの3手パターンの連続になる。
なので、移動コストは
Min(dx, dy) * 6 + (Max(dx, dy) - Min(dx, dy)) * 5
となる。（dx=x距離、dy=y距離）
終了後の感想：探索する解法の人が評価にユークリッド距離を使うと良いと言っていたのとちょっと関連ありそう？
あとはパネルを1個ずつじゃなくて複数纏めて運べたらいいんだけど、並べる順番は正しいか、分断が発生しないか、という考慮が必要になってくるので結構苦しい…。2個までならルールベースでなんとかなるか？でもジグザグ移動によるコスト軽減が大きくて、2個じゃそこまで効果出ないんだよね。
（順番的には複数運びたいねの方が先にあった）
そういえば、MM128(Regional)にちょっとだけ似ている？目標盤面を作って愚直に動かす。同種タイルが盤面全体に散っていた方が、現在位置と目標位置のマッチングで改善しやすい。ロールケーキ食べたい。（MM128でもAHC011でもkomoriさん強かった）
現在位置と目標位置のマッチングはタイルの種類ごとに出来るよね。密なのでハンガリアン法でもそこまで問題なさそう。
最終的にやったこと
全体像
1.焼きなまし法で設計図を作る
ここでの目標は、全連結かつ初期盤面に近い設計図を作ること。
2000msまで焼きなまし、最大10件の設計図を作成する。
局所解にはまりやすそうだったので、3件並列で焼きなましした。また、10件の設計図は多様性を持たせたかったので、完成したら最初からやり直しとした。*3*4
設計図の評価は移動元と移動先でマッチングしたコストの総和（コストは移動の実コスト）として、優先度付きキューで上位10件を取った。
2.設計図通りにパズルを解く
2800msまでパズルを解き、最短の手順を作成する。*5
ひたすらルールベースで時間いっぱい何回も解く。初回は貪欲だが、2回目以降は少しずつランダム要素が増していく。たまに解けないパターンになることがあるが、主にマッチングのせいなのでマッチング部分のランダム比重を増やす。
今までの最善スコアを達成不可能になったら足切りする。（見込みは特に計算せず、実際にオーバーしたら足切り）
詳細
1. 焼きなまし法で設計図を作る
近傍は2点swap、評価は連結成分のサイズ^2の総和。温度は固定。
全てのタイルを同一連結成分にすることが目的なので、同一連結成分にならない原因となっているタイルを交換しやすいように優先度を付ける。隣接セルの一方だけが辺を伸ばしている状態、隣接セル同士で同一連結成分でない状態が不整合なので、それらのセルをいくらか優先する。*6
最終目標は全連結なので、この評価でいいのか？というのはちょっとある。どちらかというと、完成できない場合を見越した評価だよね。*7
外周のタイルが外に辺を向けないことは自明なので、前処理として焼きなまし開始前に貪欲で外周のタイルを近場のタイルと交換している。効果はあまり無かったかも…？
また、15パズルだと完成不可能なパターンというのがあるが、同種タイル同士を交換することでパリティをほぼ回復できる。*8そのため、そのチェックは行わなかった。あと、全連結した場合は閉路ができないので閉路チェックもしなかった。全連結できなかったら破滅しようね。
2.設計図通りにパズルを解く
2-1. 3×3になるまで一辺ずつ設計図通りに完成させる
探索しきれる保証があるのは3×3。
残りがそのサイズになるまでは、一辺ずつルールベースで愚直に完成させる。どのタイルをどこに動かすかはハンガリアン法を使った二部マッチングで決定した。*9コストは愚直に移動する場合の実コストとした。
一辺の最後の2マスは同時に完成させないといけない。最後の2マスの目標セルそれぞれにタイルが既にあるか（また、その位置が正しい側か）で場合分けしてルールベースで動かすようにした。
ここでは、奥、手前、開始側、のような概念を扱えるものを作ったのが結構効いた気がする。これが無ければ実装量が8倍か、非効率な動きをしないといけなかった。*10
2-2.3×3を完成させる
これは完全にアルゴで、初期盤面と完成盤面の双方向からDFSするだけ。
ただし絶対に解けないパターンがある。その判定方法はサイトによって書いていることがまちまちだったが、最終的には下記サイトを参考にした。*11
8パズル，15パズルの不可能な配置と判定法 | 高校数学の美しい物語
感想戦スペースで双方向DFSが上手く行くのが分からんという人がいたので少し補足。
3×3は同種タイルが無い場合でも最大31手であることが証明されている（らしい）ので、
一方が15手、もう一方が16手探索したところで盤面がぶつかって完成できる。
3^15=14,348,907
3^16=43,046,721
なので、もっと刈れることを考えればギリギリ全探索できそうなライン。
（実際は初手は最大4方向なのと、端にいると1～2方向にしか動けないので厳密な値ではない。盤面数はこれよりかなり少ない）*12
参考までに、4×4は最大80手なので3^40=12,157,665,459,056,928,801*13で死ぬ。
やってみたかったこと
・探索
分岐の種類が多くて時間的に対応が無理そうだった。*14
・複数を同時に運ぶ
2個同時で、最大2割*15くらい手数を削減できたかも。でも限界が見えているから実装の重さもあってやりたいことではないなぁ。
・大きい盤面をヒューリスティックで解く
上位陣は割とこれっぽい。大体A*系統やビームサーチ系統。
A*はちょっと気になってたのでやってみたかったけど、基本的に1発勝負になりそう。私は数を撃つ方針だったので切り替えは辛かった。
・雑に運んで3×3を完成させるのを繰り返す
N=6なら3×3が4個、N=9なら3×3が9個あるものとみなせる。
ただ3×3が解無しになるのを避けないといけないので、そこが割と大変そう。
3×3の初期盤面と完成盤面の対応パターンは9P9=362,880で前計算や埋め込みが出来そうなので、その部分の計算はO(1)になる。
最終日はこれをやるか悩んで、結論としてお昼寝した。
日記
1日目
DFSで完成図作成できるかな～。無理だね。（辺の分断のみで枝刈り）
閉路禁止で枝刈りとか、枝で格子を作って葉を中に置くようにすれば多少マシ？でもN=10は厳しくない？
（UnionFindで閉路チェックできることに気づいていない）
2日目
焼きなましで完成図作成できるかな～。出来そうだね。
雑にswapを1秒回せばN6～8は行ける。N9～10も孤立は1～2個程度か。今は保留するけど近傍弄れば行けるっしょ。
（2,3ケース回しただけなので失敗が多いことに気づいていない）
3日目
移動元と移動先をマッチング。
実際に動かすところは実装イヤイヤ。
1個ずつなら行けそうだけど、15パズルで言うところの3,4同時セットがきついよ。
4日目
1タイル動かすのを途中まで実装。
5日目
1タイルを動かすのが完成。
4つ運ぶのに52手。40M取れる動きじゃないなあ。
2タイル動かすのは場合分けするしかないのか？
40M前提なら複数同時に動かす前提で作るか、1列一括で動かすとか作った方が良さそう。
6日目
場合分けしまくって最後2個動かすのが完成。
上手く動いたので、3*3を残して完全に動くようになる。
7日目
3*3を完成させる。
テスト用にPsyhoさんのmmtesterを導入。
無限ループがあると挙動が壊れるらしく、無限ループ対策を行う。
6*6が不可能パターンなことはほぼ無いんだけど、3*3の残り方によって不可能になるっぽい。
乱択要素を入れて時間いっぱい試行。とりあえず回って平均65%。
8日目
ん－、これ3*3を解いて回る問題では…？
実装したくないなぁ。
9日目
とにかく悪い状態を引くとスコアが落ちるので、焼きなましも移動シミュも多点にしまくる。雑に設定していたパラメータを調整していく。あとお昼寝。
感想
今回は多数のアルゴリズムを組み合わせて使う問題で、かつ最適な解法がすぐに出てくる問題ではなかったので、かなり負担が大きかったです。
1辺ずつ完成させる方針でも、最後の2個同時セットを作り切らないといけないのでスコア50%の壁が大きかったですね。
今回は手法よりは参加態度が駄目駄目で、何かを見ながら作業していつの間にか手が止まっているというのが常態化していました。*16
いや、手法も駄目だったんですが。証明されてないけど実際にやると上手く行く系はどうも漏れやすいですね…。これを解決するのは知識よりは意識の問題な気がします。あと挑戦したうえで滑り止め方針を準備できる実装速度。
何にせよ、もっとメリハリ付けてやりたいですね。
*1:返し縫いっぽい。本返し縫いよりは半返し縫いの方が糸が短くて良さそう。
*2:逆から見れば分岐。
*3:完成したものをそのまま焼き続けても大きい違いが出にくかった。
*4:こういう感覚でしたが、終盤までbestでなくcurrentを返すバグがあり、感覚が間違っている可能性があります。
*5:ジャッジ上だと+98msくらいになり、2900msだとかなり怖かった。
*6:同一連結成分でないことはそのセルが原因とは限らないが。
*7:動いてるからヨシ！
*8:同種タイルが2個あれば絶対に回復できるようです。
*9:一辺完成するたびに再マッチング。
*10:作りは結構酷くて20点レベル…。
*11:僕にはよく分からないけど偉い人がこんな事を言っていたよ、という論調の情報は疑って見た方が良さそう…（特大ブーメラン）
*12:他の方によると、9! = 362,880通りらしいし、双方向からやらなくても普通に間に合うらしい。
*13:実際は16! ≒ 2e+13通り
*14:どの辺をどの方向から完成させるか、移動元と移動先のマッチング、移動する際の経路
*15:最高に都合が良かった場合。
*16:実装イヤイヤ。
