差分
このページの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 | ||
---|---|---|---|
行 1: | 行 1: | ||
- | ======Educational DP Contest I, | + | ======Educational DP Contest I,K,L,Mメモ====== |
[[https:// | [[https:// | ||
行 37: | 行 37: | ||
| | ||
- | それぞれ縦の列を $C_i$ とすると、以下のようになる。 | + | それぞれの縦の列をまとめて1つの配列として |
$$C_{i}=C_{i-1}(1-p_i) + C_{i-1}' | $$C_{i}=C_{i-1}(1-p_i) + C_{i-1}' | ||
行 168: | 行 168: | ||
print(dp[0][n]) | print(dp[0][n]) | ||
</ | </ | ||
+ | |||
+ | ===== M - Candies ===== | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | ==== 問題 ==== | ||
+ | |||
+ | * $K$ 個のキャンディを、余りなく $N$ 人の子供に分ける | ||
+ | * 各子供には上限 $a_1, | ||
+ | * 配り方のパターン数を、$\mod{10^9+7}$ で求めよ | ||
+ | * $1 \le N \le 100$ | ||
+ | * $1 \le K \le 10^5$ | ||
+ | |||
+ | ==== 解法 ==== | ||
+ | |||
+ | 愚直にやる方法は基本的なDPで実装できるけど、遷移が多くてTLEになるので、上手く圧縮する。 | ||
+ | |||
+ | ===愚直な方法=== | ||
+ | |||
+ | ==データ== | ||
+ | $DP[i][j]=i$人目までの子供に、合計 $j$ 個の飴を配るパターン数 | ||
+ | |||
+ | として考える。$j$ の範囲は $0~K$ で用意することになる。 | ||
+ | |||
+ | ==初期状態== | ||
+ | $DP[0][0]=1$、後は0 | ||
+ | |||
+ | ==遷移== | ||
+ | $i-1$ までのDPが以下のような感じで、$a_i=2$ だった場合の遷移を考える。 | ||
+ | |||
+ | ↑j | | ||
+ | 5 | | ||
+ | 4 | | ||
+ | 3 | | ||
+ | 2 | 9 9 + 8 + 1 = 18 | ||
+ | 1 | 8 8 + 1 | ||
+ | 0 | 1 1 | ||
+ | ----+------------------------- | ||
+ | | | ||
+ | | ||
+ | | ||
+ | | ||
+ | |||
+ | この、○個配ったときの各遷移の各 $j$ につき、$DP[i-1]$ の参照と $DP[i]$ への加算が発生するので、$i-1$ から $i$ への遷移で計算が $K \times a_i$ 回発生することになる。それぞれ上限 $10^5$ なので、間に合わない。 | ||
+ | |||
+ | ===圧縮=== | ||
+ | |||
+ | ==遷移== | ||
+ | |||
+ | 全体を把握するため、もう少し少ない例でやってみる。 | ||
+ | |||
+ | ↑j | 1=1 | ||
+ | 5 | 1+2=3 | ||
+ | 4 | | ||
+ | 3 | | ||
+ | 2 | | ||
+ | 1 | | ||
+ | 0 | | ||
+ | ----+-----+-------+---------+----------- | ||
+ | | | ||
+ | |||
+ | /* | ||
+ | なんか規則性がありそう。 | ||
+ | |||
+ | 「$a_i$ による上限を設けない」場合との差を考えてみる。 | ||
+ | |||
+ | ↑j | ... | ||
+ | 7 | 1+2+2+1=6 | ||
+ | 6 | 1+2+2+1 | ||
+ | 5 | 1+2+2+1 | ||
+ | 4 | 1+2+2+1 | ||
+ | 3 | 1 | ||
+ | 2 | 2 | ||
+ | 1 | 2 | ||
+ | 0 | 1 | ||
+ | ----+----+-------------------+-------------------- | ||
+ | | i=2 | ||
+ | |||
+ | 上限を設けない場合、配り方のパターン数は、直前の状態(1, | ||
+ | |||
+ | よって、累積和でまとめてしまえば、1回の遷移にかかる計算を上限 $K$ 回に省略でき、間に合う。 | ||
+ | */ | ||
+ | |||
+ | $a_3$ に着目すると、 | ||
+ | |||
+ | * $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]$を$a_i+1$だけずらして正負逆転させたものに一致する。 | ||
+ | |||
+ | よって、計算量を上限$K$回の減算+累積和の計算に省略でき、間に合う。 | ||
+ | |||
+ | <sxh python> | ||
+ | from itertools import accumulate, starmap | ||
+ | from operator import sub | ||
+ | |||
+ | n, k = map(int, input().split()) | ||
+ | aaa = list(map(int, | ||
+ | MOD = 10 ** 9 + 7 | ||
+ | dp = [0] * (k + 1) | ||
+ | dp[0] = 1 | ||
+ | for a in aaa: | ||
+ | dp = list(accumulate(dp)) | ||
+ | dp[a + 1:] = starmap(sub, | ||
+ | dp = [x % MOD for x in dp] | ||
+ | print(dp[k]) | ||
+ | </ | ||
+ | |||
+ | このような行列同士の四則演算はNumPyを使いたくなるけど、一括で累積和を計算したらオーバーフローを起こすのか、WAになってしまった。 | ||
+ | |||
+ | う~ん、$K$の上限が$10^6$で、各項が剰余を取って$10^9+7$未満なので、最大でも$10^{15}$強にしかならないはずなんだけどなあ。WAの原因は他にあるのだろうか。 | ||
+ | |||