概要

家 \(1\) から出発して \(N\) 軒すべての家を1回ずつ訪問する順番を決め、移動コストの合計を最小化する問題です。\(N \leq 20\) という制約から、ビットマスクDPで解きます。

考察

問題の本質

この問題は、家 \(1\) を始点とし、すべての家をちょうど1回ずつ訪問する最小コストのハミルトンパスを求める問題です。

素朴なアプローチ

すべての訪問順序を列挙すると \((N-1)!\) 通りあります。\(N = 20\) のとき \((N-1)! = 19! \approx 1.2 \times 10^{17}\) となり、到底間に合いません。

重要な気づき

訪問順序を決めるとき、次にどの家に行くかを判断するために必要な情報は、

• 現在どの家にいるか（次の移動コストを計算するため）
• どの家をすでに訪問済みか（未訪問の家にしか行けないため）

の2つだけです。訪問した順番の詳細は不要です。この性質を利用し、訪問済みの集合をビットマスクで表現するDPが使えます。

アルゴリズム

ビットマスクDP（巡回セールスマン問題型DP） を用います。

状態の定義

\[dp[\text{mask}][u] = \text{訪問済みの家の集合が mask で、現在家 } u \text{ にいるときの最小コスト}\]

ここで \(\text{mask}\) は \(N\) ビットの整数で、第 \(i\) ビットが立っていれば家 \(i\)（0-indexed）が訪問済みであることを表します。

初期状態

家 \(1\)（0-indexed で家 \(0\)）からスタートするので：

\[dp[1][0] = 0\]

（ビットマスク \(1 = 0\text{b}0\ldots01\) は家 \(0\) だけが訪問済みの状態）

遷移

状態 \(dp[\text{mask}][u]\) から、まだ訪問していない家 \(v\)（\(\text{mask}\) の第 \(v\) ビットが \(0\)）へ移動します：

\[dp[\text{mask} \mid (1 \ll v)][v] = \min\left(dp[\text{mask} \mid (1 \ll v)][v],\; dp[\text{mask}][u] + |V_u - V_v| \times |u - v|\right)\]

答え

全ての家を訪問した状態（\(\text{mask} = 2^N - 1\)）において、最後にいる家は任意でよいので：

\[\text{答え} = \min_{u=0}^{N-1} dp[2^N - 1][u]\]

具体例（\(N = 3\), \(V = [10, 30, 20]\)）

• 初期: \(dp[\text{001}][0] = 0\)（家0にいる）
• 家0→家1: コスト \(|10-30| \times |0-1| = 20\)、\(dp[\text{011}][1] = 20\)
• 家0→家2: コスト \(|10-20| \times |0-2| = 20\)、\(dp[\text{101}][2] = 20\)
• 家1→家2: コスト \(|30-20| \times |1-2| = 10\)、\(dp[\text{111}][2] = 30\)
• 家2→家1: コスト \(|20-30| \times |2-1| = 10\)、\(dp[\text{111}][1] = 30\)
• 答え: \(\min(30, 30) = 30\)

計算量

• 時間計算量: \(O(2^N \times N^2)\) — 各状態（\(2^N \times N\) 通り）から未訪問の各家（最大 \(N\) 個）への遷移を試みる
• 空間計算量: \(O(2^N \times N)\) — DPテーブルのサイズ

\(N = 20\) のとき、\(2^{20} \times 20^2 \approx 4.2 \times 10^8\) 程度の操作量になります。

実装のポイント

• コストの事前計算: \(\text{cost}[i][j]\) を事前に計算しておくことで、遷移時の計算を高速化しています。

• ビット演算による未訪問頂点の列挙: bits & -bits で最下位ビットを取り出し、bits &= bits - 1 で除去するテクニックにより、未訪問の家だけを効率的に列挙しています。これにより無駄なループを回避します。

• 枝刈り: dp[mask][u] == INF や mask に \(u\) が含まれないケースを早期にスキップすることで、不要な計算を省いています。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    V = [int(input_data[i+1]) for i in range(N)]
    
    if N == 1:
        print(0)
        return
    
    # Precompute costs
    cost = [[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            cost[i][j] = abs(V[i] - V[j]) * abs(i - j)
    
    # Bitmask DP
    # dp[mask][i] = minimum cost to have visited exactly the houses in mask,
    #               currently at house i
    # Start: mask has bit 0 set, current house is 0
    
    INF = float('inf')
    full = 1 << N
    dp = [[INF]*N for _ in range(full)]
    dp[1][0] = 0  # visited house 0 (1-indexed house 1), at house 0
    
    for mask in range(1, full):
        for u in range(N):
            if dp[mask][u] == INF:
                continue
            if not (mask & (1 << u)):
                continue
            # Try to visit next unvisited house
            remaining = full - 1 - mask  # bits not in mask
            bits = remaining
            while bits:
                v = (bits & -bits).bit_length() - 1
                new_mask = mask | (1 << v)
                new_cost = dp[mask][u] + cost[u][v]
                if new_cost < dp[new_mask][v]:
                    dp[new_mask][v] = new_cost
                bits &= bits - 1
    
    print(min(dp[full-1]))

main()

---

この解説は claude4.6opus-thinking によって生成されました。