概要

絵画を左から順に並べる順列を決め、隣り合う絵画の色調差 \(|P_a-P_b|\) に壁の重み \(W_i\) を掛けた総和を最大化します。\(N\le 16\) なので、集合（ビットマスク）を用いた動的計画法で「左から順に」最大値を求めます。

考察

重要な気づき

評価値は [ \sum{i=1}^{N-1} |P{Qi}-P{Q_{i+1}}|\times W_i ] で、各項は「位置 \(i\) と \(i+1\) に置かれた2枚」と「その間の壁の重み \(W_i\)」だけで決まります。

つまり、左から順に並べていくとき、 - すでに \(k\) 枚置いた状態（位置 \(1\sim k\) が確定） - 次に \((k+1)\) 枚目をどれにするか

だけを考えれば、増える評価は「最後の絵画」と「次の絵画」の差に \(W_k\) を掛けたものになります（境界は \(k\) と \(k+1\) の間なので重みは \(W_k\)）。

素朴な方法がダメな理由

すべての順列を試すと \(N!\) 通りで、\(N=16\) では [ 16!\approx 2.1\times 10^{13} ] となり、全探索は到底間に合いません。

どう解決するか

「どの絵画を使ったか」を集合として管理し、さらに「最後に置いた絵画」を状態に持つことで、 - 同じ集合・同じ最後の絵画に到達する経路のうち、評価値が最大のものだけを残す

という形で探索を圧縮できます（典型的な bitDP / 巡回セールスマン型DP）。

アルゴリズム

状態定義

ビットマスク \(\text{mask}\) を「すでに置いた絵画の集合」とします（\(i\) 番目のビットが 1 なら絵画 \(i\) を使用済み）。

[ dp[\text{mask}][\text{last}] ] を次のように定義します：

• \(\text{mask}\) に含まれる絵画を左から \(k=\mathrm{popcount}(\text{mask})\) 個並べ終えている
• そのとき一番右（位置 \(k\)）にある絵画が last
• ここまでの評価値の最大値

初期化は、1枚だけ置いた状態は評価 0： [ dp[1\ll i][i]=0 ]

遷移

\(\text{mask}\) のサイズを \(k=\mathrm{popcount}(\text{mask})\) とすると、次に置くのは位置 \(k+1\) です。増える評価は境界 \(k\) と \(k+1\) の間なので重みは \(W_k\)（1-indexedなら \(W_{k}\)、0-indexed配列なら W[k-1]）。

nxt を未使用の絵画として、 [

dp[\text{mask}\cup{nxt}][nxt]

\max\Big( dp[\text{mask}\cup{nxt}][nxt],\; dp[\text{mask}][last] + |P{last}-P{nxt}|\times W_k \Big) ]

コードでは \(k\) 枚置いた状態から次へ進むので weight = W[k-1] を使っています（0-indexのため）。

答え

全部使った \(\text{full}=(1\ll N)-1\) に対して、 [ \max_{last} dp[\text{full}][last] ] が答えです（最後の絵画が何でもよいので最大を取る）。

実装上の工夫

• \(|P_i-P_j|\) は頻繁に使うので、あらかじめ dist[i][j] として全て前計算します。
• 未使用集合の列挙は、r & -r で最下位ビットを取り出す方法で高速に回します。

計算量

• 時間計算量: \(O(N^2 2^N)\)
  （状態数が \(N2^N\)、各状態から最大 \(N\) 遷移）
• 空間計算量: \(O(N2^N)\)
  （DPテーブル）

実装のポイント

• 境界の重みの対応に注意：\(k\) 枚置いた状態から次へ進むときに使うのは「位置 \(k\) と \(k+1\) の間」の重みなので、0-index配列では W[k-1] になります。

• dp の未到達は None で管理し、max 更新時に分岐して扱うと安全です。

• Python では mask.bit_count() が高速で、\(N\le16\) の bitDP に非常に相性が良いです。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    P = list(map(int, input().split()))
    W = list(map(int, input().split()))
    full = (1 << N) - 1

    dist = [[0] * N for _ in range(N)]
    for i in range(N):
        pi = P[i]
        for j in range(N):
            dist[i][j] = abs(pi - P[j])

    dp = [[None] * N for _ in range(1 << N)]
    for i in range(N):
        dp[1 << i][i] = 0

    for mask in range(1 << N):
        k = mask.bit_count()
        if k == 0 or k == N:
            continue
        weight = W[k - 1]
        rem = full ^ mask
        row = dp[mask]
        for last in range(N):
            val = row[last]
            if val is None:
                continue
            r = rem
            dlast = dist[last]
            while r:
                lsb = r & -r
                nxt = lsb.bit_length() - 1
                nmask = mask | lsb
                nv = val + dlast[nxt] * weight
                cur = dp[nmask][nxt]
                if cur is None or nv > cur:
                    dp[nmask][nxt] = nv
                r -= lsb

    ans = max(v for v in dp[full] if v is not None)
    print(ans)

if __name__ == "__main__":
    main()

---

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