暫定35,184,653点（得点率70%）で89位。
追記：システムテストは2,098,827,035点（得点率70%）で89位のまま。
解の一例（seed=4）
最初の土日
無。5月28日（土）～6月5日（日）のコンテストで土日が2回ある。
月曜日
問題を見始める。
スライディングパズルで木を作る。 問題の生成方法は、まずは全域木を作って、解くときの手数の上限回動かして崩すというものなので、全てが繋がった木が作れることは保証されている。 50%の点数が境目で、手数上限で全域木が作れると50% 手数がより少なければ点数が上がり、全域木が作れなければ、最大の木の大きさに応じて点数が下がっていく。
まだコードを書かずに、Twitterに上がるseed=0の完成図を眺めていた。 全域木が完成している人は、空白が右下の人が多い。 最初に正解盤面を作るときの空白は右下なので、右下の解があることは保証されている。 しかし、右下以外の全域木も上がっているので、右下が必須というわけでもない。 どういうことなのだろう。
そして、何をやってよいのか全く分からない。 「なるべく大きな木を作りましょう」なら色々とやることはあると思うが、上がる画像を見るに、ある程度の順位を取るには、全域木が前提っぽい。 普通に木を大きくしていくだけでは最後に詰まると思うんだよな。
火曜日
リポジトリを作って真面目に考え始める。 （ちゃんとスライドさせるのではなく）タイルを浮かしても良いから並び替えて目標の全域木を作る → スライドパズルとして解いて目標の全域木にする という方針が良さそうである。 スライドパズルにはパリティがあって、（タイルを浮かして並び替えた）全ての盤面のうちの半分は作れない。 しかし、この問題では最小サイズが35タイルなのにタイルは16種類で、必ず重複しているタイルがある。 鳩ノ巣🕊️ そのタイルを入れ替えればパリティを変えられるので、必ず解ける。 もちろん目標の全域木を決め打ってしまっては最適な解には辿り着けないけど、上述のように、普通にスライドさせて全域木を作るのはとても難しいだろう。
まずは見た目から入るとやる気が出る。 盤面の出力。 罫線素片（┗┏┃┻など）が使えそう……と思ったら、一方向にだけ出ているものが私の環境だと幅が違って合わない。 結局罫線は諦めて、こうした。
+ + +-- --+-- --+-- --+
| | | |
| | | |
+-- --+-- --+-- --+ +-- --+
| | | | |
| | | | |
+-- --+ + + + +
| | |
| | |
+ +-- --+ + +-- --+
| | | |
| | | |
+-- --+-- --+ +-- --+ +
| | |
| | |
+-- --+-- --+ + + +
全域木を作る方法。 左側に出ているタイルの個数と右側に出ているタイルの個数は同数だよね？ その辺を考えると、実は、閉路ができないように、場面外に辺が出ないようにと作っていけば、詰むことが無かったりしない？ → そんなことはなく普通に詰む。 ですよね。 2個のタイルの交換を近傍として焼きなませばいけるだろう → あまり上手く行かない。 7割くらいは全域木ができるのだけど、失敗することも多い。
全域木を作るのは一旦置いておいて、目標となる盤面ができたときにスライドパズルとして解く方法を考えよう。 手で解けるのだからそれをプログラムにすれば良いのだけど、とても面倒だな。 左上から順に揃えていくことにして、左上から何個目まで揃っているかと、次に揃えるタイルが目標位置とどのくらい近いかをスコアにして、ビームサーチをすれば良い感じになってくれるのでは？ なってくれませんでした。各行の残り2個のタイルと最後2列は、一度崩してから並び替える必要があり、適当に書いたビームサーチではそこを乗り越えてくれない。
どちらもダメで、今回はサボろうかなと考え始める。
水曜日
種類ごとのタイル数が揃っている＆全域木ではない から 種類ごとのタイル数が揃っている＆全域木である を作ろうとしていた。 これ、種類ごとのタイル数が揃っていない＆全域木である からスタートしてはどうだろうか？ という発想に至る。
初期盤面。タイルの交点を中心にしたときに4辺のうち3辺が埋まっている箇所が必ずある。 ここを回しても全域木であることは変わらず、タイルの種類が変わる。
これで焼きなましたら、だいたい全域木ができるようになった。 タイルの種類を変えていく場合、焼きなましに失敗したらどうしようもなくなるという問題はあるが……まあ何とかなるだろう。
スライディングパズルパート。 行ごとの最後2個のタイルについて、揃える過程に加点をして何とかした。
これで半分くらいは全域木が完成した50%のスコアを取れるようになった。 サブミットしてみたらTLE。 まあ、高速化の余地はまだいくらでもあるだろう。
木曜日
ビームサーチをする → 完成しなかったらパリティが違っていたと判断して、1箇所入れ替えてもう一度ビームサーチ としている。1回目で完成したかどうかで実行時間が倍違う。実際に解こうとしなくてもパリティは調べられるので、調べる。
途中で止まって全く進まなくなることがある。 状況を確認してみるとこうなっていた。
これ、先の図のポイントでは、4が1 ptの位置にいるので1 pt加算される。 ここから2 ptの状態に進むには4を崩さないといけない。 それができていなかった。 隣に5があったら4が目標位置にあってもポイントを加算しないようにした。
全域木がたまに作れないことがある問題については、単に全域木を作るパートを複数回実行するようにした。 ここは軽いので問題無い。
サブミットして27,529,855点。 全てのケースで全域木が作れるようになると、25,000,000点以上になるので、ドヤ顔でツイートしてみる。 なお、全てのケースで全域木が作れると25M点以上になることと、25M点以上なら全てのケースで全域木が作れていることは同値ではない。 実際このときも、他のケースで点を稼いでいるから25M点を超えているだけで、全域木が完成しないケースもちらほらあった。
そういえば、
□rich 要る？
— kusanoさん@がんばらない (@kusano_k) June 1, 2022
Sliding Tree Puzzleのseed=0で680556点を獲得!!!https://t.co/ZJs8SNYlTz #AHC011 #visualizer pic.twitter.com/doBr93BC4R
こんなツイートをしたけれど、ビジュアライザの「使い方」に後から気が付いた。
rich モードにすると、ランダムノイズが入って同じ種類のタイルの区別が可能になります。
手間が掛かっているし、実用性もあった。 同一の形状なら同じ模様だと思っていた。 すみません。
金曜日
盤面を2次元配列で扱っていたのを1次元配列化。 高速化に寄与するし、意外とコード的にも1次元配列のほうが楽。 どうせ最後にはやるので最初からやりましょう。 単純な書き換えではあるものの、どこかしらはミスるので、デバッグが面倒。
全域木から同じ種類のタイルを対応付けてスライドパズルの問題を作る部分で、今までは残っているものを貪欲に取っていたところを、距離の合計が最小になるようにした。 いや、最小費用流とか全探索とかで厳密に最小にはできるだろうけど、面倒だったので適当に焼きなまし。 簡単な問題だし、だいたい最適解になるだろう。 たぶん。 これがけっこう効いた。 貪欲に取ってもだいたい最小になるんじゃないかと思ったけど、1次元で貪欲に取っているので、2次元での距離を考えれば、そりゃそうか。
今までは全ての行で左から右に揃えていたところを、左→右と右→左を交互にした。 これは有効だろうと思っていたのに、あまり変わらず。 まあ、悪くなることはないだろうから、いいか。
ビーム幅を盤面サイズによって変えた。 手数上限が盤面幅Nの3乗で、1手あたりの処理は盤面の面積に比例するから、ビーム幅が同一ならば実行時間はNの5乗に比例ということで良いだろうか。 Nによる影響大きいな。
まだ100ケース中の数ケースで途中で詰まるものがある。 見てみるとこの形だった。
この形の何がダメなのかパッと見では分からなかった。 最後2個のタイルは全く揃っていない状態なので、次は4を右上に置こうとする。 その時の手順を考えると、先の4と5が逆になった形に必ずなるので、揃った状態まで辿り着けない。 こういうパターンが他にもありそうで怖いが……100ケースでは無くなったから、とりあえずいいだろ。 問題が出てくる度に評価関数で1個1個対処するのではなく、ビームサーチ側で何とかしたくはある。
残り時間が少なくなったときにビーム幅を減らす緊急回避を入れる。 これは単にTLEを回避することだけが目的ではなく、緊急回避があることによってビビらずにビーム幅を増やせるというメリットがある。 今となっては手数が上限に達することはほぼ無くなったので、上限まで回しても間に合うようなビーム幅にするのは無駄。 緊急回避モードに入っても意外とスコアが落ちなかった。 最後のほうは残りマスが少なくて優劣が付かないからそりゃそうか。 結局、緊急回避と言いつつ、数割はこのモードに入るようにしている。 もっと考えを推し進めれば、ビーム幅がずっと一定 → 急に減らす ではなく、徐々に減らしていくという手もありそうだが……やってはいない。
最後の土日
SECCON Beginners CTFと、Google Code Jam Round 3と、Pokemon GO Festで忙しくて、気が付いたら終わっていた。
パリティが合わなかったときにランダムに2個のタイルを入れ替えているけれど、これはタイルが遠いところになってしまう可能性がある。 パリティが一致するようにしたまま焼きなますのは試したかった。
