(2025/01/21 23:30 遷移のvisualizeについて追記しました。)
高さを状態として焼きなます解法について紹介します。
コンテストで問題を読んだ時の考察
部分木の親を付け替えたり、木を回転させたりするのが強そうだと思いました。
親の付け替えはAHC037の自分の解法に登場していたりします。解説放送も参考になります。
木の回転 - Wikipedia 本来の問題を特殊化した次の問題「木に用いる辺を固定した時に、どの頂点を値にするべきか」を決定的に解こうとすると全方位木DPがしたくなりました。木の回転で根を焼きなませば、全方位木DPをした気分になれるのでは、という考察から木の回転をするべきだと思いました。
ただしこの時は、木構造を直接状態にするのは筋が悪いように感じました。遷移時の高さチェックがかなり重そうに感じたためです。
実は実装を頑張るとこちらの方が点数が出るようです。今回の解説放送を見ましょう。
「ある頂点を高さ1にしたい」→「根が隣にあれば良い」=「高さ0が隣にあれば良い」という考察をして、高さを状態にできることに気がつきました。
焼きなましの状態の持ち方と復元
各頂点iの高さh_iを状態として持ちます。
各頂点iについてh_i = 0 または h_i = h_j + 1となるような隣接点jが存在することが条件です。
h_i = 0の場合はiが根となり、h_i = h_j + 1はiの親をjにすることで解を復元できます。
焼きなましの遷移
ランダムな頂点iとその隣接点jを選び、h_iをh_j + 1に変化
ランダムな頂点iを選び、h_iを0に変化 (1とほぼ同じ)
ランダムな頂点iとその隣接点jを選び、h_iとh_jをswap
変化させる頂点の隣接点で、hが満たすべき条件が保持されているかをチェックする必要があります。高速化の工夫として、「頂点iの隣接点であって高さがxであるものは何個あるか」を持つ配列を遷移時に更新するようにすれば、条件のチェックを高速に行うことができます。その配列やhを書き換えることなくチェックすることができるため、それを実装することでも高速化できます。
(要復習: 多分これらは焼きなましの高速化典型で、解説放送の解法も同じような高速化を行っているはずです)
高速化によって、0000.txtについて遷移候補を30,807,873回試すことができているようです。
反省点
解の復元時に辺の方向を逆向きにしていて1時間くらい混乱していました。よくない。
Jirotechさんの解法がほぼ同じで自分より繊維の種類が多いです。隣接swapをバグらせていた時間が長く、他の遷移を実装する暇がありませんでした...。実装をテキパキやりましょう。
追記: なぜこの状態が上手くいったのか
自分でもこの状態の持ち方で遷移がうまくいく理由はわかりませんが、可視化してみると自分が思っていた以上に遷移先の候補があることがわかったので追記しておきます。
まず、焼きなまし開始1secの時の解を取り出して可視化してみました。
次に、遷移1の「h_iをh_j + 1に変化」してもよい(i, j)辺を可視化しました。ただし、h_i = h_j + 1の場合はスルーしています。青と赤がそれぞれ単一方向のみ可能、紫が両方可能です。
同様に、遷移3の「h_iとh_jをswap」してもよい(i, j)辺を赤色で可視化しました。ただしh_i = h_jはスルーしています。
変化する関係を見てみると、
10をやめて5になって新しい部分木を始められる遷移や
swapによって根が移動
10と9がswap
などの遷移があり、思っていた以上に柔軟に見えました。
2025/01/22 13:08 追記: 部分木の付け替えに対して遷移が下位互換なのはそうですが、「既存の葉を新しく他の木の葉に」「swapは根や葉の役割を交換する」というのがvisualizerで確認できると、部分木の付け替えよりDFSによる破壊再構築とやっていることが近い気がしました。
ちなみにvisualizerは元の解法のコードに次のようなコードを埋め込んで出力しています。下のコードは1枚目の画像を出力するために書きました。https://github.com/niuez/egui_visualizer 自作の汎用visualizerです。
