概要

\(N\) 軒のお店から高橋君が \(P\) 軒、青木君が \(Q\) 軒を選び（重複なし）、それぞれのお店で許容範囲内の金額を決めたとき、両者の合計金額が等しくなるような計画の総数を、各更新後に求める問題です。

考察

重要な気づき

• 「高橋君の合計 = 青木君の合計」という条件は、「高橋君の合計 − 青木君の合計 = 0」と言い換えられます。
• 各お店について「スキップ」「高橋君が使う（差が増える）」「青木君が使う（差が減る）」の3択なので、DPで差を追跡すれば解けます。

差の範囲

• 高橋君は最大 \(P\) 軒で各最大 \(20\) 円使うので、差の最大値は \(P \times 20 = 60\)
• 青木君は最大 \(Q\) 軒で各最大 \(20\) 円使うので、差の最小値は \(-Q \times 20 = -60\)
• 差の範囲は \([-60, 60]\) で、高々 \(121\) 通りしかありません。

制約の活用

\(N \times M \leq 2000\) という制約から、各クエリごとにDPを最初から再計算しても間に合います。

アルゴリズム

各クエリ後に以下のDPを実行します。

状態: \(\mathrm{dp}[p][q][d]\) = 最初の何軒かを見終わった時点で、高橋君が \(p\) 軒、青木君が \(q\) 軒で買い物をし、（高橋君の合計）−（青木君の合計）= \(d - \mathrm{DOFF}\) である場合の数。

初期状態: \(\mathrm{dp}[0][0][\mathrm{DOFF}] = 1\)（差 \(0\)、誰もまだ買い物していない）

遷移: お店 \(i\)（範囲 \([L_i, R_i]\)）について： 1. スキップ: \(\mathrm{ndp}[p][q][d] \mathrel{+}= \mathrm{dp}[p][q][d]\) 2. 高橋君が購入（\(p < P\) のとき）: 金額 \(a \in [L_i, R_i]\) に対し \(\mathrm{ndp}[p+1][q][d+a] \mathrel{+}= \mathrm{dp}[p][q][d]\) 3. 青木君が購入（\(q < Q\) のとき）: 金額 \(a \in [L_i, R_i]\) に対し \(\mathrm{ndp}[p][q+1][d-a] \mathrel{+}= \mathrm{dp}[p][q][d]\)

答え: 全お店を処理後の \(\mathrm{dp}[P][Q][\mathrm{DOFF}]\)（差がちょうど \(0\)）

計算量

• 時間計算量: \(O(N \times M \times P \times Q \times D \times V)\)
  • \(D = 121\)（差の状態数）、\(V = 20\)（各お店の金額の幅の最大値）
  • \(N \times M \leq 2000\)、\(P, Q \leq 3\) なので、全体で約 \(2000 \times 9 \times 121 \times 20 \approx 4.4 \times 10^7\) 程度
• 空間計算量: \(O(P \times Q \times D)\)（DPテーブル2面分）

実装のポイント

• 差は負の値を取りうるため、オフセット \(\mathrm{DOFF} = 60\) を加えて配列の添字を非負にしています。\(\mathrm{DSIZE} = 121\) は \([-60, 60]\) の \(121\) 通りに対応します。

• DPの値が \(0\) のセルはスキップすることで定数倍を改善しています。

• 配列外アクセスを防ぐため、\(d + a < \mathrm{DSIZE}\) や \(d - a \geq 0\) のチェックを入れています。

• 各クエリで memset により DP テーブルを初期化し、毎回最初から計算し直しています（\(N \times M \leq 2000\) の制約で十分高速）。

  ソースコード

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

const int MOD = 998244353;
const int DOFF = 60;
const int DSIZE = 121;

long long dp[4][4][DSIZE];
long long ndp[4][4][DSIZE];

int main(){
    int N, P, Q, M;
    scanf("%d %d %d %d", &N, &P, &Q, &M);
    
    vector<int> L(N), R(N);
    for(int i = 0; i < N; i++){
        scanf("%d %d", &L[i], &R[i]);
    }
    
    for(int query = 0; query < M; query++){
        int x, a, b;
        scanf("%d %d %d", &x, &a, &b);
        x--;
        L[x] = a;
        R[x] = b;
        
        memset(dp, 0, sizeof(dp));
        dp[0][0][DOFF] = 1;
        
        for(int i = 0; i < N; i++){
            memset(ndp, 0, sizeof(ndp));
            int li = L[i], ri = R[i];
            
            for(int p = 0; p <= P; p++){
                for(int q = 0; q <= Q; q++){
                    for(int d = 0; d < DSIZE; d++){
                        if(dp[p][q][d] == 0) continue;
                        long long val = dp[p][q][d];
                        
                        // Skip
                        ndp[p][q][d] = (ndp[p][q][d] + val) % MOD;
                        
                        // Takahashi buys
                        if(p < P){
                            for(int am = li; am <= ri; am++){
                                int nd = d + am;
                                if(nd < DSIZE){
                                    ndp[p+1][q][nd] = (ndp[p+1][q][nd] + val) % MOD;
                                }
                            }
                        }
                        
                        // Aoki buys
                        if(q < Q){
                            for(int am = li; am <= ri; am++){
                                int nd = d - am;
                                if(nd >= 0){
                                    ndp[p][q+1][nd] = (ndp[p][q+1][nd] + val) % MOD;
                                }
                            }
                        }
                    }
                }
            }
            
            memcpy(dp, ndp, sizeof(dp));
        }
        
        printf("%lld\n", dp[P][Q][DOFF] % MOD);
    }
    
    return 0;
}

---

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