はじめに

　コンテスト後にXを見ているとビームサーチで解いている人が多数見られましたが工夫すると焼きなましでも本番19位相当のスコアが出ます（http://atcoder.jp/contests/ahc073/submissions/80100863 ）．

　なお，私は後述するDPの高速化がコンテスト中にできなかったため，終了後に生成AIを用いて実装して提出しています．

1. なぜ焼こうと思ったか

　まず，各目的地へ到達するための操作数が最小になるように，歩行と転移を選ぶ貪欲法を考えます．しかし，転移に使った魔法陣は消え，転移元に新しい魔法陣が残るため，現在の選択が将来の移動コストにも影響します．今の区間では少し遠回りをしてでも，後で使いやすい位置に魔法陣を残した方がよい場合があります．

　貪欲法の自然な拡張としては，複数の候補を残しながら前から構築するビームサーチが考えられます．ただし，現在までの操作数だけで候補を比較すると，序盤にコストを払って，将来の移動を安くする候補を途中で捨ててしまう可能性があります．

　これを避けるには，途中状態に残っている魔法陣が，今後どれほど役立つかを評価する必要があります．ところが，その価値は，残りの目的地だけでなく，どの魔法陣をどの順番で使い，どこに残していくかにも依存します．ビームサーチで先を見越した候補選択を行うには，将来コストの評価関数や先読みに工夫が必要そうです．

　一方，この問題では，すべての目的地が最初から分かっています．最後まで到達する計画を1つ持っていれば，その一部を変更した結果を，最後の目的地までの総操作数で直接評価できます．ある変更が直後の移動を悪化させても，後の移動でそれ以上に得をするなら，その効果を評価値に反映できます．

　そこで，貪欲法で完成した計画を作り，過去の選択も変更しながら全体を改善する焼きなまし法を使うことにしました．途中状態の将来性を見積もる評価関数を設計するよりも，完成した計画の評価を高速に計算する方針です．

　この方針を実現するために，次章では焼きなましの状態を「いつ，どの魔法陣を使うか」に絞ります．座標の調整をDPに任せることで，転移計画の変更に対して，将来への影響を含めた評価値を高速に求めます．

2. 焼くための工夫：座標を状態に持たない

　初期位置を \(p_0=s\)，目的地を \(p_{i+1}=g_i\) とし，\(p_i\) から \(p_{i+1}\) への移動を区間 \(i\) と呼びます．

　本来は1区間で何回でも転移できますが，本解法では，各区間での転移を高々1回に制限します．その上で，魔法陣に \(0,\ldots,K-1\) の番号を付け，長さ \(M\) の配列

\[ c_i\in\{-1,0,\ldots,K-1\} \]

を焼きなましの状態とします．

• \(c_i=-1\)：区間 \(i\) は歩行のみで移動する．
• \(c_i=k\)：区間 \(i\) で魔法陣 \(k\) を1回使う．

　魔法陣を使用すると，その魔法陣は消え，転移元に新しい魔法陣が残ります．この新しい魔法陣に同じ番号を引き継がせることにします．

　この状態には，魔法陣の初期座標も，転移元の座標も持たせていません．焼きなますのは「いつ，どの魔法陣を使うか」だけとし，座標はDPで最適化します．

3. DPの定義

3.1. 魔法陣ごと，座標軸ごとに分解する

　転移計画 \(c\) を固定すると，魔法陣 \(k\) の位置を変える操作は，魔法陣 \(k\) を使う転移だけです．また，各区間の始点と終点は目的地によって固定されています．したがって，異なる魔法陣を使う区間の座標は，それぞれ独立に最適化できます．

　さらに，歩行距離はマンハッタン距離なので，縦方向と横方向の距離の和です．反転の式と盤内に収まる条件も，各座標軸で独立しています．よって，各魔法陣について縦横を別々に最適化できます．

　以下では，ある1つの魔法陣と，ある1つの座標軸だけを考えます．

　その魔法陣を使う区間を時系列順に並べ，利用回数を \(L\) とします．\(j\) 回目に利用する区間の始点・終点の座標を，それぞれ \(u_j,v_j\) とします．

3.2. 「使った後の魔法陣の座標」を状態にする

　転移直前の魔法陣の座標を \(a\)，転移元の座標を \(x\) とすると，転移先は

\[ 2a-x \]

です．また，転移後には魔法陣が \(x\) に残ります．したがって，この区間の歩行コストは

\[ |x-u_j|+|2a-x-v_j| \]

です．

　そこで，\(D_j[x]\) を，\(j\) 回目の利用後に魔法陣の座標が \(x\) となるときの，それまでの利用区間の最小歩行コストと定義します．ここでは，対象の座標軸に沿った歩行だけを数え，転移そのものの操作回数は含めません．

　魔法陣の初期位置は自由に決められるので，初期値は

\[ D_0[a]=0 \qquad (0\le a<N) \]

です．遷移は

\[ D_j[x] = |x-u_j| + \min_{\substack{0\le a<N\\0\le 2a-x<N}} \left( D_{j-1}[a]+|2a-x-v_j| \right) \]

となります．

　条件 \(0\le 2a-x<N\) は，転移先が盤内にあるための条件です．最後に残る魔法陣の位置には制約がないため，この軸の最適値は

\[ \min_{0\le x<N}D_L[x] \]

です．

3.3. 状態全体の評価値

　魔法陣 \(k\) の利用回数を \(L_k\) とします．その魔法陣を使う区間の最小操作数は，

\[ L_k + \min_x D^{(k,\text{縦})}_{L_k}[x] + \min_x D^{(k,\text{横})}_{L_k}[x] \]

です．転移1回のコストは1なので，\(L_k\) は縦横の合計に対して1回だけ加えます．

　これを全魔法陣について合計し，転移を使わない区間のマンハッタン距離を加えれば，状態 \(c\) の評価値になります．

\[ F(c) = \sum_{i:c_i=-1}\|p_{i+1}-p_i\|_1 + \sum_{k=0}^{K-1} \left( L_k + \min_x D^{(k,\text{縦})}_{L_k}[x] + \min_x D^{(k,\text{横})}_{L_k}[x] \right). \]

　各遷移で最小値を与えた直前の座標 \(a\) を記録すれば，逆向きにたどることで，魔法陣の初期位置とすべての転移元を復元できます．

4. DPの高速化と差分計算

4.1. 単調キューによる \(O(N)\) 遷移

　上の遷移で，\(x\) ごとに直前の座標 \(a\) を全探索すると，1回の利用につき \(O(N^2)\) かかります．全体では \(O(N^2M)\) となり，焼きなましの評価として繰り返すには重いです．そこで，絶対値の中身の符号で場合分けします．

　転移先が盤内にある条件より，\(a\) の範囲は

\[ \ell_x=\left\lceil\frac{x}{2}\right\rceil, \qquad r_x=\left\lfloor\frac{x+N-1}{2}\right\rfloor \]

を用いて，\(\ell_x\le a\le r_x\) と書けます．また，\(w=x+v_j\) と置くと，

\[ |2a-x-v_j|=|2a-w| \]

なので，遷移は

\[ D_j[x] = |x-u_j| + \min\left\{ \begin{aligned} &w+ \min_{\ell_x\le a\le\lfloor w/2\rfloor} \left(D_{j-1}[a]-2a\right),\\ &-w+ \min_{\lceil w/2\rceil\le a\le r_x} \left(D_{j-1}[a]+2a\right) \end{aligned} \right\} \]

となります．空区間の最小値は \(+\infty\) とします．

　つまり，次の2種類の区間最小値を求めればよいことになります．

• 配列 \(D_{j-1}[a]-2a\) の区間最小値．
• 配列 \(D_{j-1}[a]+2a\) の区間最小値．

\(x\) を \(0\) から \(N-1\) まで増やすと，どちらの区間も左端・右端が単調に増加します．そのため，それぞれの最小値を単調キューで管理できます．

　具体的には，右端を伸ばす際に新しい要素を追加し，その要素以上の値を持つ末尾の要素を取り除きます．左端より古くなった添字を先頭から取り除けば，先頭の要素が現在の区間の最小値になります．

　各添字が追加・削除される回数は高々1回なので，1回のDP遷移は \(O(N)\) です．全魔法陣の利用回数の合計は高々 \(M\) であるため，状態全体を \(O(NM)\) で厳密に評価できます．

4.2. 変更された魔法陣だけ再計算する

　例えば，ある区間の選択を魔法陣 \(0\) から魔法陣 \(1\) に変更した場合，利用区間の列が変化するのは，この2つの魔法陣だけです．それ以外の魔法陣のDPと評価値は再利用できます．

　転移なしから魔法陣 \(0\) への変更なら，再計算が必要な魔法陣は \(0\) だけです．歩行のみの区間のコストは，別途評価値へ反映します．

4.3. 変更前のDPも再利用する

　同じ魔法陣についても，利用区間の列の先頭が変わっていなければ，その部分のDPを再利用できます．

　例えば，ある魔法陣の利用区間が

\[ (1,4,7,12)\longrightarrow(1,4,9,12) \]

と変化した場合，最初の2回の利用までは共通しています．そのため，区間 \(4\) の処理後のDP配列を保存しておけば，区間 \(9\) と区間 \(12\) の分だけ計算し直せばよいです．

　区間 \(12\) の番号自体は変わっていませんが，そこに渡されるDP配列が変わるため，区間 \(12\) も再計算の対象になります．このように，再計算する範囲は，変更位置以降の同じ魔法陣の利用列です．

　実装では，魔法陣ごとに利用区間の列と各利用後のDP配列を保存します．近傍を適用したら，変更前後の列の最長共通接頭辞を求め，その直後から末尾まで再計算します．近傍を受理した場合だけ，保存しているDPを更新します．

　再計算する利用回数の合計を \(r\) とすると，DP部分の計算量は \(O(Nr)\) です．最悪計算量は \(O(NM)\) のままですが，影響を受けない魔法陣や，変更より前の計算を省略できます．

5. 近傍について

　以下の4種類の近傍を使用しました．

5.1. 1区間の選択を変更する

　区間 \(i\) を1つ選び，\(c_i\) を現在とは異なる値に変更します． この近傍で，転移の追加・削除・使用する魔法陣の変更を行います．最も基本的な近傍で，これだけでも任意の状態に到達できます．

5.2. 近い2区間の選択を交換する

　近い位置にある2区間 \(i,j\) を選び，\(c_i,c_j\) を交換します．実装では，距離8以内の区間を選びます．

　一方が転移なしなら，転移を使うタイミングを前後に移動する近傍になります．両方が異なる魔法陣なら，近接する2回の転移の担当を入れ替える近傍になります．

　1区間ずつ変更すると途中の状態が悪くなるような変更でも，交換によってまとめて試すことができます．

5.3. 任意の2区間の選択を交換する

　距離の制限を設けずに2区間を選び，選択を交換します．近い区間の交換では届きにくい，大きなタイミングの変更を試すための近傍です．

5.4. 部分区間で2種類の魔法陣番号を交換する

　短い連続区間と，異なる2つの魔法陣番号 \(a,b\) を選びます．その区間内だけ，\(a\) を \(b\) に，\(b\) を \(a\) に置き換えます．転移なしの区間は変更しません．

　この近傍では，2つの魔法陣の利用列の一部分をまとめて交換できます．それに合わせて，関連する転移元や初期位置もDPによって最適化されます．

　なお，全区間で番号を交換すると，単なる魔法陣の名前の変更になり，評価値は変わりません．部分区間に限定することで，前後の利用列とのつながりを変更します．

　実装での選択確率は次の通りです．

近傍	選択確率
1区間の選択変更	55%
近い2区間の交換	25%
任意の2区間の交換	10%
部分区間での魔法陣番号の交換	10%