概要

区間 \([L_j, R_j]\) に含まれる商品だけを使った、予算 \(X_j\) 以下の 0/1 ナップサック問題を \(Q\) 回解く問題です。

\(Q\) が最大 \(100000\) と大きい一方で、\(N \leq 300\), \(M \leq 500\) と小さいため、全ての区間についてナップサック DP を効率よく計算します。

考察

各クエリごとに普通に 0/1 ナップサックをすると、1 クエリあたり

\(O((R-L+1)M)\)

かかります。

最悪では \(O(NM)\) なので、全体では

\(O(QNM)\)

となり、制約上

\(100000 \times 300 \times 500 = 15000000000\)

程度の計算になってしまい、間に合いません。

そこで、クエリごとではなく「区間ごと」に考えます。

区間 \([L, R]\) は全部で高々

\(O(N^2)\)

個しかありません。
\(N \leq 300\) なので、区間数は約 \(45000\) 個です。

さらに、予算上限 \(M\) も \(500\) と小さいため、各区間に対するナップサック DP をまとめて計算すれば間に合います。

重要な気づきは次の通りです。

固定した左端 \(L\) に対して、右端 \(R\) を

\(L, L+1, L+2, \ldots, N\)

と順に伸ばしていくと、区間 \([L, R]\) の DP は、区間 \([L, R-1]\) の DP に商品 \(R\) を追加するだけで作れます。

つまり、左端 \(L\) を固定して DP 配列を 1 つ持ち、右端を 1 つずつ増やしながら 0/1 ナップサックの更新を行えばよいです。

アルゴリズム

まず、クエリを区間ごとにまとめておきます。

具体的には、bucket[L][R] に区間 \([L, R]\) に対するクエリを入れておきます。
各クエリについて必要なのは予算 \(X\) と、答えを出力するためのクエリ番号 id です。

次に、左端 \(L\) を \(1\) から \(N\) まで全て試します。

固定した \(L\) に対して、DP 配列を用意します。

\(dp[c] =\) 現在の区間の商品を使って、予算 \(c\) 以下で得られる満足度の最大値

とします。

最初は商品を何も見ていないので、すべて \(0\) です。

そして右端 \(R\) を \(L\) から \(N\) まで順に増やします。

商品 \(R\) の価格を \(h = H_R\)、満足度を \(v = V_R\) とすると、0/1 ナップサックの更新は次のようになります。

for (int c = M; c >= h; c--) {
    dp[c] = max(dp[c], dp[c - h] + v);
}

ここで \(c\) を大きい方から更新することが重要です。
小さい方から更新すると、同じ商品を何度も使ってしまう可能性があります。

この更新が終わった時点で、dp[c] は区間 \([L, R]\) の商品だけを使ったときの、予算 \(c\) 以下の満足度の最大値になっています。

したがって、bucket[L][R] に入っているクエリについて、予算 \(X\) に対する答えはそのまま

dp[X]

です。

これをクエリ番号に対応する ans[id] に保存します。

最後に、入力順に ans を出力します。

計算量

• 時間計算量: \(O(N^2M + Q)\)
• 空間計算量: \(O(M + N^2 + Q)\)

\(N \leq 300\), \(M \leq 500\) なので、\(N^2M\) は約 \(45000000\) 程度であり、十分高速に実行できます。

実装のポイント

0/1 ナップサックなので、DP の更新は必ず予算を大きい方から小さい方へ行います。

for (int c = M; c >= h; c--) {
    dp[c] = max(dp[c], dp[c - h] + v);
}

また、満足度 \(V_i\) は最大 \(10^9\) で、商品数も最大 \(300\) 個あるため、満足度の合計は int に収まらない可能性があります。
そのため、DP 配列や答えは long long 型で持つ必要があります。

ソースコード

#include <bits/stdc++.h>
using namespace std;

struct Query {
    int x, id;
};

static vector<Query> bucket[305][305];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, Q;
    cin >> N >> M >> Q;

    vector<int> H(N + 1);
    vector<long long> V(N + 1);

    for (int i = 1; i <= N; i++) {
        cin >> H[i] >> V[i];
    }

    vector<long long> ans(Q);

    for (int i = 0; i < Q; i++) {
        int L, R, X;
        cin >> L >> R >> X;
        bucket[L][R].push_back({X, i});
    }

    for (int L = 1; L <= N; L++) {
        vector<long long> dp(M + 1, 0);

        for (int R = L; R <= N; R++) {
            int h = H[R];
            long long v = V[R];

            for (int c = M; c >= h; c--) {
                dp[c] = max(dp[c], dp[c - h] + v);
            }

            for (const auto &q : bucket[L][R]) {
                ans[q.id] = dp[q.x];
            }
        }
    }

    for (int i = 0; i < Q; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}

---

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