AtCoder Regular Contest 028 D - 注文の多い高橋商店

問題

arc028.contest.atcoder.jp

解法

まず 10 点の解法を考えてみましょう。

これは, 各 Q に対して正直に dp すれば良いです。
dp[i][j] = (i 番目の種類までで合計 j 個の賞品を選ぶ方法) ということにすると, dp[i+1][j] = dp[i][j] + dp[i][j-1] + ... + dp[i][j-a[i]] で dp が求まります。ただ, これを正直にやると O(QNM^2) かかって若干危ないので, dpSum[j] みたいのを使って O(QNM) にしましょう。

const int MOD = 1e9+7;
int dp[111][111];
int dpSum[111];
 
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M, Q;
    cin >> N >> M >> Q;
    if (N > 100 || M > 100 || Q > 100) return 0;
    vector<int> a(N);
    for (int i = 0; i < N; i++) cin >> a[i];
    while (Q--) {
        int k, x;
        cin >> k >> x;
        k--;
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        int m = M-x;
        for (int i = 0; i < N; i++) {
            if (i == k) {
                for (int j = 0; j <= m; j++) {
                    dp[i+1][j] = dp[i][j];
                }
                continue;
            }
            for (int j = 0; j <= m; j++) dpSum[j+1] = (dpSum[j] + dp[i][j]) % MOD;
            for (int j = 0; j <= m; j++) {
                dp[i+1][j] = dpSum[j+1] - dpSum[max(0, j-a[i])];
                dp[i+1][j] = (dp[i+1][j]+MOD)%MOD;
            }
        }
        cout << dp[N][m] << endl;
    }
    return 0;
}

で, 次に 80 点解法を考えてみましょう。上の計算ではいちいち最初から計算していて, もったいない, という感じがします。そこで, いわゆる「戻すDP」をやることを考えます。
最初に dp[i][j] をちゃんと計算しておきます。各クエリ k x は, 「k 種類目は全く選ばずに M-x 個の商品を選ぶ方法」と同じになります。

dp[N][*] が与えられているとすると, k 種類目による dp の遷移は最後にやったとして(k = N-1 だったようなイメージ),
dp[N][0] = dp[N-1][0]
dp[N][1] = dp[N-1][0] + dp[N-1][1]
...

というようになっているので,

minus = 0 に初期化
dp[N-1][0] = dp[N][0] - minus, minus += dp[N-1][0]
dp[N-1][1] = dp[N][1] - minus, minus += dp[N-1][1]
...
のようにやっていけば良いです(dp[N-1][i] の i が a[N-1] 以上の時, minus -= dp[N-1][i-a[N-1]] することに注意。和は dp[N-1][i] + ... + dp[N-1][i-a[N-1]] なので)。

これで O(QM) で解けるようになりました。これで 80 点です。よく考えると, O(M) の計算で dp[N-1][*] がすべて計算できるので, 最初に前計算しておけば Q 個のクエリに対して O(1) で答えられるので満点が得られます。

const int MOD = 1e9+7;
int dp[2020][2020];
int dpSum[2020];
int ans[2020][2020];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M, Q;
    cin >> N >> M >> Q;
    vector<int> a(N);
    for (int i = 0; i < N; i++) cin >> a[i];
    dp[0][0] = 1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= M; j++) dpSum[j+1] = (dpSum[j]+dp[i][j]) % MOD;
        for (int j = 0; j <= M; j++) {
            dp[i+1][j] = dpSum[j+1] - dpSum[max(0, j-a[i])];
            dp[i+1][j] = (dp[i+1][j]+MOD)%MOD;
        }
    }
    for (int k = 0; k < N; k++) {
        int minus = 0;
        vector<int> dpdp(M+1);
        for (int i = 0; i <= M; i++) {
            dpdp[i] = (dp[N][i]-minus+MOD)%MOD;
            (minus += dpdp[i]) %= MOD;
            if (i >= a[k]) {
                (minus += (MOD-dpdp[i-a[k]])) %= MOD;
            }
        }
        for (int i = 0; i <= M; i++) ans[k][i] = dpdp[i];
    }
    while (Q--) {
        int k, x;
        cin >> k >> x;
        k--;
        cout << ans[k][M-x] << endl;
    }
    return 0;
}