概要

この問題は、いくつかの展示品を選んでトラック（積載量 \(W\)）に積み込み、「選んだ展示品の見込み利益の合計」から「配送コスト（訪れる異なる会場の数の2乗）」を引いた値を最大化する問題です。

会場の総数 \(K\) が \(1 \le K \le 8\) と非常に小さいことに着目し、ビットDP（集合DP）と\(0-1\) ナップサック問題のDPを組み合わせることで、制限時間内に効率よく解くことができます。

---

考察

1. 会場の選択を固定する

配送コストは、選んだ展示品の「異なる会場の数 \(c\)」のみに依存します。 もし、「どの会場の展示品を選ぶか」という会場の集合 \(S\)（\(S \subseteq \{1, 2, \dots, K\}\)）をあらかじめ決めたとしましょう。

このとき、訪れる会場の数は \(c = |S|\) で固定されるため、配送コストは \(c^2\) で確定します。 したがって、集合 \(S\) を固定したもとでの最大利益は、以下の問題（通常の \(0-1\) ナップサック問題）を解くことで求まります。

「集合 \(S\) に含まれる会場の展示品のみを使って、重さの合計が \(W\) 以下となるように選んだときの、見込み利益の最大値」

すべての可能な集合 \(S\)（空集合を除くと \(2^K - 1\) 通り）についてこのナップサック問題を解き、各 \(S\) について (最大利益) - |S|^2 を計算してその最大値をとれば、全体の答えを求めることができます。

2. 重複する計算をDPで高速化する

\(2^K\) 通りの集合のそれぞれに対して、一からナップサックDPを解くと計算量が大きくなってしまいます。 そこで、集合の包含関係を利用して、以前に計算したDPテーブルを再利用（遷移）することを考えます。

集合 \(S\) に対するDPテーブルを dp[S][w]（集合 \(S\) の展示品のみを使い、重さ \(w\) 以下での最大利益）とします。 集合 \(S\) から任意の1つの会場 \(j \in S\) を除いた集合を \(prev\_S = S \setminus \{j\}\) とすると、dp[S] は以下のように段階的に作ることができます。

1. dp[S] に dp[prev_S] の結果をそのままコピーする（会場 \(j\) の展示品を1個も選ばない場合に相当）。
2. 会場 \(j\) に属する展示品を使って、dp[S] のDPテーブルを更新する（会場 \(j\) の展示品を選ぶ場合に相当）。

このように、集合 \(S\) を「すでに計算済みの部分集合 \(prev\_S\)」に「新しい会場 \(j\) の展示品」を追加したものとして遷移させることで、無駄な再計算を省くことができます。

---

アルゴリズム

ステップ 1: 会場のソート（最適化）

計算量を削減するため、展示品数が少ない会場ほど「多くの集合 \(S\) の遷移元」として使われるように、会場のインデックスを展示品数の昇順にソートします。 （※詳細は「計算量」および「実装のポイント」を参照）

ステップ 2: DPテーブルの更新

dp[S][w] を「会場の集合 \(S\) に属する展示品のみを考慮したときの、制限重量 \(w\) における最大利益」と定義します。

1. dp テーブルを \(0\) で初期化します。
2. \(S = 1\) から \(2^K - 1\) までループを回します。
3. \(S\) の最も右にある立っているビット（最下位ビット）を \(j\) とします。
4. \(prev\_S = S \setminus \{j\}\)（\(S\) から \(j\) を除いた集合）とします。
5. dp[S] に dp[prev_S] をコピーします。
6. 会場 \(j\)（ソート後の実際の会場番号）に属する各展示品 \(i\) について、以下のように dp[S] を更新します。 $\(dp[S][w] = \max(dp[S][w], dp[S][w - w_i] + v_i) \quad (w = W, W-1, \dots, w_i)\)$

ステップ 3: 答えの計算

すべての集合 \(S\)（\(0 \le S < 2^K\)）について、以下を計算してその最大値を求めます。 $\(\text{最大値} = \max_{S} \left( dp[S][W] - |S|^2 \right)\)\( ここで、\)|S|\( は集合 \)S$ に含まれる会場の数（ビット表現における立っているビットの数）です。

---

計算量

時間計算量

各会場 \(j\)（\(0 \le j < K\)）が最下位ビットとして選ばれる集合 \(S\) の個数は \(2^{K - 1 - j}\) 個です。 会場 \(j\) に属する展示品の数を \(N_j\) とすると、全体の計算量は以下のようになります。

\[O\left( \sum_{j=0}^{K-1} 2^{K - 1 - j} \cdot N_j \cdot W \right)\]

最悪の場合でも、展示品の総数 \(\sum N_j = N\) であるため、各会場の展示品数が均等（\(N/K\) 程度）のとき、全体の計算量は約 \(O(2^K \cdot \frac{N}{K} \cdot W)\) となります。 本問題の制約（\(N \le 300, K \le 8, W \le 3000\)）を当てはめると、最悪ケースでも演算回数は約 \(2.8 \times 10^7\) 回となり、実行時間制限に十分間に合います。

空間計算量

• \(O(2^K \cdot W)\)

DPテーブルのサイズは \(2^K \times (W + 1)\) です。 \(2^8 \times 3001 \approx 7.7 \times 10^5\) 要素（long long 型で約 6.1 MB）であり、メモリ制限に対して非常に余裕があります。

---

実装のポイント

• 最下位ビットの高速な取得: C++20 で導入された std::countr_zero を使用することで、集合 \(S\) の最下位ビットのインデックス \(j\) を高速（定数時間）に取得できます。

• ポップカウントの高速化: 選んだ会場の数 \(|S|\) を求める際、C++20 の std::popcount を使用することで、ビットが立っている数を高速にカウントできます。

• 会場のソートによる最適化: 遷移の回数（\(2^{K-1-j}\)）は、インデックス \(j\) が小さい（下位ビットである）ほど多くなります。そのため、展示品の数 \(N_j\) が少ない会場をインデックスの若い順（下位ビット側）に配置することで、重いナップサックDPの遷移回数を劇的に減らし、実行速度を高速化しています。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <bit>

using namespace std;

struct Item {
    int w;
    long long v;
};

int main() {
    // Optimize standard I/O operations for competitive programming
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K, W;
    if (!(cin >> N >> K >> W)) return 0;

    vector<vector<Item>> items_by_venue(K);
    for (int i = 0; i < N; ++i) {
        int w, d;
        long long v;
        cin >> w >> v >> d;
        --d; // Convert to 0-indexed
        items_by_venue[d].push_back({w, v});
    }

    // Optimization: Sort venue indices by the number of items in ascending order.
    // This minimizes the overall computation because the transition cost
    // in the DP depends on the size of the set's least significant bit.
    vector<int> p(K);
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(), [&](int a, int b) {
        return items_by_venue[a].size() < items_by_venue[b].size();
    });

    // dp[S][w] stores the maximum profit using a subset of venues S with total weight <= w
    vector<vector<long long>> dp(1 << K, vector<long long>(W + 1, 0));

    for (int S = 1; S < (1 << K); ++S) {
        int j = std::countr_zero((unsigned int)S);
        int prev_S = S ^ (1 << j);
        
        // Copy the DP state from the subset without venue j
        dp[S] = dp[prev_S];
        
        // Update the DP state by incorporating items from venue j
        for (const auto& item : items_by_venue[p[j]]) {
            for (int w = W; w >= item.w; --w) {
                dp[S][w] = max(dp[S][w], dp[S][w - item.w] + item.v);
            }
        }
    }

    long long ans = 0;
    for (int S = 0; S < (1 << K); ++S) {
        int c = std::popcount((unsigned int)S);
        long long profit = dp[S][W];
        long long cost = (long long)c * c;
        ans = max(ans, profit - cost);
    }

    cout << ans << "\n";

    return 0;
}

---

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