概要

商品列の区間 \([L, R]\) から予算 \(X\) 以下で満足度を最大化する、区間指定付きの0/1ナップサック問題を \(Q\) 回答える問題です。

考察

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

各クエリに対して独立に0/1ナップサックを解くと、1回あたり \(O(N \times M)\) かかり、全体で \(O(Q \times N \times M)\) となります。\(Q = 100{,}000\), \(N = 300\), \(M = 500\) では約 \(1.5 \times 10^{10}\) 回の計算が必要となり、TLEになります。

重要な気づき

0/1ナップサックはアイテムを1つずつ追加して更新できる性質があります。つまり、アイテム集合 \(\{L, L+1, \ldots, R-1\}\) に対するDP配列がある状態で、アイテム \(R\) を追加して \(\{L, L+1, \ldots, R\}\) に対するDP配列を \(O(M)\) で得られます。

この性質を利用し、左端 \(L\) が同じクエリをまとめて処理します。\(L\) を固定したら、\(R\) を \(L\) から \(N\) まで1つずつ増やしながらDPを更新し、該当するクエリに都度答えれば、DP計算を共有できます。

アルゴリズム

1. クエリを左端 \(L\) ごとにグループ化し、各グループ内を \(R\) の昇順にソートする。

2. 各 \(L = 1, 2, \ldots, N\) について：

   • DP配列 \(dp[0..M]\) を全て \(0\) で初期化する（\(dp[w]\) = 重さ \(w\) 以下で得られる最大満足度）。
   • \(R = L, L+1, \ldots, N\) の順に以下を繰り返す：
     • アイテム \(R\)（価格 \(H_R\), 満足度 \(V_R\)）をナップサックに追加： $\(dp[w] \leftarrow \max(dp[w],\ dp[w - H_R] + V_R) \quad (w = M, M-1, \ldots, H_R)\)$
     • 現在の \(R\) に一致するクエリ \((L, R, X)\) があれば、答えは \(dp[X]\)。

3. 全クエリの答えを出力する。

具体例

\(N=3\), \(M=5\), アイテムが \((H,V) = (2,3), (3,5), (1,2)\) のとき、\(L=1\) について： - \(R=1\): アイテム1を追加 → \(dp = [0,0,3,3,3,3]\) - \(R=2\): アイテム2を追加 → \(dp = [0,0,3,5,5,8]\) - \(R=3\): アイテム3を追加 → \(dp = [0,2,3,5,7,8]\)

クエリ \((L=1, R=3, X=4)\) なら答えは \(dp[4] = 7\)。

計算量

• 時間計算量: \(O(N^2 \cdot M + Q \log Q)\)
  • 各 \(L\) について \(R\) を \(L\) から \(N\) まで回し、毎回 \(O(M)\) のDP更新 → \(\sum_{L=1}^{N}(N-L+1) \cdot M = O(N^2 M)\)
  • \(N=300, M=500\) で約 \(4.5 \times 10^7\) 回（C++で十分高速）
  • クエリのソートに \(O(Q \log Q)\)
• 空間計算量: \(O(M + Q)\)
  • DP配列は \(O(M)\)、各 \(L\) ごとに再利用
  • クエリ格納と答え格納に \(O(Q)\)

実装のポイント

• 0/1ナップサックの更新は重さを降順にループすることで、各アイテムが高々1回しか選ばれないことを保証する（昇順だと同じアイテムを複数回使ってしまう）。

• クエリを \(L\) ごとにグループ化し \(R\) でソートすることで、\(R\) を増やしながら逐次的にクエリに答えられる。

• \(dp[X]\) が「重さちょうど \(X\)」ではなく「重さ \(X\) 以下」の最大値になるよう、初期値を全て0にし、更新時に \(dp[w]\) を保持する形にしている（\(\max\) を取っているため、容量に余裕がある状態も自然に含まれる）。

  ソースコード

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    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];
    }
    
    // Group queries by L: queries[L] = list of (R, X, original_index)
    vector<vector<tuple<int, int, int>>> queries(N + 1);
    
    vector<long long> ans(Q);
    
    for (int j = 0; j < Q; j++) {
        int L, R, X;
        cin >> L >> R >> X;
        queries[L].emplace_back(R, X, j);
    }
    
    for (int L = 1; L <= N; L++) {
        if (queries[L].empty()) continue;
        
        // Sort queries by R
        sort(queries[L].begin(), queries[L].end());
        
        vector<long long> dp(M + 1, 0);
        int qidx = 0;
        
        for (int R = L; R <= N; R++) {
            // Add item R to knapsack (standard 0/1 knapsack update)
            for (int w = M; w >= H[R]; w--) {
                dp[w] = max(dp[w], dp[w - H[R]] + V[R]);
            }
            
            // Answer all queries with this L and this R
            while (qidx < (int)queries[L].size() && get<0>(queries[L][qidx]) == R) {
                int X = get<1>(queries[L][qidx]);
                int idx = get<2>(queries[L][qidx]);
                ans[idx] = dp[X];
                qidx++;
            }
        }
    }
    
    for (int j = 0; j < Q; j++) {
        cout << ans[j] << '\n';
    }
    
    return 0;
}

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