AHC011の日記です。ちゃんとした解説を読みたい方はリンク先の解説記事をどうぞ。
日記と言いつつコンテスト終了後1週間後に書いています。日記とは……。
1日目（土）
今日と明日は中部地方旅行。短期コンじゃなくてよかった。
名古屋駅でごはんを食べながら問題を読む。スライドパズル……。スライドパズルか……。そもそもスライドパズルで遊んだことがないのだけれどどうすれば。
どうせ上位陣は当たり前のように木を完成させてくるんだろうな。ガチャガチャ動かして直接木を作るのは難しそうだからとりあえず完成図を作ってからスライドパズルを解く方針かなあ。その方針でダメそうだったらその時考える。
操作回数は回か。タイル1枚あたり
回と考えると結構ギリギリ？*1
友人氏との待ち合わせが13時なのでそれまでスライドパズルについて調べてみる。そもそも解ける配置と解けない配置があるらしい。ふむふむ。アルゴリズムとしてはA*とかが使えるらしい。それはそうなのだが、A*といっても結局は全探索でしょ？4x4程度ならまだしも6x6とかになるともう無理では？別に厳密解が欲しいわけじゃないんだよな。しかし他に賢いアルゴリズムも特に見当たらない。
人間はどうやってスライドパズルを解くのだろうと調べてみる。左上から1枚ずつ揃えると良いらしい。1行分のラスト2枚を揃えるのが難しくて、車庫入れ？とかいうテクが必要らしい。ルールベースでごちゃごちゃする必要があるけれど、これなら確かに揃えられそう。
大学時代の友人氏と合流したのであいち航空ミュージアムへ。機械工学のバックグラウンドを持った人同士でこういうところに行くと余裕で半日が溶ける。マジでオススメです。急なお願いに付き合ってくれて本当にありがとう……。
ホテルに着いたので問題の考察をする。maspyさんが38M点で圧倒的1位になっている。最初勘違いしていたが、暫定テストは100ケースではなく50ケースらしい。もう半分まで縮めてるの！？やっぱりパズルつよつよerじゃないと厳しいんだろうか……。
とりあえず入力部分と、盤面の可視化コードを書く。罫線記号を使ってこんな感じに。*2
明日も早いのでABCには参加せず早めに寝る。
2日目（日）
名古屋駅から近鉄で鈴鹿サーキットへ。SUPER GT 第3戦を観に行く。天気が良いのはありがたいのだが、めちゃくちゃ暑い……。
EOS 7D mark II + EF400mm F4 DO IS II USM + EXTENDER EF1.4×IIIという構成。重い。席は1コーナーだけど、逆バンクというところまで歩いて行って撮影。確かに良い絵が撮れて満足。
帰りの新幹線のなかでPCを開く。まずはスライドパズルであることを無視して木を作っていく。といっても貪欲的に解くのはかなり厳しそうで、できるとしたら焼きなましだろう。ダメだろうなと思いつつ、どんな問題か感覚を掴むため「木の辺が繋がったらボーナス、繋がらない辺があったら大幅減点」みたいな貪欲を書く。無事閉路ができた。それはそう。
まあ焼きなましだよなあ。家に着いたので、とりあえず初期盤面から2点swapの焼きなましを書く。評価関数は閉路がない連結成分のサイズの二乗和。時間をかけると意外と焼ける。すげー！
╻┏━━╸┏╸┏╸╻ ┣╋━┳━╋┳┫╻┃ ╹┗╸┗╸╹┃╹┗┫ ┏━┓╻╻╻┣━━┫ ┣┓┃┃┗┻┛┏━┫ ┃╹╹┃╺┓┏┻╸╹ ┃┏┓┃╺┫┃╺┳╸ ┗┫┃┣┳┻┫╺╋╸ ╻┃┗┫┣╸┣┳┻╸ ┗┻╸╹╹╺┛┗╸
閉路検出はUnion-Findでやっていたけれど、はタダじゃないらしい。DFSの方が3倍速かった（それはそう）。
思ったより焼きなましの試行回数が少ないなと思っていたら最適化オプションを付け忘れてた。アホ。
ここまで来たらスライドパズルを揃えるところまで書いてしまいたい。木ができたらマンハッタン距離でマッチングを行ってパネルに番号を付ける。パネルを行きたい方向にスライドさせるには空きマスをタイルの横まで持っていってあげるとよさそう*3で、これは2次元グリッド上でBFS。車庫入れはググって出てきたものをハードコーディング。ちゃんと揃うよう偶置換・奇置換には気を付ける。死ぬほどバグらせながら書いて初提出すると27Mで22位。まあ悪くないかな。
// 車庫入れハードコーディング（ひどい） fn get_parking_moves_v( input: &Input, row: usize, cursor: Coordinate, fixed: &Map2d<bool>, ) -> Vec<usize> { let target = Coordinate::new(row + 1, input.n - 3); let mut moves = bfs(input, cursor, target, &fixed); // https://kowasekeishin.com/15puzzle/ moves.push(1); moves.push(2); moves.push(2); moves.push(3); moves.push(0); moves.push(1); moves.push(0); moves.push(3); moves }
3日目（月）
ちょうど業務が忙しくてなかなか時間が取れない。が、やっていく。
今は木を作った段階でタイルに番号を割り振って固定してしまっているが、これを揃えながら動的に変えてしまった方が良さそう。1枚ずつ揃えるのはそのままに、一番近いタイルを選ぶようにする。31.4M点で22位。
マッチングのコストも焼きなまし段階で考慮するようにしてみる。あまり上手く行かない。一旦ボツ。
4日目（火）
ルールベースで揃えるのは限界があるので色々調べる。「フォローしているアカウント」にチェックを入れて「スライドパズル」でTwitter検索すると、2011年にGoogle主催のDevQuizというコンテストでスライドパズルが出題されていた痕跡が発見される。もうちょっと調べると、解法晒し祭りのまとめ記事があった。助かる。
強い人はやっぱりA*系を使っていそう。でもこのコンテストはローカル実行で時間かけられる系っぽいしな……。使ったことがないアルゴリズムを使うより、できればいつものアルゴリズムを使いたい。とりあえずビームサーチを書いてみる。
端を揃えると高得点とか評価関数に入れてみたが、同じ場所をぐるぐる回るばかりでうまく揃えてくれない。一旦揃えたものを壊したりするような動きを行ってくれないんだろうな。やっぱり全探索寄りのアルゴリズムじゃないと局所解から抜け出せなさそう。ビームサーチはボツとして、IDA*を書いてみることに。
5日目（水）
IDA*は初めて書くが、多分こんな感じだろｗと適当に書いてみる。全部一気に揃えるのは無理なので、上から1行ずつ揃えていき、残り2行になったら左から1列ずつ揃える。当然探索すべきノードの数は指数関数的に増えていくので、ノード数が増えすぎたら一番いいやつを残して残りを全部捨てるようにする。
バグを一通り取って投げると35.6Mで25位。いろいろ改善すると37.3Mで15位。まだmaspyさんに追いつけないのですが……。ちなみに1位は42M。強すぎ。
6日目（木）
（この日だけちゃんと日記が書かれていた）
今の自分が37.3M、トップが42M。実行時間を長くしてやってみたけど、どう足掻いても現状のままで手数が2/3まで縮む気がしない。
木の構築とスライドパズルを独立した問題ではなく組み合わせて出題してきた点がポイントなのでは。多分愚直にスライドパズルを解くだけじゃダメで、何かしらのズルをする必要がありそう。パズルを解きながら答えの盤面を変えちゃうとか。途中で焼いていくと良い？スコアは良いものが思い付かない、というか厳密なスコアを出すのは多分不可能だけど、とりあえずマンハッタン距離の総和をいい感じに引いてあげればいいか。
いい感じに、が難しいんだよな。上の文章書いたの誰？
現行解法のビジュアライザを見てみる。やっぱり下の方までタイルを取りに行っていてもったいないよなあ。これを解消できると強そう。
最終タイルのマスにどのマスのパネルが来るか？を解として持つ。初手でカーソルを右下に持っていった後は2点スワップ近傍で改善。偶置換・奇置換の差分更新はBITを使わず
で可能（flipすればよいだけ）。これとカーソルの右下までの距離の偶奇が合えばパズルが完成可能なので、そのときのみbest解を更新する。
疲労が溜まっているのでプロテインを飲んで早く寝る。
7日目（金）
パズルを揃えながら動的に答えの盤面を変えちゃうのは良いアイデアだと思ったが、実装してみると上手く行かなかった。そもそも今の焼きなましの性能が悪く、局所解を抜け出しにくいのがかなり問題な気がする。現状の焼きなましだと木を作れる確率も7～8割くらいしかなくて、複数回やることで誤魔化してるんだよな。上位陣は安定して構築しているはずだし絶対にもっと良い焼きなまし方が……うーん……。
8日目（土）
水曜日から進捗がないので焦るも、相変わらずいい焼き方が思い付かない。
Twitterで流れてきた「ダンジョンの中のひと」というマンガが気になったので読んでみる。おもしろくてかわいい。オススメです。*4
買い物に行っていたら焼きなまし方が生えた。今は「タイルの枚数を常に満たす」ように焼いているが、逆に「木であることを常に満たす」ように焼いてもいいのでは？「木」とか「連結」みたいな条件は評価値が連続的でなく取り扱いづらいので、そちらを気にしなくて良いようにするという発想。
上手く行くという確信は持てなかったが、実装してみると今までとはうって変わって一瞬で焼ける。すごい。*5
ABC終了後、揃えながら焼いて動的に完成図を変えるやつを実装してみる。面白いように点数が上がった。とりあえず3日ぶりの提出をすると38.8Mで27位、ちゃんとパラメータ調整して投げると40.2Mで17位。
興奮して眠れないので、自明な改善としてIDA*を双方向IDA*にした。41.0Mで11位。
9日目（日）
あの、こっちが弊社コンということになりませんか pic.twitter.com/ZLX2CZm5tl
— TERRY (@terry_u16) 2022年6月4日
※前回のAHC010で爆死していた
最終日だが、やりたいことはだいたいやれたのであとは細かい調整のみ。
- 焼きなまし中のマッチングをフローから貪欲に変更（40.9Mだが手元では伸びた）
- 木を焼きやすいよう上→左→上→……と逆L字型に揃える（42.0M）
- パラメータ調整（42.2M）
- バグチェック（10000ケース回して落ちなかったのでヨシ！）
コンテスト終了時点で42.2M、暫定14位。
その後
システムテストで1つ順位を上げて最終13位になった。
レッドコーダーになれたのでうれしい。
terry_u16さんのAtCoder Heuristic Contest 011での成績：13位
— TERRY (@terry_u16) 2022年6月7日
パフォーマンス：2655相当
レーティング：2797→2816 (+19) :)
Highestを更新し、五段になりました！#AtCoder #AtCoderHeuristicContest011 https://t.co/JTyipIXQwY
ついにヒューリスティック赤コーダーになりました……！ pic.twitter.com/0bSSSuEutX
