AtCoder Educational DP Contest M問題解いてみた

今回の問題

問題文

$N$ 人の子供たちがいます。 子供たちには $1, 2, \ldots, N$ と番号が振られています。

子供たちは $K$ 個の飴を分け合うことにしました。
このとき、各 $i$ ($1 \leq i \leq N$) について、子供 $i$ が受け取る飴の個数は $0$ 以上 $a_i$ 以下でなければなりません。
また、飴が余ってはいけません。

子供たちが飴を分け合う方法は何通りでしょうか？
$10^9 + 7$ で割った余りを求めてください。
ただし、$2$ 通りの方法が異なるとは、ある子供が存在し、その子供が受け取る飴の個数が異なることを言います。

制約

• 入力はすべて整数である。
• $1 \leq N \leq 100$
• $0 \leq K \leq 10^5$

自分の回答

#include <bits/stdc++.h>
#include <atcoder/dsu>
using namespace std;
using namespace atcoder;
const int MOD = 1e9 + 7;
int main() {
    int N, K;
    cin >> N >> K;
    
    vector<int> a(N);
    for(int i = 0; i < N; i++) {
        cin >> a[i];
    }

    vector<int> dp(K + 1, 0);
    
    dp[0] = 1;

    for(int i = 0; i < N; i++) {
        
        vector<int> next_dp(K + 1, 0);
        
        vector<int> sum(K + 1);
        sum[0] = dp[0];
        for(int j = 1; j <= K; j++) {
            sum[j] = (sum[j-1] + dp[j]) % MOD;
        }

        
        for(int j = 0; j <= K; j++) {
           
            int R = j;
            int L = j - a[i];
            
            int val = sum[R];
            if (L > 0) {
               
                val = (val - sum[L-1] + MOD) % MOD; 
            }
            next_dp[j] = val;
        }
        
        dp = next_dp;
    }

    cout << dp[K] << endl;

    return 0;
}

解説

もともと、dp[i][j]をi人目までにj個配った時の場合の数にした。それを少し変形した。今回dpでそぎ落とした情報は誰に何個上げたかというものは必要なく、合計で何個上げたかが重要である。