概要

\(N\) 個の絵画の並べ方（順列）を最適化し、隣り合う絵画の色調値の差と、その位置の仕切り壁の重みの積の総和を最大化する問題です。制約が \(N \le 16\) と小さいため、巡回セールスマン問題（TSP）と似た考え方の bit DP（動的計画法） を用いて解くことができます。

考察

まず、すべての絵画の並べ方を全探索（順列の全列挙）する素朴なアプローチを考えてみます。並べ方の総数は \(N!\) 通りになりますが、\(N = 16\) のとき \(16! \approx 2.09 \times 10^{13}\) となり、制限時間内に計算を終えることは到底できません（TLEになります）。

ここで、評価値の計算方法に注目します。左から順に絵画を配置していくとき、新しく追加される評価値は 「1つ前に配置した絵画」と「新しく配置する絵画」の差分 だけで決まります。 つまり、次にどの絵画を配置するかを考える際、「これまでどのような順番で絵画を配置してきたか」をすべて記憶しておく必要はなく、以下の2つの情報さえ分かっていれば十分です。 1. これまでどの絵画を使用したか（使用済みの絵画の集合） 2. 最後に配置した絵画はどれか

このように状態をまとめることで、調べるべきパターン数を劇的に減らすことができます。これは「巡回セールスマン問題」を解く際によく使われる bit DP のテクニックそのものです。

アルゴリズム

絵画の集合をビット列 \(S\) で表す bit DP を行います。（例：絵画 \(0\) と \(2\) を使用済みなら \(S = 101_{(2)} = 5\)）

1. DPテーブルの定義 \(dp[S][u]\) を、「すでに配置した絵画の集合が \(S\) で、最後に配置した（一番右にある）絵画が \(u\) であるときの、評価値の最大値」と定義します。 （あり得ない状態は \(-1\) で初期化しておきます）

2. 初期状態 最初に絵画を1つだけ選んで配置します。 すべての \(i\) \((0 \le i \le N-1)\) について、\(dp[1 \ll i][i] = 0\) とします。 （まだ壁をまたいでいないため、評価値は \(0\) です）

3. 遷移 すでに配置した絵画の集合を \(S\)、最後に配置した絵画を \(u\) とします。 次に、まだ配置していない絵画 \(v\) （\(v \notin S\)）を配置することを考えます。

このとき、\(S\) に含まれる絵画の個数を \(k\) 個とすると、次にまたぐ仕切り壁は左から \(k\) 番目の壁なので、その重みは \(W_k\)（0-indexedなら \(W_{k-1}\)）になります。 したがって、新しい評価値は現在の評価値に \(|P_u - P_v| \times W_{k-1}\) を足したものになります。

遷移式は以下のようになります。 $\(dp[S \cup \{v\}][v] = \max(dp[S \cup \{v\}][v], dp[S][u] + |P_u - P_v| \times W_{k-1})\)$

1. 答え すべての絵画を配置し終えた状態（\(S = (1 \ll N) - 1\)）において、最後に配置した絵画 \(u\) が何であれ、最大の評価値を持つものが答えになります。 $\(\max_{0 \le u \le N-1} dp[(1 \ll N) - 1][u]\)$

計算量

• 時間計算量: \(O(2^N N^2)\) 状態数が \(2^N \times N\) 通りあり、それぞれの状態から次に配置する絵画 \(v\) を最大 \(N\) 通り試すためです。\(N=16\) のとき \(2^{16} \times 16^2 \approx 1.6 \times 10^7\) 回のループとなり、制限時間内に十分に間に合います。
• 空間計算量: \(O(2^N N)\) DPテーブルとして \(2^N \times N\) の配列を保持するためです。

実装のポイント

Pythonなどのスクリプト言語では、実行速度（定数倍）に気を配る必要があります。正解コードでは以下の工夫によって高速化を図っています。 - 前計算の活用: 絵画間の色調値の差分 \(|P_u - P_v|\) をあらかじめ2次元配列 diff に計算して保存しています。 - 集合に対する要素の分類: 各状態 \(S\) に対して、「含まれる要素（in_s）」と「含まれない要素（out_s）」、および「要素数（popcount）」を事前に計算してリストにまとめています。これにより、メインのDPループ内でビット演算による判定を省き、必要な要素だけを直接ループで回すことができるため、大幅な高速化に繋がります。

ソースコード

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    n = int(data[0])
    p = [int(x) for x in data[1:n+1]]
    w = [int(x) for x in data[n+1:2*n]]
    
    diff = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            diff[i][j] = abs(p[i] - p[j])

    dp = [[-1] * n for _ in range(1 << n)]
    for i in range(n):
        dp[1 << i][i] = 0
        
    popcount = [0] * (1 << n)
    in_s = [[] for _ in range(1 << n)]
    out_s = [[] for _ in range(1 << n)]
    for s in range(1 << n):
        popcount[s] = popcount[s >> 1] + (s & 1)
        for i in range(n):
            if s & (1 << i):
                in_s[s].append(i)
            else:
                out_s[s].append(i)
                
    for s in range(1, (1 << n) - 1):
        k = popcount[s]
        weight = w[k - 1]
        
        dp_s = dp[s]
        for u in in_s[s]:
            curr = dp_s[u]
            if curr == -1:
                continue
            
            diff_u = diff[u]
            for v in out_s[s]:
                val = curr + diff_u[v] * weight
                nxt_s = s | (1 << v)
                if val > dp[nxt_s][v]:
                    dp[nxt_s][v] = val
                        
    print(max(dp[(1 << n) - 1]))

if __name__ == '__main__':
    solve()

この解説は gemini-3.1-pro-thinking によって生成されました。