D - 均等な買い物 / Equal Shopping Editorial by admin
gemini-3-flash-thinking概要
\(N\) 軒の店から高橋君が \(P\) 軒、青木君が \(Q\) 軒選んで買い物をしたとき、二人の合計金額が一致するような計画の総数を求める問題です。クエリごとに店の買い物可能範囲 \([L_i, R_i]\) が更新されますが、制約の \(N \times M \le 2000\) および \(P, Q \le 3\)、さらに金額が最大 \(20\) と非常に小さいことを利用して、動的計画法（DP）を高速に回すことで解くことができます。
考察
1. 状態量の少なさに注目する
この問題の鍵は、各パラメータが非常に小さいことです。 - 高橋君と青木君が買い物をする店舗数 \(P, Q\) は最大 \(3\) です。 - 各店舗の金額 \(L_i, R_i\) は最大 \(20\) です。 - したがって、一人の合計金額の最大値は \(3 \times 20 = 60\) となります。
二人の合計金額が等しいという条件は、「（高橋君の合計）-（青木君の合計）= 0」 と言い換えることができます。この差の範囲は \(-60\) から \(60\) までのわずか \(121\) 通りしかありません。
2. 計算量の見積もり
クエリ回数 \(M\) と店舗数 \(N\) について、\(N \times M \le 2000\) という特殊な制約があります。これは、「クエリごとに全店舗を対象とした DP を一から解き直しても間に合う」 ことを示唆しています。 1回あたりの DP の計算量は、おおよそ \(O(N \times P \times Q \times (\text{金額の差の範囲}))\) となります。 最大ケースでも \(2000 \times 3 \times 3 \times 121 \approx 2.1 \times 10^6\) 程度の計算量であり、これを \(M\) 回ではなく全体を通して合計 \(N \times M\) のオーダーで処理できるため、十分に実行時間制限に間に合います。
アルゴリズム
動的計画法の定義
以下の状態をもつ DP を行います。
dp[p][q][diff]：
- \(p\)：高橋君が買い物をした店舗数 (\(0 \le p \le P\))
- \(q\)：青木君が買い物をした店舗数 (\(0 \le q \le Q\))
- \(diff\)：現在の合計金額の差（高橋 - 青木）。負の値を扱うため、オフセット（\(60\)）を加えて \(0 \sim 120\) の範囲で管理します。
遷移
各店舗 \(i\) について、以下の 3 つの選択肢があります。
- 誰も買い物をしない
next_dp[p][q][diff] += dp[p][q][diff]
- 高橋君が買い物をする
- 金額 \(v \in [L_i, R_i]\) を選ぶ。
next_dp[p+1][q][diff + v] += dp[p][q][diff]
- 青木君が買い物をする
- 金額 \(v \in [L_i, R_i]\) を選ぶ。
next_dp[p][q+1][diff - v] += dp[p][q][diff]
累積和による高速化
「金額 \(v \in [L_i, R_i]\) を選ぶ」という遷移を愚直にループで回すと計算量が増えますが、dp[p][q] の diff に関する累積和を事前に計算しておくことで、範囲 \([L_i, R_i]\) の加算を \(O(1)\) で行うことができます。
例えば、高橋君が買い物をした後の next_dp[p+1][q][s] は、直前の dp[p][q] において差が s - R[i] から s - L[i] の範囲にあるものの総和となります。
計算量
- 時間計算量: \(O(M \cdot N \cdot P \cdot Q \cdot S)\)
- ここで \(S\) は合計金額の差の範囲（約 \(120\)）です。
- \(N \times M \le 2000\) より、全体で約 \(4 \times 10^6\) 回程度の操作となり、高速です。
- 空間計算量: \(O(P \cdot Q \cdot S)\)
- DP テーブルを使い回す（インライン化する）ことで、店舗数 \(N\) に依存しないメモリ量で実装可能です。
実装のポイント
負のインデックス:
diffが負にならないようOFFSET = 60を足して管理します。累積和の活用: 範囲内の金額をすべて試す代わりに累積和を使うことで、内側のループを高速化しています。
初期化: 各クエリの開始時に DP テーブルを
0で初期化し、dp[0][0][OFFSET] = 1（誰も何も買っていない状態）からスタートします。ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
/**
* Problem: Equal Shopping
* We have N shops, each with a range [Li, Ri].
* Takahashi shops at exactly P shops, Aoki at exactly Q shops.
* No same shop for both.
* Total Takahashi sum = Total Aoki sum.
* We need to count the number of such plans after each of M updates.
*
* Constraints:
* N <= 2000, P <= 3, Q <= 3, M <= 1000, N * M <= 2000.
* Li, Ri <= 20.
*
* DP state: dp[p][q][s]
* p: number of shops Takahashi has used (0 to P)
* q: number of shops Aoki has used (0 to Q)
* s: current sum difference (Takahashi - Aoki), offset by 60 to handle negative values.
* Max sum for each is 3 * 20 = 60. Max difference is 60.
* The difference s ranges from -60 to 60, offset to 0 to 120.
*/
int main() {
// Fast I/O
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, P, Q, M;
if (!(cin >> N >> P >> Q >> M)) return 0;
// Current ranges for each shop
vector<int> L(N + 1), R(N + 1);
for (int i = 1; i <= N; ++i) {
cin >> L[i] >> R[i];
}
const int MOD = 998244353;
const int OFFSET = 60;
const int MAX_S = 120;
// Static DP tables to avoid re-allocation and keep memory usage low
static int dp[4][4][121];
static int next_dp[4][4][121];
static int S[122];
// Process M updates
for (int j = 0; j < M; ++j) {
int X, A, B;
cin >> X >> A >> B;
L[X] = A;
R[X] = B;
// Reset the DP table for the current configuration of shops
memset(dp, 0, sizeof(dp));
dp[0][0][OFFSET] = 1;
// Dynamic Programming over all shops
for (int i = 1; i <= N; ++i) {
// next_dp[p][q][s] starts as dp[p][q][s] (case where no one shops at shop i)
memcpy(next_dp, dp, sizeof(dp));
for (int p = 0; p <= P; ++p) {
for (int q = 0; q <= Q; ++q) {
// Optimization: Skip states that have no possible plans
bool all_zero = true;
for (int s = 0; s <= MAX_S; ++s) {
if (dp[p][q][s] != 0) {
all_zero = false;
break;
}
}
if (all_zero) continue;
// Compute prefix sums of dp[p][q][s] for range queries on sum difference
S[0] = 0;
for (int s = 0; s <= MAX_S; ++s) {
S[s + 1] = (S[s] + dp[p][q][s]) % MOD;
}
// Case: Takahashi shops at shop i
if (p + 1 <= P) {
for (int s = 0; s <= MAX_S; ++s) {
// s_new = s_old + v => s_old = s_new - v
// v in [L[i], R[i]] => s_old in [s - R[i], s - L[i]]
int low = s - R[i];
int high = s - L[i];
if (high < 0) continue;
if (low < 0) low = 0;
if (low <= high) {
int ways = (S[high + 1] - S[low] + MOD) % MOD;
next_dp[p + 1][q][s] = (next_dp[p + 1][q][s] + ways) % MOD;
}
}
}
// Case: Aoki shops at shop i
if (q + 1 <= Q) {
for (int s = 0; s <= MAX_S; ++s) {
// s_new = s_old - v => s_old = s_new + v
// v in [L[i], R[i]] => s_old in [s + L[i], s + R[i]]
int low = s + L[i];
int high = s + R[i];
if (low > MAX_S) continue;
if (high > MAX_S) high = MAX_S;
if (low <= high) {
int ways = (S[high + 1] - S[low] + MOD) % MOD;
next_dp[p][q + 1][s] = (next_dp[p][q + 1][s] + ways) % MOD;
}
}
}
}
}
// Move updated DP state to current DP
memcpy(dp, next_dp, sizeof(dp));
}
// Result is the number of plans where Takahashi used P shops, Aoki used Q shops, and sums were equal (diff=0).
cout << dp[P][Q][OFFSET] << "\n";
}
return 0;
}
この解説は gemini-3-flash-thinking によって生成されました。
posted:
last update: