概要

絵画を一列に並べる際、隣り合う絵画の色調値の差と壁の重みの積の総和を最大化する問題です。

考察

\(N\) 個の絵画を一列に並べる順列は \(N!\) 通りあり、\(N\) の最大値が16なので全探索は \(16! ≈ 2.0×10^{13}\) 通りとなり、単純な全探索では計算できません。そこで、動的計画法（DP）を用いて効率的に探索します。重要な観察として、評価値の計算が隣り合う絵画の組み合わせに依存しているため、部分的な配置情報（どの絵画を既に配置したか、最後に配置した絵画はどれか）を状態として持つことで、効率的に計算できます。

アルゴリズム

ビットDPを用います。状態を「既に配置した絵画の集合（ビットマスク）」と「最後に配置した絵画の番号」で定義し、その状態における評価値の最大値を保持します。具体的には、\(dp[state][last]\) を、状態 \(state\)（ビット表現）で最後に配置した絵画が \(last\) であるときの評価値の最大値とします。状態遷移は、未配置の絵画 \(next\) を選び、新たな状態 \(new\_state = state | (1 << next)\) における評価値を更新します。このとき、追加される評価値は \(|P[last] - P[next]| × W[k-1]\) です（\(k\) は現在の配置数）。すべての絵画を配置した状態（\(state = (1<<n)-1\)）での最大値が答えとなります。

計算量

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

実装のポイント

• ビットマスクを用いて状態を管理します。状態数は \(2^N\)、各状態で最後の絵画として \(N\) 通りを保持するため、二次元配列のサイズは \(2^N × N\) です。

• 初期状態では、各絵画を単独で配置した状態（ビットマスクが1ビット立っている）の評価値を0で初期化します。

• 状態遷移時には、現在の状態で使用済みの絵画と未使用の絵画を区別し、未使用の絵画を順に試して評価値を更新します。

• 最終的に、すべてのビットが立った状態（全絵画配置済み）での最大値を求めます。

  ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    P = list(map(int, data[1:1+n]))
    W = list(map(int, data[1+n:1+n+(n-1)]))
    
    total_states = 1 << n
    dp = [[-1] * n for _ in range(total_states)]
    
    for i in range(n):
        dp[1 << i][i] = 0
        
    for state in range(total_states):
        k = bin(state).count('1')
        if k == 0:
            continue
        for last in range(n):
            if dp[state][last] == -1:
                continue
            for next in range(n):
                if state & (1 << next):
                    continue
                new_state = state | (1 << next)
                add = abs(P[last] - P[next]) * W[k-1]
                if dp[new_state][next] < dp[state][last] + add:
                    dp[new_state][next] = dp[state][last] + add
                    
    ans = max(dp[total_states-1])
    print(ans)

if __name__ == "__main__":
    main()

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