ABC 222
Table of Contents
D - Between Two Arrays
$dp[i][x]$: $i$ 番目までの数が決まっており, $c_i = x$ のときの場合の数とする.
$c_i = x$ となるときの場合の数は, $c_{i-1} \leq x$ となる場合の数であるから
$\displaystyle dp[i][x] = \sum_{k = a_{i-1}}^x dp[i-1][k]$
これを元に naive に実装すると以下のようになる.
vector<vector<ll>> dp(n, vector<ll>(MAX, 0));
rep2(x, a[0], b[0] + 1) dp[0][x] = 1;
rep2(i, 1, n) {
rep2(x, a[i], b[i] + 1) {
rep2(k, a[i - 1], x + 1) {
dp[i][x] += dp[i - 1][k];
dp[i][x] %= MOD;
}
}
}
ll ans = 0;
rep(i, MAX) {
ans += dp[n - 1][i];
ans %= MOD;
}
cout << ans << endl;
しかしこれでは最大で $O(N \times 3000^2) = O(3000^3)$ の計算量がかかり制限時間に待ち合わない. TLE 提出コード
ここで $dp[i][x] = dp[i][x-1] + dp[i-1][x]$ ということに気づくと, $i$ 番目の計算では $dp[i][a_i]$ のときだけ for loop を回して, $a_i < x \leq b_i$ の範囲にある $x$ のときは すでに計算した結果を使い回せるということに気づく. よって DP テーブルの更新は以下のようになる.
vector<vector<ll>> dp(n, vector<ll>(MAX, 0));
rep2(x, a[0], b[0] + 1) dp[0][x] = 1;
rep2(i, 1, n) {
rep2(x, a[i], b[i] + 1) {
if (x == a[i]) {
rep2(k, a[i - 1], x + 1) {
dp[i][x] += dp[i - 1][k];
dp[i][x] %= MOD;
}
} else {
dp[i][x] = (dp[i - 1][x] + dp[i][x - 1]) % MOD;
}
}
}
ll ans = 0;
rep(i, MAX) {
ans += dp[n - 1][i];
ans %= MOD;
}
cout << ans << endl;