概要

\(N\)軒の家を1回ずつ訪問する順路の中で、移動コストの合計を最小化する問題です。移動コストは標高差と家番号差の積で計算されます。

考察

家の数\(N\)が最大20と小さいため、全ての順列を試すと\(19! \approx 1.2 \times 10^{17}\)通りとなり、全探索は不可能です。そこで、動的計画法による効率的な解法を考えます。

重要な観察は、訪問済みの家の集合と最後に訪問した家の情報だけで、その状態からの最小コストが一意に決まることです。これにより、状態数を\(2^N \times N\)（約\(20 \times 2^{20} \approx 20 \times 10^6\)）に抑えられます。

アルゴリズム

ビットマスクを用いた動的計画法（Bit DP）を適用します。

• 状態: dp[state][last] = 訪問済み家の集合がstate（ビットマスク）、最後に訪問した家がlastであるときの最小コスト
• 初期状態: 家1のみ訪問済み（state=1<<0）、最後の家が家1（last=0）でコスト0
• 遷移: 現在の状態(state, last)から、未訪問の家next_nodeへ移動
  • 移動コスト: abs(V[last] - V[next_node]) * abs(last - next_node)
  • 新しい状態: state | (1<<next_node)、最後の家がnext_node
• 答え: 全ての家を訪問した状態（state=(1<<n)-1）における最小コスト

計算量

• 時間計算量: \(O(2^N \times N^2)\)
• 空間計算量: \(O(2^N \times N)\)

\(N=20\)の場合、\(2^{20} \times 20^2 = 1048576 \times 400 \approx 4.2 \times 10^8\)回の計算となり、Pythonでも十分実行可能です。

実装のポイント

• 状態数を\(2^N \times N\)の二次元配列で管理

• 初期値は十分大きな数（INF）で初期化

• ビット演算を用いて状態の更新を効率的に行う

• 最終的に全ての家を訪問した状態での最小値を求める

  ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    V = list(map(int, data[1:1+n]))
    
    total_states = 1 << n
    INF = 10**18
    dp = [[INF] * n for _ in range(total_states)]
    
    dp[1][0] = 0
    
    for state in range(total_states):
        for last in range(n):
            if dp[state][last] == INF:
                continue
            for next_node in range(n):
                if state & (1 << next_node):
                    continue
                next_state = state | (1 << next_node)
                cost = abs(V[last] - V[next_node]) * abs(last - next_node)
                if dp[next_state][next_node] > dp[state][last] + cost:
                    dp[next_state][next_node] = dp[state][last] + cost
                    
    ans = min(dp[total_states-1])
    print(ans)

if __name__ == '__main__':
    main()

この解説は deepseekv3 によって生成されました。