概要

\(N\) 個の絵画を \(N\) か所の位置に並べる順列を決め、隣り合う絵画の色調値の差と仕切り壁の重みの積の総和を最大化する問題です。\(N \leq 16\) という制約を活かし、ビットマスクDPで解きます。

考察

素朴なアプローチ

すべての順列を試すと \(N!\) 通りの配置があります。\(N = 16\) のとき \(16! \approx 2 \times 10^{13}\) となり、到底間に合いません。

重要な気づき

評価値の計算式をよく見ると：

\[\sum_{i=1}^{N-1} |P_{Q_i} - P_{Q_{i+1}}| \times W_i\]

これは左から順に絵画を1つずつ配置していく過程として考えられます。位置 \(k\)（0-indexed）に絵画を置くとき、新たに加算される評価値は「位置 \(k-1\) に置いた絵画との色調値の差 × \(W_{k-1}\)」だけで決まります。

つまり、現在どの絵画が使用済みか（集合） と 最後に置いた絵画が何か さえ分かれば、次のステップで加算される値を計算できます。これはビットマスクDPの典型的な構造です。

アルゴリズム

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

状態定義

• \(dp[\text{mask}][j]\)：使用済みの絵画の集合が \(\text{mask}\)（ビットで表現）で、最後に配置した絵画が \(j\) であるときの、評価値の最大値。

初期状態

位置 \(0\) に絵画 \(j\) を1つだけ置いた状態：

\[dp[1 \ll j][j] = 0 \quad (0 \leq j < N)\]

まだ隣との比較がないので評価値は \(0\) です。

遷移

\(\text{mask}\) のビットが立っている数を \(bc\)（= 配置済みの絵画数）とすると、次に配置するのは位置 \(bc\)（0-indexed）です。位置 \(bc-1\) と位置 \(bc\) の間の壁の重みは \(W[bc-1]\) です。

まだ使っていない絵画 \(k\)（\(\text{mask}\) の \(k\) ビット目が \(0\)）を位置 \(bc\) に置くと：

\[dp[\text{mask} | (1 \ll k)][k] = \max\left(dp[\text{mask} | (1 \ll k)][k],\; dp[\text{mask}][j] + |P_j - P_k| \times W[bc-1]\right)\]

答え

すべての絵画を配置し終えた状態、すなわち \(\text{mask} = 2^N - 1\) のときの最大値：

\[\max_{j=0}^{N-1} dp[2^N - 1][j]\]

具体例（N=3, P=[1,3,5], W=[2,4]）

• 位置0に絵画を1つ配置（評価値0）
• 位置1に次の絵画を配置：壁の重み \(W[0]=2\) を使って差を計算
• 位置2に最後の絵画を配置：壁の重み \(W[1]=4\) を使って差を計算
• 例えば配置 \((1,5,3)\) なら \(|1-5| \times 2 + |5-3| \times 4 = 8 + 8 = 16\)

計算量

• 時間計算量: \(O(2^N \times N^2)\) — 各状態 \((mask, j)\) について未使用の絵画 \(k\) を列挙
• 空間計算量: \(O(2^N \times N)\) — DPテーブルのサイズ

\(N = 16\) のとき、\(2^{16} \times 16^2 = 65536 \times 256 \approx 1.7 \times 10^7\) 程度で十分間に合います。

実装のポイント

• ビット演算で未使用絵画を列挙: remaining = full ^ mask として、bits & -bits で最下位ビットを取り出すテクニックにより、未使用の絵画だけを高速に列挙しています。

• popcount で現在位置を特定: bin(mask).count('1') で配置済み絵画数を数え、次に使う壁の重み \(W[bc-1]\) を決定します。

• 初期値の管理: DPテーブルを \(-1\)（未到達）で初期化し、到達していない状態からの遷移をスキップしています。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    P = [int(input_data[idx + i]) for i in range(N)]; idx += N
    W = [int(input_data[idx + i]) for i in range(N - 1)]; idx += N - 1

    if N == 1:
        print(0)
        return

    # Bitmask DP
    # dp[mask][j] = maximum evaluation value when we have placed paintings corresponding to
    # bits in mask, and the last painting placed (at position |mask|-1) is painting j.
    # |mask| tells us how many paintings have been placed so far.

    INF = -1
    full = (1 << N) - 1

    # Initialize dp as dict or array
    # Since N <= 16, mask can be up to 2^16 = 65536, and j up to 15
    # Total states: 65536 * 16 = ~1M, manageable

    dp = [[INF] * N for _ in range(1 << N)]

    # Base case: place one painting at position 0
    for j in range(N):
        dp[1 << j][j] = 0

    for mask in range(1, 1 << N):
        bc = bin(mask).count('1')
        if bc >= N:
            continue
        # Position of next painting to place is bc (0-indexed)
        # The wall between position bc-1 and bc has weight W[bc-1]
        w = W[bc - 1]  # bc >= 1 since we need at least 1 painting placed
        for j in range(N):
            if dp[mask][j] == INF:
                continue
            if not (mask & (1 << j)):
                continue
            val = dp[mask][j]
            pj = P[j]
            # Try placing painting k at position bc
            remaining = full ^ mask
            bits = remaining
            while bits:
                k = (bits & -bits).bit_length() - 1
                new_mask = mask | (1 << k)
                new_val = val + abs(pj - P[k]) * w
                if new_val > dp[new_mask][k]:
                    dp[new_mask][k] = new_val
                bits &= bits - 1

    print(max(dp[full]))

solve()

---

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