全体方針

本解法は以下の3章からなる．

1. 移動ベクトルの選択（ローカルで計算するので予算ゼロ）
2. 差分更新ビームサーチで初期解を構築（予算 1.2 s）
3. 厳密差分評価の焼きなまし + 区間 DP LNSで磨く（タイムリミットまで）

ビームサーチはPrussianBlue さんの解法を参考にしました． (https://atcoder.jp/contests/ahc070/submissions/78855323)

なお，延長戦では生成AIを使用しています．ここで解説する解法を生成AI禁止の4時間で実装することは難しいかもしれません．

---

1. 移動ベクトルの選択

1.1 位置は「ベクトル使用回数」だけで決まる

移動ベクトルを \(v_0,v_1,v_2\)，ターン \(t\) までの \(v_1,v_2\) の使用回数を \(c_1,c_2\) とすると，

\[ \mathrm{pos}(t)=(t+1)v_0+c_1(v_1-v_0)+c_2(v_2-v_0)\pmod N . \]

つまり位置は手順の順序に依存せず，使用回数のみで決まる．

1.2 極小三角形族

採用したのは

\[ v_0=(70,75),\quad v_1=(71,76),\quad v_2=(72,75). \]

差分は \(v_1-v_0=(1,1)\)，\(v_2-v_0=(2,0)\)．回転座標 \((i+j,\ i-j)\) で見ると 3 手は

\[ (145,-5),\quad(147,-5),\quad(147,-3) \]

となり，どの 2 手も高々 2 しか違わない．

毎手の「ドリフト速度」を回転座標の 2 軸それぞれで ±2 刻みに操舵できる．つまり \(k\) 手先の位置は基準軌道の周りを幅 \(O(k)\) で連続的に埋め，深い先読みがそのまま精密な位置調整として機能する．

一方で \((t+1)v_0\) の基準ドリフト自体は毎ターン大きく飛ぶため，盤面全体への到達性も保たれる．この「大きく回りながら微調整だけ選ぶ」構造が，ビーム・LNSと相性が良かった．

族の特定は，\(\mathrm{pos}(t)\) の格子としての性質で枝刈りしつつ 95,000 通りの三つ組を実測評価して行った．

---

2. 差分更新ビームサーチ

ベースは PrussianBlue さんの解法．

• 全 10000 ターンを 2 手ずつ（5000 レベル）進める幅 128〜320 のビームサーチ
• 各ノードが \(102\times102\) の「最寄りお札距離場」を保持し，お札設置を BFS 緩和で増分更新する厳密評価
• ノード評価 = 累積実コスト − 重み × 累積 gain（gain は距離が下がった各セルの生存確率モデル）
• 終端マスでの重複除去と親あたり子数上限で多様性を確保

本解はこれを差分更新ビームサーチにした．元解はノード生成のたびに距離場を memcpy 複製するため，1 走行あたり 557,048 回 × 10,404 B ＝ 5.8 GB の複製が発生し，メモリ帯域律速だった．観察は

ビーム木の生存辺は 1 レベルあたり 350〜1,100 本しかない

こと．そこで距離場は全体で 1 本だけ持ち，各ノードには BFS 緩和の \((\text{cell},d_{\mathrm{old}},d_{\mathrm{new}})\) undo ログのみを保存する．ノード間の移動は木上の LCA まで undo → 逆適用で行い，レベルごとに走査方向を反転して折り返しコストを消す．

これを実装すると1.6〜1.9 倍の高速化となり，そのままビーム幅に還元された．

---

3. 焼きなまし

3.1 全体像

• 状態は 10000 手の移動列そのもの
• 近傍は swap（90 %）/ 窓シャッフル（10 %）/ 250 イテレーションに 1 回の区間 DP LNS
• 棄却時は undo ログの逆再生で完全復元．最良解の同期は変更ターンだけを dirty リストで書き戻す

これを支えるのが以降の厳密差分評価器で，手元実測では 約 \(1.4\times10^7\) 反復を実現した．

3.2 厳密差分評価の帳簿

「移動列の一部を書き換えたときの \(\Delta D\)」を厳密かつ局所的に求めるため，次の構造を常に整合させて持つ．

• firstStamp[c] : セル \(c\) に最初にお札が立つターン．セルごとの先頭 4 訪問ターンを 16 bit × 4 でパックしたSIMD ソート済みリストで管理し（挿入・削除はベクトル比較 + popcount シフト），5 件以上はスピル配列に溢して最小値だけ昇格させる
• distTurn[t] / achieveCnt[t] : \(d_t\) と，その距離をちょうど達成しているお札の枚数
• cellRec / turnRec : セル ⇄（ターン, 距離）の相互パック．空間走査が 32 bit ロード 1 回で判定できる
• nzWord : \(d_t\ge1\) のターンの 64 bit ビットセット
• blockMax + 接尾辞 max / 接尾辞 popcount : 64 ターンブロック単位の \(\max d_t\) と非ゼロ数（走査コスト見積り用）
• maxCover[c] : セル \(c\) を中心とする半径 \(k\) のリングが，どこかのターンの達成距離になり得る \(k\) の上限（65,536 イテレーションごとに再構築）

更新の対称性が鍵で，

• お札の追加は距離が下がるターン（と同距離のカウント増）だけを触る
• お札の削除は achieveCnt が 0 になったターンだけ recomputeTurn でリングを \(k+1\) から外側へ再探索する（settledFlag で同一ターンの二重減算を防止．\(k=1,2\) は完全展開）

3.3 direct / ring の 2 走査戦略

差分適用で「影響を受けるターン」を列挙する方法を 2 つ持ち，毎回作業量見積りで安い方を選ぶ．

• direct : 時間範囲 \([t_0,t_1)\) の \(d_t\ge1\) ターンを nzWord で列挙し，変更セルとの距離を直接計算する．作業量 ≈ 範囲内の非ゼロターン数（接尾辞 popcount で \(O(1)\) 見積り）
• ring : 変更セルの半径 \(k_{\max}\) 以内を空間走査する．作業量 ≈ \(2(k_{\max}+1)^2\times\) 係数．\(k_{\max}\le24\) は事前計算した SIMD グループ表で 4 セル同時判定，\(k_{\max}\le4\) は完全展開

\(k_{\max}\) は区間 \(\max d_t\)（blockMax）と maxCover の両方で絞る．追加側はさらに時間範囲を 128/512/2048 で切った「前半 direct + 後半 ring」の混合案も比較する．局所変更 1 回の処理が影響範囲に比例するオーダーに収まり，反復数がそのまま桁で伸びた．

3.4 軽量な近傍

• swap : \(t_0\) と \(t_0+g\)（\(g=1/2/3\) を確率 \(0.5/0.3/0.2\)）の 2 手を交換．区間 \([t_0,t_0+g]\) の中間位置だけがずれる最小近傍
• 窓シャッフル : 長さ 3〜6 の窓を Fisher–Yates で並べ替え（8 バイト比較で無変化案は棄却）
• 狙い撃ち : \(d_t\ge1\) のターンを一様サンプルし，怪異の半径 \(\min(d_t,4)\) 内の目標マスを選ぶ．\(v_a\to v_b\) を怪異前に \(k\) 個・\(v_b\to v_a\) を怪異後に \(k\) 個（\(k\le3\)）交換する最短の窓を全 6 方向から探し，既存訪問を目標マスへ平行移動してお札を 1 枚寄せる

3.5 DP による LNS

250 イテレーションに 1 回，窓 \([l,r)\)（長さ 12〜26，一様）を丸ごと作り直す．

1. removeWindowStamps で窓内のお札を帳簿から一時除去する
2. 節 1.1 の格子構造より，窓内の使用回数を保存する並べ替え全体を「使用済み \(v_1\) 数 \(q_1\) × 使用済み \(v_2\) 数 \(q_2\)」を状態とする DP で厳密に走査できる．終端位置の一致は自動で保たれ，遷移は各ステップ 3 種のみ
3. DP のコストは \(\min(\lVert\mathrm{pos}_k-e_{l+k}\rVert_1,\ \mathrm{refDist}_{l+k})\cdot\sqrt{l+k+1}\)（\(\mathrm{refDist}\) = 窓除去後の参照距離）から次節の将来価値を引いたもの
4. DP 解を挿入し，厳密差分で出た本物の \(\Delta\) で採否を判定する（\(\Delta\le0\) は必ず受理，それ以外は温度スケール付き閾値受理）

DP は窓内お札同士の相互寄与を無視した近似だが，採否は常に厳密値で行うため安全．窓は \(l\ge1\) が前提で，\(l=0\) だと区間 \([0,r)\) を覆うお札が消え「各ターンは常に何かのお札に覆われている」という帳簿の不変条件が壊れる．

3.6 将来価値場 — 窓の外を目的関数に入れる

この LNS の本体は窓内ではなく窓の外にある．

窓のお札を抜いた瞬間の distTurn は，そのまま「窓を無視したときの参照距離 \(\mathrm{refDist}_t\)」になっている（再シミュレーション不要）．そこから将来価値場

\[ V[c]=\sum_{t\ge r}\max\!\left(0,\ \min(\mathrm{refDist}_t,6)-\lVert c-e_t\rVert_1\right)\sqrt{t+1} \]

を作り，DP の目的関数を

\[ \text{窓内実コスト}-0.8\sum_k V[\mathrm{pos}_k] \]

とする．窓内の各お札が，窓より先のターンをどれだけ救うかを 1 マス単位で評価していることになる．

窓内だけを最適化すると全く採用されず壊滅的に悪化した． つまり LNS の性能はほぼこの将来項で決まっていた．

3.7 将来価値場のチェックポイント化

\(V\) を毎回 \(t\ge r\) の全ターンから散布し直すと LNS 1 回が重すぎる．そこで

• 512 ターン刻みの接尾辞スナップショット \(\mathrm{ck}[j]=\sum_{t\ge512j}(\cdots)\) を 20 本保持し，16,384 イテレーションごとに再構築する
• LNS ごとには (a) \(r\) からスナップショット境界までの残差ターンの散布と，(b) 窓除去でログに載ったターンについてスナップショット時距離との差分だけの再散布を行う

散布で触れたセルのみを記録してゼロクリアも差分化し，\(V\) の構築が窓近傍のコストに収まる．