概要

各お店について「買わない」「高橋君が買う」「青木君が買う」のどれかを選び、高橋君が \(P\) 軒、青木君が \(Q\) 軒で買い物し、合計金額が等しくなる計画数を求めます。

更新後ごとに、お店を先頭から順に見る動的計画法で答えを再計算します。

考察

均等な買い物計画では、重要なのは次の \(3\) つです。

• 高橋君が買ったお店の数
• 青木君が買ったお店の数
• 高橋君の合計金額と青木君の合計金額の差

そこで、

\[ \text{差} = \text{高橋君の合計金額} - \text{青木君の合計金額} \]

として管理します。

最終的に求めたいのは、

• 高橋君が買ったお店数が \(P\)
• 青木君が買ったお店数が \(Q\)
• 差が \(0\)

となる場合の数です。

素朴に全ての買い物計画を列挙すると、各お店について複数の選択肢があるため非常に多くなり、間に合いません。

一方で、この問題では以下の制約が小さいです。

• \(P \leq 3\)
• \(Q \leq 3\)
• 購入金額は最大 \(20\)

したがって、それぞれの合計金額は最大でも

\[ 3 \times 20 = 60 \]

です。

よって、差は \(-60\) 以上 \(60\) 以下だけを考えれば十分です。

また、更新があるため高速な更新処理が必要に見えますが、制約に

\[ N \times M \leq 2000 \]

があります。

そのため、各更新後に最初から DP をやり直しても十分間に合います。

アルゴリズム

DP を次のように定義します。

\[ dp[p][q][d] \]

を、現在まで見たお店について、

• 高橋君が \(p\) 軒で買い物した
• 青木君が \(q\) 軒で買い物した
• 金額差が \(d - \text{OFF}\)

であるような計画数とします。

ここで、差は \(-60\) から \(60\) までなので、配列の添字として扱いやすくするために

\[ \text{OFF} = 60 \]

を足して管理します。

つまり、差 \(0\) は添字 \(60\) に対応します。

初期状態では、まだどのお店も見ておらず、誰も買い物していないので、

\[ dp[0][0][\text{OFF}] = 1 \]

です。

各お店 \(i\) について、範囲を \([L_i, R_i]\) とします。

現在の状態 \(dp[p][q][d]\) から、次の \(3\) 種類の遷移を行います。

1. 誰も買い物しない

\[ ndp[p][q][d] += dp[p][q][d] \]

2. 高橋君が金額 \(a\) で買い物する

\(p < P\) のとき、各 \(a \in [L_i, R_i]\) について、

\[ ndp[p+1][q][d+a] += dp[p][q][d] \]

高橋君の合計金額が増えるので、差も \(a\) 増えます。

3. 青木君が金額 \(a\) で買い物する

\(q < Q\) のとき、各 \(a \in [L_i, R_i]\) について、

\[ ndp[p][q+1][d-a] += dp[p][q][d] \]

青木君の合計金額が増えるので、差は \(a\) 減ります。

全てのお店を処理したあと、答えは

\[ dp[P][Q][\text{OFF}] \]

です。

これは、高橋君が \(P\) 軒、青木君が \(Q\) 軒で買い物し、差が \(0\)、つまり合計金額が等しい計画数を表します。

各更新では、指定されたお店の区間 \([L_X, R_X]\) を新しい \([A, B]\) に置き換えたあと、この DP を最初から計算し直します。

計算量

購入金額の候補数を \(V = 20\)、差の状態数を

\[ D = 121 \]

とします。

• 時間計算量: \(O(M \times N \times (P+1)(Q+1) \times D \times V)\)
• 空間計算量: \(O((P+1)(Q+1) \times D)\)

\(P,Q,V,D\) はすべて小さい定数であり、さらに \(N \times M \leq 2000\) なので十分高速です。

実装のポイント

• 差は負になる可能性があるため、添字として使うために OFF = 60 を足して管理します。

  • 差 \(0\) は OFF
  • 差 \(+a\) は OFF + a
  • 差 \(-a\) は OFF - a

• 各お店について ndp を新しく作り、そこへ遷移します。

  • これにより、同じお店で高橋君と青木君が同時に買うような遷移を防げます。

• 答えは非常に大きくなる可能性があるため、常に \(998244353\) で割った余りを取ります。

• 更新は累積的なので、配列 L, R を直接書き換えてから DP を実行します。

  ソースコード

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

static const int MOD = 998244353;
static const int OFF = 60;
static const int W = OFF * 2 + 1;

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

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

    vector<int> L(N), R(N);
    for (int i = 0; i < N; i++) cin >> L[i] >> R[i];

    auto solve = [&]() -> int {
        int dp[4][4][W] = {};
        int ndp[4][4][W] = {};

        dp[0][0][OFF] = 1;

        for (int i = 0; i < N; i++) {
            memset(ndp, 0, sizeof(ndp));

            for (int p = 0; p <= P; p++) {
                for (int q = 0; q <= Q; q++) {
                    for (int d = 0; d < W; d++) {
                        int val = dp[p][q][d];
                        if (!val) continue;

                        int &none = ndp[p][q][d];
                        none += val;
                        if (none >= MOD) none -= MOD;

                        if (p < P) {
                            for (int a = L[i]; a <= R[i]; a++) {
                                if (d + a < W) {
                                    int &to = ndp[p + 1][q][d + a];
                                    to += val;
                                    if (to >= MOD) to -= MOD;
                                }
                            }
                        }

                        if (q < Q) {
                            for (int a = L[i]; a <= R[i]; a++) {
                                if (d - a >= 0) {
                                    int &to = ndp[p][q + 1][d - a];
                                    to += val;
                                    if (to >= MOD) to -= MOD;
                                }
                            }
                        }
                    }
                }
            }

            memcpy(dp, ndp, sizeof(dp));
        }

        return dp[P][Q][OFF];
    };

    for (int j = 0; j < M; j++) {
        int X, A, B;
        cin >> X >> A >> B;
        --X;
        L[X] = A;
        R[X] = B;
        cout << solve() << '\n';
    }

    return 0;
}

---

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