概要

\(N\) 個の展示品から重さの合計が \(W\) 以下になるように選び、「見込み利益の合計 \(-\) 配送コスト（訪問する異なる会場数の2乗）」を最大化する問題です。会場数 \(K \leq 8\) という制約を活かし、ビットマスクで会場の部分集合を列挙しつつナップサック問題を解きます。

考察

素朴なアプローチの問題点

普通の0/1ナップサックでは「どの展示品を選んだか」から「異なる会場数 \(c\)」を求めてコスト \(c^2\) を引く必要があります。ナップサックDPの状態に「使った会場の集合」を含めると、状態数が \(O(2^K \cdot W)\) になり、遷移に \(O(N)\) かかって全体で非常に大きくなります。

重要な気づき

「利用する会場の集合を先に決めてしまう」 というアプローチが有効です。

会場の部分集合 \(S\) を固定すれば： - 使える展示品は「出展先が \(S\) に含まれるもの」に限定される - 配送コストは \(|S|^2\) で確定する

したがって、各 \(S\) に対して「\(S\) に属する会場向けの展示品だけで通常の0/1ナップサック」を解き、得られた最大利益から \(|S|^2\) を引けばよいのです。

増分的なDP構築

\(K \leq 8\) なので部分集合は最大 \(2^8 = 256\) 個です。各部分集合ごとにナップサックをゼロから解くと遅いですが、増分的に構築できます。

部分集合 \(S\) の最下位ビット（ある会場 \(b\)）を見つけ、\(S' = S \setminus \{b\}\) とすると： - \(S'\) のナップサック結果はすでに計算済み - そこに会場 \(b\) の展示品を追加するだけで \(S\) のナップサック結果が得られる

これにより、各部分集合で追加する展示品は1つの会場分だけで済みます。

アルゴリズム

1. 展示品を会場ごとにグループ分けする
2. dp_arr[mask][w] = 会場集合 mask の展示品から重さ \(w\) 以下で得られる最大利益、と定義
3. dp_arr[0] = [0, 0, ..., 0]（空集合は利益0）
4. mask を \(1\) から \(2^K - 1\) まで順に処理：
   • mask の最下位ビット \(b\) を求め、prev = mask ^ (1 << b) とする
   • dp_arr[prev] をコピーし、会場 \(b\) の展示品で通常の0/1ナップサック更新を行う
   • 答えの候補：dp_arr[mask][W] - (|mask|の1の個数)^2
5. 全部分集合での候補の最大値（\(0\) 以上）を出力

計算量

• 時間計算量: \(O(2^K \cdot N \cdot W)\)
  • 各展示品は、自分の会場がlowest bitとなる \(2^{K-1}\) 個程度の部分集合で処理され、各回 \(O(W)\) の更新を行う
  • 実測では \(K=8, N=300, W=3000\) で十分高速
• 空間計算量: \(O(2^K \cdot W)\)
  • 全部分集合のナップサック配列を保持（\(256 \times 3001\) 程度）

実装のポイント

• 最下位ビットの取得: lsb = mask & (-mask) で効率的に取得し、bit_length() - 1 で会場番号に変換

• ナップサック更新の方向: 0/1ナップサックなので重さを大きい方から小さい方へ走査（同じ品物の多重選択を防ぐ）

• 答えの下限が0: 1個も選ばない場合（空集合）で利益0が保証されるため、答えは必ず非負

• 会場番号の0-indexed化: 入力は1-indexedだが、ビット操作のため内部では0-indexedに変換

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    W = int(input_data[idx]); idx += 1
    
    items = []
    for i in range(N):
        w = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        d = int(input_data[idx]); idx += 1
        items.append((w, v, d - 1))  # 0-indexed venue
    
    # Group items by venue
    venue_items = [[] for _ in range(K)]
    for w, v, d in items:
        venue_items[d].append((w, v))
    
    # For each subset of venues, solve a knapsack problem using only items from those venues
    # and compute max profit - popcount(subset)^2
    # K <= 8, so 2^8 = 256 subsets
    # For each subset, we need to solve a 0/1 knapsack with capacity W
    
    # Precompute for each venue, the items
    # For efficiency: iterate over subsets in a smart order
    # We can use the fact that subset S can be built from subset S without one venue
    # dp_knapsack[S][w] = max value using items from venues in S with total weight exactly w
    # But storing 256 * 2001 might be fine, and we build incrementally
    
    # Actually, let's think about it differently:
    # For each subset S, knapsack[S][w] = best value achievable with weight <= w using items from venues in S
    # We can compute knapsack[S] from knapsack[S without highest bit] by adding items from the highest bit venue
    
    # dp[S] = knapsack array of size W+1 for subset S
    # This requires 256 * 2001 storage = ~512K entries, which is fine
    
    # Build in order of subsets. For empty set, dp[0] = [0] * (W+1)
    # For subset S, find lowest set bit b, let S' = S ^ (1 << b)
    # dp[S] = dp[S'] then add all items from venue b (standard 0/1 knapsack update)
    
    best_answer = 0
    
    # Store dp as a dict of arrays to save memory (only need to keep what's needed)
    # Actually 256 arrays of 2001 ints is fine
    dp = [None] * (1 << K)
    dp[0] = bytearray(b'\x00' * (W + 1) * 4)  # Not great, let's use list approach
    
    # Let's use a simpler approach: just arrays
    # dp[mask] = list of length W+1, dp[mask][w] = max value with weight exactly w? 
    # Better: dp[mask][w] = max value with weight <= w
    
    # For memory, store as list of lists
    dp_arr = [None] * (1 << K)
    dp_arr[0] = [0] * (W + 1)
    
    for mask in range(1, 1 << K):
        # Find lowest set bit
        lsb = mask & (-mask)
        b = lsb.bit_length() - 1
        prev_mask = mask ^ lsb
        
        # Copy from prev_mask
        cur = dp_arr[prev_mask][:]
        
        # Add items from venue b (standard 0/1 knapsack, iterate items, weight backward)
        for w_item, v_item in venue_items[b]:
            for cap in range(W, w_item - 1, -1):
                val = cur[cap - w_item] + v_item
                if val > cur[cap]:
                    cur[cap] = val
        
        dp_arr[mask] = cur
        
        # Compute answer for this mask
        c = bin(mask).count('1')
        cost = c * c
        profit = cur[W] - cost
        if profit > best_answer:
            best_answer = profit
    
    print(best_answer)

main()

---

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