概要

この問題は、配送コスト（選んだ会場の数の2乗 \(c^2\)）を考慮しながら、積載量 \(W\) 以下で展示品の利益を最大化するナップサック問題の変形版です。

会場の総数 \(K\) が \(K \le 8\) と非常に小さいことに着目し、「どの会場の展示品を選ぶか」を深さ優先探索（DFS）で全探索しながら、同時にナップサックDP（動的計画法）を更新していくことで、効率よく最適解を求めます。

考察

1. なぜ単純なナップサックDPでは解けないのか？

通常のナップサックDPでは、選んだ個々の展示品の重さと利益だけを管理します。しかし本問では、選んだ展示品の「会場の種類数 \(c\)」によって配送コストが \(c^2\) 引かれます。 同じ会場の展示品を何個選んでもコストは増えませんが、新しい会場の展示品を1つでも選ぶとコストが大きく跳ね上がります。そのため、「どの会場の展示品をすでに選んでいるか」という情報をDPの状態に持たせる必要があります。

2. \(K \le 8\) という制約に着目する

会場の数 \(K\) は最大でも \(8\) と非常に小さいです。各会場について、「その会場の展示品を1つ以上選ぶ（＝会場を使用する）」か、「1つも選ばない（＝会場を使用しない）」かの選択肢は \(2\) 通りしかありません。 すべての会場に対する選択の組み合わせは最大でも \(2^K = 2^8 = 256\) 通りです。

したがって、どの会場を使用するかをあらかじめ決めてしまえば、それぞれの決め方（最大256通り）に対して、選んだ会場に属する展示品だけを使った通常のナップサックDPを解くことができます。

3. DFSによる効率的なDPの更新

256通りそれぞれに対して一からDPを解き直すと、重複する計算が多くなり無駄が発生します。 そこで、深さ優先探索（DFS）を用いて、会場 \(1\) から順に「選ぶ」か「選ばない」かを分岐しながら、DPテーブルを段階的に更新していきます。

• 会場 \(i\) を「選ばない」場合：DPテーブルは更新せず、そのまま次の会場の探索に進みます。
• 会場 \(i\) を「選ぶ」場合：現在のDPテーブルをコピーし、会場 \(i\) に属する展示品を使ってDPテーブルを遷移（更新）させた後、次の会場の探索に進みます。

これにより、探索の途中で計算したDPテーブルを再利用できるため、大幅に計算量を削減できます。

---

アルゴリズム

1. 前処理

• 展示品を会場ごとにグループ分けします。
• 枝刈り（探索の早期打ち切り）の効果を高めるため、展示品の数が多い会場から順に処理するようにソートします。
• 各会場以降に残っているすべての展示品の利益の総和（累積和 rem_val）を計算しておきます。これは枝刈りの判定に使用します。

2. DFS（深さ優先探索）の設計

DFSの関数を dfs(depth, current_dp, selected_count) と定義します。 - depth: 現在検討している会場のインデックス（\(0 \le \text{depth} \le K\)） - current_dp: current_dp[w] は、重さの合計が \(w\) 以下のときの最大利益を表す配列（サイズ \(W+1\)） - selected_count: これまでに「選ぶ」と決定した会場の数（\(= c\)）

探索のステップ：

1. 最大値の更新: 現在のDPテーブルにおける最大利益は current_dp[W] です。ここから配送コスト selected_count \(^2\) を引いた値で、全体の最大値 ans を更新します。
2. 枝刈り: 「現在の最大利益 current_dp[W]」に「残りの会場にあるすべての展示品の利益 rem_val[depth]」を足し、そこから現在の配送コストを引いた値が、これまでの暫定最大値 ans 以下であれば、これ以上探索を続けても最大値を更新できる見込みがないため、探索を打ち切ります（return）。
3. ベースケース: depth == K（すべての会場を検討し終えた）なら探索を終了します。
4. 遷移（分岐）:
   • 選択肢1（選ばない）: 会場 depth の展示品を1つも選ばずに、次の会場へ進みます。 dfs(depth + 1, current_dp, selected_count)
   • 選択肢2（選ぶ）: 会場 depth の展示品からいくつか選ぶとして、DPテーブルを更新して進みます。 current_dp をコピーした next_dp を作成し、会場 depth に属する各展示品 \((w_i, v_i)\) について、以下の01ナップサックDPの遷移を行います。 $\(\text{next\_dp}[w] = \max(\text{next\_dp}[w], \text{next\_dp}[w - w_i] + v_i) \quad (w_i \le w \le W)\)$ 更新後、dfs(depth + 1, next_dp, selected_count + 1) を呼び出します。

---

計算量

時間計算量: \(O(2^K \cdot N \cdot W)\) （最悪値）

• DFSの分岐数は最大で \(2^K\) 通りです。
• 各分岐において、その会場に属する展示品の数 \(N_{\text{venue}}\) に対し、サイズ \(W\) のDPテーブルの更新を行うため、1ステップあたりの遷移コストは \(O(N_{\text{venue}} \cdot W)\) となります。
• 全体として、最悪時間計算量は \(O(2^K \cdot N \cdot W)\) となりますが、強力な枝刈り（rem_val による判定）と会場のソート順の工夫により、実際に探索される状態数は \(2^K\) よりも遥かに少なくなります。実行時間は数ミリ秒〜数十ミリ秒と非常に高速です。

空間計算量: \(O(K \cdot W + N)\)

• DFSの再帰の深さは最大で \(K\) です。
• 各深さで保持するDPテーブルのサイズは \(W + 1\) です。
• したがって、空間計算量は \(O(K \cdot W + N)\) となり、メモリ制限に対して十分に余裕があります。

---

実装のポイント

• 01ナップサックDPの更新順: 各展示品は1つしか選べないため、DPテーブルを更新する際は、重さ \(w\) を大きい方から逆順（W から w_i まで）にループを回す必要があります。これにより、同じ展示品を重複して選んでしまうことを防ぎます。

• 会場のソート順: 展示品が多い会場を先に処理することで、探索の早い段階で大きな利益（ans）を確定させることができます。これにより、枝刈りの条件式 current_dp[W] + rem_val[depth] - selected_count^2 <= ans が成立しやすくなり、無駄な探索を劇的に削減できます。

  ソースコード

import sys

# 再帰上限の変更（K <= 8 なので実際には不要だが念のため）
sys.setrecursionlimit(2000)


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    K = int(data[1])
    W = int(data[2])

    items_by_venue = [[] for _ in range(K + 1)]
    idx = 3
    for _ in range(N):
        w = int(data[idx])
        v = int(data[idx + 1])
        d = int(data[idx + 2])
        items_by_venue[d].append((w, v))
        idx += 3

    venues = [items_by_venue[i] for i in range(1, K + 1)]
    # 展示品数が多い会場から順に処理することで、DPの遷移回数を最小化する
    venues.sort(key=len, reverse=True)

    # 各深さ以降の会場に含まれる展示品の利益の総和（枝刈り用）
    rem_val = [0] * (K + 1)
    for i in range(K - 1, -1, -1):
        rem_val[i] = rem_val[i + 1] + sum(v for w, v in venues[i])

    ans = 0

    def dfs(depth, current_dp, selected_count):
        nonlocal ans

        # 現在のDPでの最大値を評価
        # current_dp は単調非減少なので、最大値は常に current_dp[W] となる
        val = current_dp[W] - selected_count * selected_count
        if val > ans:
            ans = val

        if depth == K:
            return

        # 枝刈り：残りの展示品をすべて選んでも暫定の最大値を超えられない場合は探索を打ち切る
        if current_dp[W] + rem_val[depth] - selected_count * selected_count <= ans:
            return

        # 選択肢1: 会場 depth を選ばない
        dfs(depth + 1, current_dp, selected_count)

        # 選択肢2: 会場 depth を選ぶ
        next_dp = current_dp[:]
        for w_i, v_i in venues[depth]:
            for w in range(W, w_i - 1, -1):
                if next_dp[w - w_i] + v_i > next_dp[w]:
                    next_dp[w] = next_dp[w - w_i] + v_i
        dfs(depth + 1, next_dp, selected_count + 1)

    init_dp = [0] * (W + 1)
    dfs(0, init_dp, 0)

    print(ans)


if __name__ == "__main__":
    solve()

---

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