Educational DP Contest / DP まとめコンテスト - M - Candies
組み合わせは苦手なんだって。。。
https://gyazo.com/8b036a2540d162ef31741aa3a2f5b6f2
考えたこと
dpテーブルをどう組むか..
2次元dpは使いそうだな
$ dp[i][j] として、$ iが先頭から何人目かでいいかな?
$ jはなんだろ。。全体の飴の数でいいかな?
つまり、$ dp[5][6] = 1~5までの子供で6つの飴を分け合う通り数
これなら、構築もおそらく$ 10^5 \times 10^2ですむはず
構築方法はどうするか?
$ dp[i][j] = dp[i-1][k-j] + 1 かな？
i=5, j=6, k=10として、5人で6つの飴を分け合うのは、4人で4つの飴を分け合う通り数に新しく1を足せばいい
あとは$ a[i] という制約もあるので、$ j が$ a[i]までたどり着いたら、そこ以降は同じ数にする的な
これで最後にi=nでj ~ kまでを全て足せばいける？
あと入力例2をみると、0通りの方法もあるから、それの対策も必要そう
dp構築前に、aのsumをとって、それがkより小さかったら例外処理でいいか
これで試してみたけど、ダメだった、解説を見よう。。
解説をみて
dpの考えはあってたけど、構築方法がまるっきりダメだった
$ dp(i, j) = dp(i - 1, j) + dp(i - 1, j - 1) + ... + dp(i - 1, j - a[i - 1] )
$ dp(i, j) = 1 $ j = 0の場合
$ dp(i, j) = 0 $ j < 0, i = 0 の場合
これだと、最悪で$ O(NK^2) で TLEになるらしい(毎回$ aを全て舐めないといけなく、aの最大値がKなので
何か対応が必要
式変形をするか
解説見たら、式変形がわかりやすかったので、それでやってみる
$ jに$ j-1を代入した式を考える
1. $ dp(i, j-1) = dp(i - 1, j-1) + dp(i - 1, j - 2) + ... + dp(i - 1, j - a[i - 1]-1 )
これを元の式から引きます
2. $ dp(i,j) - dp(i,j-1) = dp(i-1,j) + (dp(i-1,j-1) - dp(i-1,j-1)) + ... - dp(i-1, j-a[i-1]-1)
という形で、元の式の、$ dp(i-1,j) 1の式の $ dp(i-1, j-a[i-1]-1) を除いた共通部分が削除できる
あとは$ dp(i,j-1) を左辺から右辺に移行して
3. $ dp(i,j) = dp(i-1,j) + dp(i,j-1) - dp(i-1, j-a[i-1]-1)
とできた。これは計算量が$ O(NK) になるので間に合うはず
提出したコード
code: M.cpp
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i) #define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i) #define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i) #define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i) template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }
// dpnk=先頭からn人でk個を分け合うパターン数 ll mod_num = 1e9+7;
ll solve(int i, int j) {
if(j == 0) return 1;
if(j < 0) return 0;
if(i == -1) return 0;
if(dpij != -1) return dpij; return dpij = ((solve(i - 1, j) + solve(i, j - 1)) % mod_num - solve(i - 1, j - ai - 1) + mod_num) % mod_num; }
int main() {
int n,k; cin >> n >> k;
// dpテーブル初期化
EFOR(i,0,n) EFOR(j,0,k) dpij = -1; cout << solve(n-1, k) << endl;
return 0;
}
MODするとこで、何度かWA.iconがでた。MODうまくできないなあ..