AHC062「King’s Tour」解法解説 – それでもロケットは回っている

感想

参加が遅れて２時間半くらいしか使えなかったにも関わらず、過去最高の125位を取れた。ぱっと見た感じ、焼きなまし的な方法が強そうだったが、ただ往復するだけの簡単な貪欲法が思いついたので提出してみたら、実行時間は短いし（24ms）意外と強かったので、解説記事を作成。といっても、問題ページと提出コードをClaudeに渡して殆ど書いてもらったもの。なお、コード作成時は一切AIに質問していない。詳しく書いてあるが、図だけ見ても何やっているか分かると思う。

問題概要

問題のページ：https://atcoder.jp/contests/ahc062/tasks/ahc062_a

$N \times N$ （ $N = 200$ ）のグリッドが与えられる。各マス $(i, j)$ には住民数 $A_{i,j}$ （ $1$ 以上 $N^2$ 以下の整数が重複なくランダムに配置）が存在する。

全マスをちょうど一度ずつ訪問するハミルトンパスを構築し、以下のスコアを最大化する。 $\sum_{k=0}^{N^2-1} k \cdot A_{i_k, j_k}$ 移動は縦・横・斜めの 8 方向（チェビシェフ距離 1）が許される。

解法の方針

提出コード：https://atcoder.jp/contests/ahc062/submissions/74066996

スコアを最大化するためには、住民数が多いマスほど後（大きい k）に訪問する ことが重要。

理想を言えば全マスを住民数の昇順に訪問できれば良いが、隣接制約があるため任意の順序では訪問できない。そこで、以下の 2 ステップのアプローチを取る。

構造的なパスを構築：隣接するマスのペアが「連続して」訪問されるような特殊なジグザグパスを作る
局所スワップ最適化：各ペアの中で住民数が大きい方を後に訪問するよう交換する

ステップ1：パスの構築

全体の構造

パスは大きく 2 フェーズに分かれる。

フェーズ1: グリッドの左端から右端方向へ
フェーズ2: グリッドの右端から左端方向へ

$N = 200$ のとき n/4 = 50 回のループで各フェーズを実行する。
下の図は見やすいように、N=20の場合の図である。

フェーズ1の詳細（偶数列を処理）

(0,0) → 出発点

各イテレーションで以下を繰り返す（nj は偶数列 0, 4, 8, ...）:
  1. 列 nj を上から下へ縦断: (1,nj) → (2,nj) → ... → (n-1, nj)
  2. 斜め移動: (n-1, nj) → (n-1, nj+1)  ← 奇数列1マスのみ訪問
  3. 列 nj+2 を下から上へ縦断: (n-2, nj+2) → ... → (0, nj+2)
  4. 斜め移動: (0, nj+2) → (0, nj+3)   ← 奇数列1マスのみ訪問
  → nj += 4 して次のイテレーションへ

このフェーズで偶数列 $\{0, 2, 4, \ldots, 198\}$ をほぼ全訪問し、奇数列は各列の上端または下端の 1 マスのみを通過する。

フェーズ2の詳細（奇数列を処理）

フェーズ1終了後、今度は右から左方向へ同様のパターンで奇数列を縦断する。

各イテレーションで以下を繰り返す（nj は奇数列 199, 195, 191, ...）:
  1. 列 nj を上から下へ縦断
  2. 斜め移動（偶数列の1マス）
  3. 列 nj-2 を下から上へ縦断
  4. 斜め移動（偶数列の1マス）
  → nj -= 4 して次のイテレーションへ

このままだと、最後に原点に戻って重複してしまうので、 ans.pop_back() で余分な 1 要素を削除。
これでちょうど $N^2 = 40000$ マスのパスが完成する。

ステップ2：局所スワップ最適化

パスを構築した後、隣接する列ペア $(0,1),\ (2,3),\ (4,5),\ \ldots$ に対して局所的なスワップを行う。
一例として0000.txtのサンプルの場合、以下のようになる。

スワップのロジック

rep(j, n/2) {
    ll k = 2*j;           // k = 0, 2, 4, ..., 198
    rep2(i, 2, n-2) {    // 行 i = 2 から n-3 まで
        ll left  = mp[P(i, k)];    // (i, k) の訪問順
        ll right = mp[P(i, k+1)];  // (i, k+1) の訪問順
        if (a[i][k] > a[i][k+1])
            swap(ans[left], ans[right]);
    }
}

スワップの意味

パスの構造上、列 $k$ と列 $k+1$ の同一行 $i$ のマスは 訪問順が隣接している（= パス上で隣り合っている）ように設計されている。そのため、行 2〜 $N-3$ の範囲なら、この2つのマスはパスの連続性を壊さずに入れ替え可能となる。

スワップの条件 a[i][k] > a[i][k+1] は：

左の列の住民数 > 右の列の住民数 → 交換
これにより、住民数が大きいマスを後（大きい k）に訪問 できる

スワップが有効な理由

パスの構造から、行 $i$ （ $2 \leq i \leq N-3$ ）において、列 $k$ と列 $k+1$ のマスは次のような関係になっている：

... → (i-1, k) → (i, k) → (i, k+1) → (i+1, k+1) → ...
         ↑前の訪問                     ↑次の訪問

または逆順でも同様。このとき $(i, k)$ と $(i, k+1)$ を入れ替えても：

$(i-1, k)$ から $(i, k+1)$ への移動は斜め隣接なので有効（チェビシェフ距離1）
$(i, k+1)$ から $(i, k)$ への移動も斜め隣接なので有効
$(i, k)$ から $(i+1, k+1)$ への移動も斜め隣接なので有効

よって、スワップ後もパスの隣接制約が保たれる。

全体フロー

入力読み込み
    ↓
構造的なハミルトンパスを構築
（フェーズ1: 左→右、偶数列を縦断）
（フェーズ2: 右→左、奇数列を縦断）
    ↓
各マスの訪問順を記録したマップ mp を構築
    ↓
列ペア (0,1), (2,3), ..., (198,199) の各行で
住民数の多いマスが後に来るようスワップ
    ↓
結果を出力

計算量

フェーズ	計算量
パス構築	$O(N^2)$
マップ構築	$O(N^2 \log N)$
スワップ最適化	$O(N^2)$
合計	$O(N^2 \log N)$

考察・改善の余地

本解法はシンプルな構造化パス＋局所スワップのみを行っている。スコアをさらに向上させる可能性がある改善案として：

より広い範囲の局所スワップ：行方向（同一列の隣接行）のスワップも検討
焼きなまし法（Simulated Annealing）：2-opt や Or-opt 的な操作でパス全体を改善
貪欲法によるパス再構築：住民数上位のマスから優先的に訪問時刻を割り当てる構築
ビームサーチ：複数の候補パスを維持しながら構築

今回の解法は実装が非常にシンプルながら、構造的なパスと局所最適化の組み合わせにより実用的なスコアを達成している。