D - お買い物プラン / Shopping Plan Editorial by admin
gemini-3-flash-thinking概要
この問題は、与えられたアイテムの範囲 \([L_j, R_j]\) と予算 \(X_j\) に対して、最大満足度を求める「範囲制限付きの 0/1 ナップサック問題」です。商品の数 \(N\) や予算の上限 \(M\) は比較的小さいですが、クエリ数 \(Q\) が非常に多いため、クエリごとに独立して動的計画法（DP）を行うと間に合いません。
考察
素朴なアプローチ
1つのクエリに対してナップサック問題を解く場合、計算量は \(O(N \times M)\) となります。これを \(Q\) 回繰り返すと、全体の計算量は \(O(Q \times N \times M)\) です。 制約を代入すると \(10^5 \times 300 \times 500 = 1.5 \times 10^{10}\) となり、実行時間制限（通常 2秒程度）を大幅に超えてしまいます。
効率化のポイント
この問題の肝は、「範囲が固定された静的なデータに対して、大量の範囲クエリをどう捌くか」という点にあります。 商品の並びが固定されているため、分割統治法（Divide and Conquer）を用いることで、重複する計算をまとめ、クエリあたりの計算量を削減することが可能です。
アルゴリズム
「分割統治法」を用いて、クエリを再帰的に処理します。
1. 分割統治の仕組み
関数 solve(L, R, queries) を考えます。これは、範囲 \([L, R]\) に完全収まるクエリ群を処理する関数です。
- 範囲の中央 \(mid = (L+R)/2\) を決めます。
- クエリを以下の3つに分類します。
- 左側 \([L, mid]\) に完全に収まるクエリ
- 右側 \([mid+1, R]\) に完全に収まるクエリ
- \(mid\) をまたぐ（\(L_j \le mid\) かつ \(R_j > mid\)）クエリ
- 左右に完全に収まるクエリは、さらに
solveを再帰的に呼び出して処理します。 - \(mid\) をまたぐクエリを、このステップで一括して処理します。
2. またぐクエリの処理（マージ）
\(mid\) をまたぐクエリ \([L_j, R_j]\) は、「左側の断片 \([L_j, mid]\)」と「右側の断片 \([mid+1, R_j]\)」に分解できます。
- 左側の準備: \(mid\) から左方向（\(mid, mid-1, \ldots, L\)）へ向かって、各位置を開始点としたナップサック DP（接尾辞 DP）を計算しておきます。
- 右側の準備: \(mid+1\) から右方向（\(mid+1, mid+2, \ldots, R\)）へ向かって、各位置を終了点としたナップサック DP（接頭辞 DP）を計算しておきます。
- 結合: クエリの予算を \(X_j\) とすると、左側で予算 \(k\)、右側で予算 \(X_j - k\) を使う場合の最大満足度の和を、すべての \(0 \le k \le X_j\) について試せば、そのクエリの答えが求まります。
この結合処理は、1つのクエリにつき \(O(M)\) で終わります。
計算量
DPテーブルの構築: 分割統治の各レベルにおいて、全アイテム \(N\) 個について DP を行います。分割の深さは \(O(\log N)\) なので、全体で \(O(N \times M \times \log N)\) です。
クエリの処理: 各クエリは必ずどこか一つの \(mid\) をまたぐタイミングで一度だけ処理されます。その際の結合処理は \(O(M)\) なので、全体で \(O(Q \times M)\) です。
合計時間計算量: \(O(N M \log N + QM)\) 制約を当てはめると、約 \(1.2 \times 10^6 + 5 \times 10^7\) となり、制限時間内に十分収まります。
空間計算量: \(O(NM + Q)\) 再帰の各段階で DP テーブルを保持する必要があります。
実装のポイント
DPテーブルの管理:
cur_dp_l[i][w]は「アイテム \(i\) から \(mid\) までを使って重さ \(w\) 以下にする最大満足度」を保持します。メモリ節約のため、1次元配列を再利用したり、必要な分だけ確保するようにします。クエリの振り分け: 再帰ごとにクエリのリストを
left_q,right_q,cross_qに振り分けることで、無駄な探索を省きます。入出力の高速化: \(Q=10^5\) と多いため、C++ の場合は
cin.tie(NULL); ios::sync_with_stdio(false);を使用し、endlの代わりに\nを使うのが望ましいです。ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Structure to store item properties: price (h) and satisfaction (v)
struct Item {
int h;
long long v;
};
// Structure to store query details: range [l, r], budget (x), and original index (id)
struct Query {
int l, r, x, id;
};
int N, M, Q;
Item items[305];
long long results[100005];
/**
* Solves the range knapsack problem using a Divide and Conquer approach.
* This handles queries by splitting the range and processing those that cross the midpoint.
*
* Time Complexity: O(N * M * log N + Q * M)
* Space Complexity: O(N * M + Q)
*/
void solve(int L, int R, const vector<Query>& queries) {
// If no queries are in this range, return early
if (queries.empty()) return;
// Base case: range consists of a single item
if (L == R) {
for (const auto& q : queries) {
// Only one item to consider, check if budget allows it
results[q.id] = (items[L].h <= q.x ? items[L].v : 0);
}
return;
}
int mid = (L + R) / 2;
vector<Query> left_q, right_q, cross_q;
// Distribute queries into three groups based on their range [l, r]
for (const auto& q : queries) {
if (q.r <= mid) {
left_q.push_back(q);
} else if (q.l > mid) {
right_q.push_back(q);
} else {
cross_q.push_back(q);
}
}
// Process queries that cross the midpoint
if (!cross_q.empty()) {
int l_size = mid - L + 2;
int r_size = R - mid + 1;
int m_plus_1 = M + 1;
// DP tables for the suffix of the left side and prefix of the right side
// cur_dp_l[i - L] stores the knapsack for items [i, mid]
// cur_dp_r[i - mid] stores the knapsack for items [mid + 1, i]
vector<long long> cur_dp_l(l_size * m_plus_1, 0);
vector<long long> cur_dp_r(r_size * m_plus_1, 0);
// Compute suffix knapsacks for the left side [L, mid]
for (int i = mid; i >= L; --i) {
int idx = i - L;
int next_idx = idx + 1;
int cur_base = idx * m_plus_1;
int next_base = next_idx * m_plus_1;
int h = items[i].h;
long long v = items[i].v;
for (int w = 0; w < h; ++w) {
cur_dp_l[cur_base + w] = cur_dp_l[next_base + w];
}
for (int w = h; w <= M; ++w) {
long long val1 = cur_dp_l[next_base + w];
long long val2 = cur_dp_l[next_base + w - h] + v;
cur_dp_l[cur_base + w] = (val1 > val2 ? val1 : val2);
}
}
// Compute prefix knapsacks for the right side [mid + 1, R]
for (int i = mid + 1; i <= R; ++i) {
int idx = i - mid;
int prev_idx = idx - 1;
int cur_base = idx * m_plus_1;
int prev_base = prev_idx * m_plus_1;
int h = items[i].h;
long long v = items[i].v;
for (int w = 0; w < h; ++w) {
cur_dp_r[cur_base + w] = cur_dp_r[prev_base + w];
}
for (int w = h; w <= M; ++w) {
long long val1 = cur_dp_r[prev_base + w];
long long val2 = cur_dp_r[prev_base + w - h] + v;
cur_dp_r[cur_base + w] = (val1 > val2 ? val1 : val2);
}
}
// Combine the results from the left suffix and right prefix for crossing queries
for (const auto& q : cross_q) {
long long max_v = 0;
int l_base = (q.l - L) * m_plus_1;
int r_base = (q.r - mid) * m_plus_1;
for (int k = 0; k <= q.x; ++k) {
long long current_v = cur_dp_l[l_base + k] + cur_dp_r[r_base + (q.x - k)];
if (current_v > max_v) max_v = current_v;
}
results[q.id] = max_v;
}
}
// Recursively solve for queries strictly in the left or right halves
solve(L, mid, left_q);
solve(mid + 1, R, right_q);
}
int main() {
// Optimize I/O operations
ios::sync_with_stdio(false);
cin.tie(NULL);
if (!(cin >> N >> M >> Q)) return 0;
// Input items (1-indexed)
for (int i = 1; i <= N; ++i) {
cin >> items[i].h >> items[i].v;
}
// Input queries
vector<Query> queries(Q);
for (int i = 0; i < Q; ++i) {
cin >> queries[i].l >> queries[i].r >> queries[i].x;
queries[i].id = i;
}
// Solve using divide and conquer
solve(1, N, queries);
// Output all query results
for (int i = 0; i < Q; ++i) {
cout << results[i] << "\n";
}
return 0;
}
この解説は gemini-3-flash-thinking によって生成されました。
posted:
last update: