概要

家 \(1\) から出発して全ての家をちょうど一度ずつ訪問するとき、移動コスト \(|V_i-V_j|\times|i-j|\) の合計が最小になる訪問順（ハミルトン路）を求める問題です。\(N\le 20\) なので、部分集合DP（bit DP）で解けます。

考察

重要な気づき

• 「未訪問の家ならどこへでも直接移動できる」ため、経路の制約は 訪問順序 だけです。
• つまり本質的には「重み付き完全グラフ上の最短ハミルトン路（始点固定、終点自由）」です。
• ただしコストは対称で、各辺の重みは $\( w(i,j)=|V_i-V_j|\times|i-j| \)$ と事前計算できます。

素朴解がダメな理由

訪問順序を全探索すると、順序は \((N-1)!\) 通り（家1以外の並べ替え）あります。
例えば \(N=20\) だと \(19!\approx 1.2\times 10^{17}\) で、到底間に合いません。

解決方針

「どの家集合を訪問済みか」と「最後にいる家」だけが次の遷移に必要です（過去の順序全体は不要）。
この性質を使い、状態を圧縮したDP（bit DP） を行います。

アルゴリズム

状態

家 \(1\) は最初から訪問済みなので、家 \(2..N\) の訪問状況をビットで持ちます。

• \(M=N-1\)（家 \(2..N\) の個数）
• mask：\(M\) bit の整数
  
  • bit \(k\)（\(0\)-indexed）が 1 ⇔ 家 \((k+2)\) を訪問済み
• last：現在いる家（0-indexed で \(0..N-1\)）
  • last=0 は家1、last=1 は家2、… を表す

DPは $\( dp[\text{mask}][\text{last}] = \text{「家1から開始し、maskの家を訪問し終えてlastにいる最小コスト」} \)$ とします。

初期状態： - まだ家 \(2..N\) を訪問していないので mask=0 - 現在地は家1なので last=0 - よって \(dp[0][0]=0\)

遷移

未訪問の家 nxt を1つ選んで移動します。 - newmask = mask | (nxt に対応するビット) - 遷移コストは事前計算した \(w(last,nxt)\)

式で書くと $\( dp[newmask][nxt] = \min\left(dp[newmask][nxt],\ dp[mask][last] + w(last,nxt)\right) \)$

答え

全て訪問した状態は full = (1<<M)-1。終点は自由なので $\( \min_{last\in\{2..N\}} dp[full][last] \)\( が答えです（\)N=1$ のときは移動がないので 0）。

具体例（\(N=3\)）

家2と家3の訪問状況を2bitで持つ： - mask=00（誰も訪問していない）から開始 - 例えば家2へ行くなら mask=01, last=家2 - 次に家3へ行くなら mask=11, last=家3
というように、訪問済み集合と最後の家だけで更新できます。

計算量

• 時間計算量: \(O(N^2 \cdot 2^{N-1})\)
  各 mask（\(2^{N-1}\) 通り）について、last（最大 \(N\) 通り）から nxt（最大 \(N\) 通り）へ遷移するため。
• 空間計算量: \(O(N \cdot 2^{N-1})\)
  DP表の大きさが状態数に比例します。

実装のポイント

• 家2..Nだけをbitで管理すると、開始時点（家1訪問済み）を自然に扱えて状態数も半分になります。

• 遷移では rem = full ^ mask を使い、未訪問集合を取り出してから
  b = r & -r（最下位の1bit）で高速に列挙しています。

• DP配列は dp[mask*N + last] の一次元にして高速化・省メモリ化しています。

• コスト \(w(i,j)\) は全組を前計算（\(O(N^2)\)）して、DP中は足し算だけにします。

  ソースコード

import sys
from array import array

def main():
    input = sys.stdin.readline
    N = int(input())
    V = list(map(int, input().split()))
    if N == 1:
        print(0)
        return

    w = [[0] * N for _ in range(N)]
    for i in range(N):
        vi = V[i]
        ii = i + 1
        row = w[i]
        for j in range(N):
            row[j] = abs(vi - V[j]) * abs(ii - (j + 1))

    M = N - 1
    full = (1 << M) - 1
    INF = 10**18

    size = (1 << M) * N
    dp = array('Q', [INF]) * size
    dp[0] = 0  # mask=0, last=0

    for mask in range(1 << M):
        base = mask * N
        rem = full ^ mask

        if mask == 0:
            cur = dp[0]
            if cur != INF:
                r = rem
                w0 = w[0]
                while r:
                    b = r & -r
                    nxt = (b.bit_length() - 1) + 1
                    newmask = b
                    idx = newmask * N + nxt
                    val = cur + w0[nxt]
                    if val < dp[idx]:
                        dp[idx] = val
                    r -= b
            continue

        tmp = mask
        while tmp:
            b_last = tmp & -tmp
            last = (b_last.bit_length() - 1) + 1
            cur = dp[base + last]
            if cur != INF and rem:
                wl = w[last]
                r = rem
                while r:
                    b = r & -r
                    nxt = (b.bit_length() - 1) + 1
                    newmask = mask | b
                    idx = newmask * N + nxt
                    val = cur + wl[nxt]
                    if val < dp[idx]:
                        dp[idx] = val
                    r -= b
            tmp -= b_last

    base = full * N
    ans = INF
    tmp = full
    while tmp:
        b = tmp & -tmp
        last = (b.bit_length() - 1) + 1
        val = dp[base + last]
        if val < ans:
            ans = val
        tmp -= b

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。