概要

この問題は、2次元平面上の \(N\) 個の地点をすべて一度ずつ巡回して戻ってくる際の、合計燃料コスト（移動距離の2乗の和）を最小化する問題です。これはグラフ理論における「巡回セールスマン問題 (TSP)」と呼ばれる有名な問題の1つです。

考察

素朴なアプローチ

すべての地点の訪問順序を全探索することを考えます。地点1（配送センター）からスタートし、残りの \(N-1\) 個の地点を並べる方法は \((N-1)!\) 通りあります。 \(N=16\) の場合、\((16-1)! = 15! \approx 1.3 \times 10^{12}\) となり、制限時間内に計算を終えることは不可能です。

効率的な解法への手がかり

巡回ルートを決定する際、ある時点で重要な情報は以下の2点だけです。 1. すでにどの地点を訪問したか 2. 今どの地点にいるか

次にどの地点へ向かうかを決める際、「どのような順番でこれまでの地点を回ってきたか」という詳細な経路は、それ以降の最小コストには影響しません。この性質を利用して、動的計画法 (DP) を適用します。

訪問済みの地点の集合をビット列で表す「ビット集合（bitset）」を用いることで、効率的に状態を管理できます。

アルゴリズム

ビットDP (Bitmask DP)

以下の状態を定義します。

• dp[mask][i]：集合 mask に含まれる地点をすべて訪問済みで、現在地点 i にいるときのコストの最小値。

ここで mask は、\(N\) 個の地点のうち訪問済みの地点のインデックスに対応するビットが 1 になっている整数です（例：地点0と2を訪問済みなら mask は \(2^0 + 2^2 = 5\)）。

1. 初期化

地点1（インデックス0）からスタートするため、地点0のみを訪問した状態を 0 とします。 - dp[1][0] = 0 - それ以外の dp の値は無限大 (\(\infty\)) で初期化

2. 遷移

現在の状態 dp[mask][i] から、まだ訪問していない地点 j へ移動する場合： - dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][i] + dist(i, j)) ※ dist(i, j) は地点 i と j の間の燃料コスト \((X_i - X_j)^2 + (Y_i - Y_j)^2\) です。

3. 最終結果

すべての地点を訪問した状態は mask = (1 << N) - 1 です。最後は地点1（インデックス0）に戻る必要があるため、以下の最小値が答えとなります。 - \(\min_{i=1}^{N-1} (dp[(1 \ll N) - 1][i] + dist(i, 0))\)

計算量

• 時間計算量: \(O(2^N \cdot N^2)\)
  • 状態数が \(2^N \cdot N\) 個あり、各状態からの遷移（次の地点 j の探索）に \(O(N)\) かかります。
  • \(N=16\) のとき \(2^{16} \cdot 16^2 \approx 1.6 \times 10^7\) となり、Pythonでも十分に間に合う計算量です。
• 空間計算量: \(O(2^N \cdot N)\)
  • DPテーブルの大きさに依存します。

実装のポイント

1. 距離の事前計算: 2地点間のコストを計算する際、ループの中で何度も同じ計算をしないよう、あらかじめ dist[i][j] として二次元配列に保存しておくと高速です。

2. ビット演算: mask & (1 << i) で地点 i が訪問済みか判定したり、mask | (1 << i) で訪問済みに更新したりする操作をスムーズに行います。

3. ループの順序: mask の値が小さい順にループを回すことで、遷移元の値が必ず計算済みの状態になるようにします。今回のコードでは range(3, 1 << N, 2) とすることで、地点0（1番目のビット）が必ず含まれる奇数の mask のみを効率的に探索しています。

   ソースコード

import sys

def solve():
    # Read all input at once for speed
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Parse N
    N = int(input_data[0])
    
    # Parse coordinates
    coords = []
    for i in range(N):
        coords.append((int(input_data[1 + 2*i]), int(input_data[2 + 2*i])))
    
    # Precompute squared Euclidean distances between all pairs of points
    dist = [[0] * N for _ in range(N)]
    for i in range(N):
        xi, yi = coords[i]
        for j in range(i + 1, N):
            xj, yj = coords[j]
            d2 = (xi - xj)**2 + (yi - yj)**2
            dist[i][j] = dist[j][i] = d2
    
    # DP table: dp[mask][i] is the minimum cost to visit points in 'mask' ending at point index 'i'.
    # Point 1 is at index 0.
    # N = 20 means 2^20 * 20 elements. 10**15 is used as infinity.
    inf = 10**15
    dp = [[inf] * N for _ in range(1 << N)]
    
    # Base case: start at point index 0, having visited only that point.
    dp[1][0] = 0
    
    # Iterate through all possible masks that include the starting point (bit 0 is set).
    # We start from mask 3 (binary 00...011) because mask 1 is the base case.
    for mask in range(3, 1 << N, 2):
        # Pre-extract indices of set bits in the current mask to speed up inner loops.
        set_bits = [i for i in range(N) if (mask & (1 << i))]
        
        # Try each point i in the current mask as the last visited point.
        for i in set_bits:
            if i == 0:
                continue
            
            # prev_mask represents the set of points visited before point i.
            prev_mask = mask ^ (1 << i)
            dp_prev = dp[prev_mask]
            dist_i = dist[i]
            
            # Find the minimum cost to reach point i from any possible previous point j.
            m = inf
            for j in set_bits:
                # dp_prev[j] is the cost to visit points in prev_mask ending at j.
                # If j is not in prev_mask or cannot be an end-point, dp_prev[j] is inf.
                d = dp_prev[j] + dist_i[j]
                if d < m:
                    m = d
            dp[mask][i] = m
    
    # The final answer is the minimum cost to visit all N points and return to point index 0.
    full_mask = (1 << N) - 1
    ans = inf
    dp_full = dp[full_mask]
    dist_0 = dist[0]
    for i in range(1, N):
        res = dp_full[i] + dist_0[i]
        if res < ans:
            ans = res
    
    # Output the result
    print(ans)

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-thinking によって生成されました。