差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:contest_history:atcoder:2019:0106_educational_dp [2019/01/10] – [解法] ikatakos | programming_algorithm:contest_history:atcoder:2019:0106_educational_dp [2019/01/11] – [解法] ikatakos | ||
|---|---|---|---|
| 行 188: | 行 188: | ||
| ==データ== | ==データ== | ||
| - | DP[i][j]=iDP[i][j]=i人目までの子供に、jj 個の飴を配るパターン数 | + | DP[i][j]=iDP[i][j]=i人目までの子供に、合計 |
| として考える。jj の範囲は 0～K で用意することになる。 | として考える。j の範囲は 0～K で用意することになる。 | ||
| 行 212: | 行 212: | ||
| この、○個配ったときの各遷移の各 j につき、DP[i−1] の参照と DP[i] への加算が発生するので、i−1 から i への遷移で計算が K×ai 回発生することになる。それぞれ上限 105 なので、間に合わない。 | この、○個配ったときの各遷移の各 j につき、DP[i−1] の参照と DP[i] への加算が発生するので、i−1 から i への遷移で計算が K×ai 回発生することになる。それぞれ上限 105 なので、間に合わない。 | ||
| + | |||
| + | 擬似コード | ||
| + | for i in 1..N: | ||
| + | for k in 0..a: | ||
| + | for j in 0..K: | ||
| + | dp[i][j+k] += dp[i-1][j] | ||
| ===圧縮=== | ===圧縮=== | ||
| 行 229: | 行 235: | ||
| | | | | ||
| + | /* | ||
| なんか規則性がありそう。 | なんか規則性がありそう。 | ||
| 行 249: | 行 255: | ||
| よって、累積和でまとめてしまえば、1回の遷移にかかる計算を上限 K 回に省略でき、間に合う。 | よって、累積和でまとめてしまえば、1回の遷移にかかる計算を上限 K 回に省略でき、間に合う。 | ||
| + | */ | ||
| + | |||
| + | a3 に着目すると、 | ||
| + | |||
| + | * j=0～3 に DP[2][0]=1 を加算 | ||
| + | * j=1～4 に DP[2][1]=2 を加算 | ||
| + | * j=2～5 に DP[2][2]=2 を加算 | ||
| + | * j=3～6 に DP[2][3]=1 を加算 | ||
| + | |||
| + | という区間加算で表される。よって、いもす法による累積和で高速化できる。 | ||
| + | |||
| + | * DP[3][0]に1、DP[3][4]に-1を加算 | ||
| + | * DP[3][1]に2、DP[3][5]に-2を加算 | ||
| + | * DP[3][2]に2、DP[3][6]に-2を加算 | ||
| + | * DP[3][3]に1、DP[3][7]に-1を加算 | ||
| + | * DP[3]の累積和を取る | ||
| + | |||
| + | ここで、正の加算の部分はそのままDP[2]で流用でき、負の部分はDP[2]をai+1だけずらして正負逆転させたものに一致する。 | ||
| + | |||
| + | よって、計算量を上限K回の減算+累積和の計算に省略でき、間に合う。 | ||
| <sxh python> | <sxh python> | ||
| 行 265: | 行 291: | ||
| print(dp[k]) | print(dp[k]) | ||
| </ | </ | ||
| + | |||
| + | このような行列同士の四則演算はNumPyを使いたくなるけど、一括で累積和を計算したらオーバーフローを起こすのか、WAになってしまった。 | ||
| + | |||
| + | う～ん、Kの上限が106で、各項が剰余を取って109+7未満なので、最大でも1015強にしかならないはずなんだけどなあ。WAの原因は他にあるのだろうか。 | ||
| + | |||
| + | |||
| + | |||
