AHC 011 - Kiri8128の日記

AHC 011 でやったこと・考察したことなどをつらつら書きます。最終的なアルゴリズムを見たい人は最終日（9 日目）の項目へ。

1 日目（5/28 土）

【昼】

子供と公園に行ったり人生ゲームをしたりしていたので実装はできなかったけど、問題文は読めた。

【考察】

15 パズルの一般化として「 $N^2-1$ 」パズルを考える。 15 パズルはやったことがあるので分かるけど、到達可能な配置であれば *1 基本的に 1 枚ずつ決めていける。角になるときはスペースが足りなくてつらいけどそれ以外はすでに決めたタイルを動かさずに決められることが簡単に分かる。「到達可能」かどうかは、本当は偶置換・奇置換の問題があるが、本問では同じタイルが少なくとも 1 組はあるので大丈夫。

手数は 1 枚決めるのに $O(N)$ かかるので、全体で $O(N^3)$ 手でできる。

本問では同じタイルがたくさんあるので、各タイルを見る際に必ず距離 $O(1)$ の範囲に同じタイルがあると仮定すると、全体で $O(N^2)$ でできそう。定数倍がそこそこあるのと $N$ が小さくて怖いけど、本問の制約 $2N^3$ だとまあなんとかなるだろう。

よって、おおまかな戦略として下記があげられる。

① タイルの多重集合が与えられたケースと同じにあるような「木」を探す

② その木をターゲットとして 15 パズル（「 $N^2-1$ 」パズル）を愚直に頑張る

これをするなら全ケース「木」にできる前提になっちゃうけど、まあできるかなという感覚（つまり最低でも 25M 点は出るはず）。直感的にはさすがに全ケース「木」はできるとして、 30M ～ 40M ぐらいを目指さないといけないのかなというイメージ。

【戦略】

一番簡単な戦略としては、上で挙げた

① 木を探す

② 木に合うように 15 パズルをする

を独立に（①→②の順に）する方法がある。もっと効率よくするなら②で有利になるように①を決めるとか、①と②を合体して焼きなましするとかいろいろありそう。

焼きなましは（Python だと時間的に）不利になりそうなので、メインの解法としてはあまり選択肢には入れていない。

【夕】

1 時間ぐらいあいたので実装してみる。

この時点で 25M はいないので、上の戦略で大丈夫なら提出できるところまでいければそこそこ上位に行けるはず。

【①について】

適当な「木」を作ってからランダムに入れ替えるみたいな雑な操作でいけないかな。

木をキープする近傍は、まじめにやると大変だけど、コの字型になっている 4 マスの空き辺を動かす操作は $O(1)$ でできるので、とりあえずこれでできればラッキーということでやってみる。

「ぴったり一致」まではいけず・・・

（コの字型の図解は下で）

【夜】

賞金 ABC があったので出てから AHC の実装に。

夕方やってたのをもう少しちゃんと実装してみた。具体的には、

・ランダムに木を作成する

・入力で与えられたタイルの多重集合との差分を考える

・差分がなるべく小さくなるように「コ」の字型を回す操作をたくさんする *2

をランダムにやる。「ぴったり一致」じゃないと意味ないので、焼きなましはあまり使えなさそう。とは言え局所解は怖いので、「ある程度小さくなったら逆側もたまに許す」みたいにすると、一応非現実的とまではいかない時間でぴったり一致するものが出てくることもありそうなことが分かった *3 。とりあえず全部繋ぎ（ $25M$ 相当）を作りたいので、前半部分の高速化はあとでやることにして、その後の 15 パズル部分を（雑にでも）実装したい。

② 15 パズル部分

アルゴリズムとして簡単なのは、 1 枚ずつ順番に決めていく方法。これだと、動かしたいタイルを 5 手で 1 マスぐらい進めることができる。まあ $T$ の制約にはぎりぎり間に合いそうだけど最善からは程遠い感じ。一度実装してしまうと後戻りしづらいので悩んでるうちに時間が過ぎてしまった。

ところで、デバッグ時に盤面を表すのに「罫線文字」をうまく使うと見やすくなった *4。

2 日目（5/29 日）

自分も家族も体調不良でダウン。。「いのちだいじに」

寝ながら脳内考察は少しだけ。昨日は偶奇の問題は大丈夫と思ってたけどそうでもない気が。同じ種類のマスが複数あるのでたしかに必ず到達可能ではあるんだけど、好きな順に貪欲に決めていくと最後に困る可能性があることに気付いた。同じマスがなくなる瞬間に気を付けるか、最初から最後の 3 マスに同じ種類のマスを 2 種類入れておくなどをするとラクそうと思った。

3 日目（5/30 月）～ 4 日目（5/31 火）

仕事＆体調不良でほぼ進まず。最高 38 度の熱と頭痛・喉痛・鼻水で何も考えられない。火曜日は有給とって病院で診てもらいつつ PCR 検査もしてもらった。

その後もほぼ寝たきりだけどちょっとだけ考察。ただ、脳内考察をしても実際に実験してうまくいくかとか時間・試行回数がどれぐらいになるのかを試せないのがとてもつらい。

AHC やりたいけどベッドから出れずに仕方なく脳内考察してるけど実装も実験もできないの辛すぎて発狂しそうになっている
— きり (@kiri8128) May 31, 2022

発狂しながら冷静になって考察したところいくつか気付きなどを得た。

「コの字型」以外にも、「一本だけ出ているマス」も自由に回転して良いことに気付いた。これで自由度が上がるので前半ステップが速くなるはず（？）。
前半ステップが終わった段階で、ターゲットまでの距離の合計とかで簡易判定すると良さそうなものを選別できる。距離の合計の最小値は Min Cost Flow でできる。計算時間はよく分からないけどまじめに後半ステップをするよりは早いだろう。
15 パズルとかでググってみると、 $A^{*}$ というアルゴリズムがあるらしいということが分かった。ヒューリスティック関数というのを使うと高速で探索できるとのこと。よく分かってないけど後半使えるかも？

回転について

「コの字型の部分を回転する」、「一本出ているマスを回転する」の図解はこんな感じ。

コの字は 4 マス、一本は 1 マス（とそれに隣接するマス）が対象。図のように緑の部分を移動しても「木」であることは保たれる。

$A^{*}$ について

ググるといろいろ出てくるが、寝ながらスマホで理解しやすかったのはこれ。

yamakatsusan.web.fc2.com

通常の Dijkstra では、スタートからの距離 $d_v$ が小さい頂点 $v$ から順に探索する方法だった。

$A^{*}$ は、予め（手動で）ヒューリスティック関数 $h_v$ を決めておき、 $d_v$ の代わりに $d_v+h_v$ の小さい順に探索を行う方法とのこと。 $h_v$ は頂点 $v$ からゴールまでの距離に近いものが望ましいが、実際の距離以下であれば正しい結果を返すことが保証される（これでも Dijkstra より高速化される）。 $h_v$ を実際のゴールまでの距離よりも大きくすると、正しい結果が保証されない代わりにより高速化できる。

5 日目（6/1 水）

体調はまだだいぶ悪い（頭痛・鼻水・喉痛）けど 1 日目の 1 マスずつ愚直に動かすアイデアをやっと実装してみる。結構汚い実装でつらいけど、なんとかできた。ただ最後の偶奇とか途中のコーナーケースはあまり考えていない。雑にやった感じ、 $N=10$ でちょうど 2000 手ぐらい。これだと 25M ぎりぎり乗るかどうかで細部詰めてもいまいちになりそう・・・。

6 日目（6/2 木）

【夜～翌朝】

今こそ発狂しながら覚えた $A^{*}$ を使うときが来た。いくら $A^{*}$ でもさすがに $10^{2}$ マスは全部はきつい印象だけど、 2 ～ 3 マスずつ適用すれば今の 1 マスずつよりだいぶ短くできるはず。

ヒューリスティック関数としては、各パネルのマンハッタン距離の合計を使うのが良いと書いてあったが、近いところはうまくいかないかもなので「 $\max( \mathrm{ManhattanDistance} - 2, 0) * K$ 」みたいにした *5 。 $K$ は 3 ぐらいまで下げればほぼ理論値になる気がする。高速化したいときは 10 とか 100 とか適当に増やせば良さそう。

雑に実装すると、手数が $N=10$ で 1000 手ぐらいになった。ほかの $N$ でも $N^{3}$ ぐらいになってるので、これが確実にできれば $37.5M$ になるはず！

あとは偶奇調整が残っているけど、めんどくさいので

右下の $3\times 3$ の 9 マスの中に同じパネルが少なくとも 1 組あるようにする（そうでないと棄却する）
最後の 9 マスは一気に $A^{*}$ をする

という手抜きで乗り切ることにした。

前半がミスる確率は $\displaystyle\frac{_{15}C_{8}}{15^{8}} \fallingdotseq 10\%$ ぐらいなので大きな問題にはならないだろう。

9 マス $A^{*}$ は Python だとそこそこ時間ロスだけどこの際仕方ない *6 。

ついでに「一本だけ出ているマス」も実装する。

木の盤は、簡単のため必ず右下が空パネルになるように決めた。あとパネルを決める順番は右上からヘビ状に順番に決めることにした。

ここまでのロジックは

与えられた状態を board とする
木の状態の盤 tree_board をランダムに作る
tree_board のうち、「一本だけ出ているマス」または「コの字型になっている箇所」を探して回転するという操作を、 board と tree_board のパネルの集合が一致するまで繰り返す。
ただし、差が 9 枚以上なら山登り（差が減る方向のみに進む）、差が 8 枚以下なら簡易焼きなまし（差が増える場合は $20\%$ の確率で採用）、みたいにした *7 。
board と tree_board のパネルの集合が一致したら、 tree_board をターゲットとしてパネルを合わせていく。合わせる順番はヘビ状（下図）で、最後の 9 マスは一気に合わせる。
合わせ方は、基本的には 2 枚ずつ $A^{*}$ をする。具体的には、次に決めたい 2 マスに使うパネルを、最も近いものから選ぶ。選ばれたパネルを目的地に移動する（疑似）最短距離を $A^{*}$ で求める。という感じ

1 回まわすだけで TLE になったり、謎の RE が出たりで苦しんだ。

TLE 解消として、前半の山登り・簡易焼きなましでのコスト変化を $O(N^2)$ かけていたのを $O(N)$ に落としてみた *8 が、特にコードテスト環境だとあまり速くならず泣いてしまう *9 。

それでもいろいろ軽くしたり RE の原因をつぶしたりしてなんとか AC 。

正の得点を得ました！！！ pic.twitter.com/Q7PAdo5yza
— きり (@kiri8128) June 3, 2022

$35M$ でこの時点で 46 位。当初の予定だと $37.5M$ ぐらいは出て欲しかったけど、 TLE をなくすためにいろいろサボったのでまあやむなし。

さてここからどうするか。

7 日目（6/3 金）

－－－－－ここから余談－－－－－

頭痛・喉痛・鼻水に加えて、薬を飲んでるせいか常に眠気がひどく、現実と夢と AHC の世界が混じっているような感覚が一週間続いている。

イギリスの夢はゆうさんろんどんの影響？

頭痛がやばくて寝てました。謎な夢を見た。
— きり (@kiri8128) June 3, 2022

子供が「テキシコー」という、プログラミング的思考を学ぶ番組に興味を持ったみたいで、繰り返しみている。良い傾向。

ついでにこの前プレゼントであげた理論的思考力を鍛えるゲームにもハマっている模様。これも良い傾向。

人生ゲームを毎日させられるループから抜けられるか。

－－－－－余談終わり－－－－－

夢から覚めて、試してなかった Min Cost Flow を実装。前半パートを適当な時間まで試して一番良いものだけ後半パートをすることに。

後半の時間が読めないので時間をどうするか迷うけど、とりあえず $N$ ごとに適当な時間を決め打ちして、「ひとつ以上盤面があるかつ時間を超えている」場合に後半パートに移ることにした。

あと時間計測をして気付いたのは、後半パートの最後の 9 マスでかなり *10 時間がかかっている模様。

$A^{*}$ のパラメータをいじって高速化することに。

パラメータは近距離の調整と全体のファクターの 2 つ。通常時と最後の 9 マスに分けてパラメータ設定してみた。

DistanceAdjustment は大きいほど正確になるが遅くなる。通常は 2 、最後の 9 マスでは 1 にした。

全体のファクター HeuristicFactor は小さいほど正確で遅い。通常は $10 * (N - 5)$ 、最後の 9 マスでは 5 にした。通常時は $10\times 10$ の盤面をフルに使うような場合には最悪探索数が爆発する *11 ので大きめにしている。

$\max( \mathrm{ManhattanDistance} - \mathrm{DistanceAdjustment}, 0) * \mathrm{HeuristicFactor}$

8 日目（6/4 土）

割とやることがなくなってきた。

とりあえず 1 ループが結構でかくなってきたので、「ループが回って時間過ぎてたら終わる」だと途中で TLE に引っかかる可能性が高い。いろんなところに強制 EXIT を入れて、少なくとも 1 つ ANS を見つけている場合は時間が来たら途中で打ち切りみたいにした。これで TLE の不安はだいぶ減った。

あとアイデアとしては

全体で $A^{*}$ を雑にでもしてみる
そもそも前半ステップと後半ステップを完全に分離しているのでうまく融合する
$A^{*}$ のパラメータ調整
木の盤面に合わせるときの順番を一意に決めているので、逆回りなどいくつか試す

などがある。前後半の融合は今からだと厳しい。パラメータ調整はやれば多少上がるかもだけど長時間 Run する余裕がない（のとそもそもそういうプロセスができていない）、しかもあまり上がりそうにないのでパス。

「逆回り」は一度で二度試せてお得なのでこれを入れることに。あと結局最小費用流はやめて愚直に Score を計算する方針に変えた。もろもろやってみたが、 36M 台ぐらいでほぼ変わらず。

コードテストで見てみると、 $N$ が小さいときの方がループ回数が小さいという謎現象が起きていることに気付いた。特に前半ステップが遅そう。自由度が低すぎてうまくいかないのか。前半ステップは手抜き実装でやってるのでうまくやればもっと効率化できるんだけど今からだと厳しいか。

ぐぬぬー。いま $A^{*}$ を 2 マスずつやってるけど、 3 マスにしたら速くなったりしないかな・・・と思っていじってみると有意に上がりそう。投げたら 37.3M ！よしよし。

当然 4 マスならどうかと思って実験すると点数は 1 ～ 2 M 上がりそうだけど 5～8 秒かかるケースがあって TLE になりそう。

Python （ PyPy ）を使っている以上、スピード勝負に持ち込むと不利なのは分かってるのでなるべく別路線で行きたいけど、今回はスピード勝負にならざるを得ない感じか、ということに今更気付いてきた。まあしょうがない。

その後細かい調整などで約 37.5M （37,497,152 点）が出た。結果的にこれがプレテスト最高得点になった。

あと公開されている seed=0 を結果の盤面も見てみた。

この時点で一番良さそうだったツカモさんの盤面が、幸い（左右逆だけど）端っこに空マスがあるので、前半部分をこれで丸コピして、後半部分を自分のロジックでやってみて何点取れるかやってみた。結果は 76 万点ぐらいで、全部自分の方法でやったのとそんなに変わんない感じ。うーん。

Sliding Tree Puzzleのseed=0で878472点を獲得!!!https://t.co/z5T8lhW6Hc #AHC011 #visualizer pic.twitter.com/CadpleNqac
— ツカモ (@tsukammo) June 3, 2022

最終日 9 日目（6/5 土）

何度か出し直したけど特に変更してない。

最終的なアルゴリズムはこんな感じ。

ランダムに木の盤面を作る
「一本マス」と「コの字型」を回転させて、入力盤面とパネルの集合が一致して、かつ最後の 9 マスに重複を含む木盤面を探す
入力盤面から木盤面への path を $A^{*}$ で 3 マスずつ決める（ただし最後は 9 マス一気に決める）
最大スコアなら Ans を書き換える
逆回りで 3. 4. をやりなおす
1. ～ 5. を時間いっぱい回す

$A^{*}$ のヒューリスティック関数は下の形で、

$\max( \mathrm{ManhattanDistance} - \mathrm{DistanceAdjustment}, 0) * \mathrm{HeuristicFactor}$

3 マスのとき： $\mathrm{DistanceAdjustment}$ は 2 固定。 $\mathrm{HeuristicFactor}$ は使う盤面の広さ *12 に応じて 5 ～ 100 を段階的に適用

9 マスのとき： $\mathrm{DistanceAdjustment}$ は 1 、 $\mathrm{HeuristicFactor}$ は 5 でそれぞれ固定。

スコアを計算する回数は $N=6$ で 4 ～ 10 回程度（つまり上の 1. から 6. が 2 ～ 5 回まわる）、 $N=10$ では 1 ～ 4 回程度。特に前半ステップはばらつきが大きいので十分な回数回ってないイメージ。

最終提出のスコアは 37,307,105 点。最高得点 37.5M から若干下がってしまったけどまあ誤差の範囲か。

全体の感想

身近なゲームに類似の題材でとても面白かった。 $A^{*}$ も初めて書いたけど、実装が簡単なわりに便利で勉強になった。

前半ステップは「 $O(1)$ で変更できる」と思って喜んで採用したが、もう少し効率が良い方法がある気がする。

時間勝負になると追い込みが苦しい。手元の実行環境も生 Python なのでたくさん回して実験などがしづらい（今回はしなかった）。 AHC は PyPy にこだわらず言語を変えるのもひとつの手だが。

上位陣の点数すごいので勉強したい。

*1:全部ばらばらの場合は全パターンのちょうど半分が到達可能

*2:この操作で木であることが崩れない。「コ」の字の場所を見つけたあとは $O(1)$ で処理できる

*3:手元実行は生 Python なのでめちゃくちゃ遅いけど、実際の提出だと PyPy なのできっとそこそこ速くなって間に合うかも？まあだめならいくらでも高速化できるはず（？）

*4:「けいせん」で変換すると出てくるやつ。 1 本だけのものは良い罫線文字が見つからなかったので矢印で代用した。 1 本は慣れないとつながりが見づらいかもしれないけど、私の解法だと重要（「回転」できる）なのでこれはこれで見やすい

*5:後述のとおりパラメータはあとで可変にした

*6:ちゃんと判定するのめんどくさそう

*7:枚数と確率はそいろいろ変えた

*8:本当は $O(1)$ でできるけど定数倍激重なので手間の割に影響ほぼないかむしろ遅くなりそうなのでサボった。

*9:PyPy だとランダムアクセスが遅いのが効いてるのか・・・？

*10:コードテストで 1 秒とか、いくつか試した最悪ケースだと 2.5 秒以上かかっているものも

*11:と言っても 2 マス探索だと $O(N^6)$ ぐらい

*12: $N^{2}$ ではなく、関係するパネルを含む最小長方形の広さ