差分
このページの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/16] – [解法] ikatakos | ||
---|---|---|---|
行 1: | 行 1: | ||
- | ======Educational DP Contest I, | + | ======Educational DP Contest I,J, |
[[https:// | [[https:// | ||
行 58: | 行 58: | ||
print(sum(dp[n // 2 + 1:])) | print(sum(dp[n // 2 + 1:])) | ||
</ | </ | ||
+ | |||
+ | ===== J - Sushi ===== | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | ==== 問題 ==== | ||
+ | |||
+ | * 寿司が乗った皿が $N$ 個ある | ||
+ | * $i$ 番目の皿に乗った寿司は $A_i$ 個($A_i=1~3$) | ||
+ | * $1~N$ が均等に出るサイコロを振って、出た目の番号の皿の寿司を1個食べる | ||
+ | * ただし、出た目の番号の皿に寿司が残っていなかった場合は何もしない | ||
+ | * 全ての寿司を食べ終えるまでにサイコロを振る回数の期待値を求めよ | ||
+ | |||
+ | ==== 解法 ==== | ||
+ | |||
+ | 先ほどのコインと同じく確率で遷移するDPだが、状態の持たせ方と、自己遷移があるので式変形を工夫する必要がある。 | ||
+ | |||
+ | === データ === | ||
+ | |||
+ | $DP[i][j][k]=$皿に残る寿司が1個の皿が $i$ 個、2個の皿が $j$ 個、3個の皿が $k$ 個の時に、全て食べ終えるまでの回数の期待値 | ||
+ | |||
+ | 同じ個数の寿司が残る皿は区別しなくともよいので、個数でまとめる。 | ||
+ | |||
+ | 寿司は増えないので、$k$ の上限は初期状態での3枚皿の個数、$j$ の上限は初期状態での2枚皿と3枚皿の合計となる。 | ||
+ | |||
+ | === 遷移 === | ||
+ | |||
+ | \begin{eqnarray} | ||
+ | DP[i][j][k] &=& \frac{i}{N} DP[i-1][j][k] \\ | ||
+ | &+& \frac{j}{N} DP[i+1][j-1][k] \\ | ||
+ | &+& \frac{k}{N} DP[i][j+1][k-1] \\ | ||
+ | &+& \frac{N-i-j-k}{N} DP[i][j][k] \\ | ||
+ | &+& 1 | ||
+ | \end{eqnarray} | ||
+ | |||
+ | * 右辺の1行目は、寿司が1個残る皿の目を出して、1個の皿が1個減る | ||
+ | * 右辺の2行目は、寿司が2個残る皿の目を出して、2個の皿が1個減り、1個の皿が1個増える | ||
+ | * 右辺の3行目は、寿司が3個残る皿の目を出して、3個の皿が1個減り、2個の皿が1個増える | ||
+ | * 右辺の4行目は、寿司が0個残る皿の目を出して、何もしない | ||
+ | |||
+ | $DP[i][j][k]$ が両辺に出てくるのでこのままでは遷移できないため、移項する。 | ||
+ | |||
+ | \begin{eqnarray} | ||
+ | (1-\frac{N-i-j-k}{N})DP[i][j][k] &=& \frac{i+j+k}{N}DP[i][j][k] \\ | ||
+ | &=& \frac{i}{N} DP[i-1][j][k] \\ | ||
+ | &+& \frac{j}{N} DP[i+1][j-1][k] \\ | ||
+ | &+& \frac{k}{N} DP[i][j+1][k-1] \\ | ||
+ | &+& 1 | ||
+ | \end{eqnarray} | ||
+ | \begin{eqnarray} | ||
+ | DP[i][j][k] &=& \frac{N}{i+j+k}(\frac{i}{N} DP[i-1][j][k] \\ | ||
+ | &+& \frac{j}{N} DP[i+1][j-1][k] \\ | ||
+ | &+& \frac{k}{N} DP[i][j+1][k-1] \\ | ||
+ | &+& 1) \\ | ||
+ | &=& \frac{iDP[i-1][j][k] + jDP[i+1][j-1][k] + kDP[i][j+1][k-1] + N}{i+j+k} | ||
+ | \end{eqnarray} | ||
+ | |||
+ | 各添字が負にならないように注意して、これを埋めていく。 | ||
+ | |||
+ | $i+j+k$ が小さい方からループを回せばボトムアップでもできるし、このように+1、-1が入り交じってどの値から先に埋めれば良いか混乱する場合は、メモ化再帰でもよい。 | ||
+ | |||
+ | リスト参照が多いため、Python, | ||
+ | |||
+ | |||
+ | <sxh python> | ||
+ | # TLE | ||
+ | from collections import Counter | ||
+ | |||
+ | n = int(input()) | ||
+ | cnt = Counter(input().split()) | ||
+ | c1, c2, c3 = cnt[' | ||
+ | total = c1 + 2 * c2 + 3 * c3 | ||
+ | c23 = c2 + c3 | ||
+ | dp = [[[0] * (c3 + 1) for _ in range(c2 + c3 + 1)] for _ in range(n + 2)] | ||
+ | |||
+ | for k in range(1, n + 1): | ||
+ | still = n / k | ||
+ | for a1 in range(k, max(-1, 2 * k - total - 1, k - c23 - 1), -1): | ||
+ | dpap, dpac, dpan = dp[a1 - 1], dp[a1], dp[a1 + 1] | ||
+ | for a2 in range(min(k - a1, c2 + c3), max(-1, 3 * k - 2 * a1 - total - 1, k - a1 - c3 - 1), -1): | ||
+ | a3 = k - a1 - a2 | ||
+ | tmp = 0 | ||
+ | if a1: | ||
+ | tmp += dpap[a2][a3] * a1 | ||
+ | if a2: | ||
+ | tmp += dpan[a2 - 1][a3] * a2 | ||
+ | if a3: | ||
+ | tmp += dpac[a2 + 1][a3 - 1] * a3 | ||
+ | dpac[a2][a3] = tmp / k + still | ||
+ | print(dp[c1][c2][c3]) | ||
+ | </ | ||
+ | |||
===== K - Stones ===== | ===== K - Stones ===== | ||
行 151: | 行 243: | ||
$DP[l][r]$ があった時、先頭と末尾のどちらを取るかは、以下の大きい方となる。 | $DP[l][r]$ があった時、先頭と末尾のどちらを取るかは、以下の大きい方となる。 | ||
- | * $-DP[l-1][r]+a_l$ | + | * $-DP[l+1][r]+a_l$ |
* $-DP[l][r-1]+a_{r-1}$ | * $-DP[l][r-1]+a_{r-1}$ | ||
行 188: | 行 280: | ||
==データ== | ==データ== | ||
- | $DP[i][j]=i$人目までの子供に、$j$ 個の飴を配るパターン数 | + | $DP[i][j]=i$人目までの子供に、合計 |
として考える。$j$ の範囲は $0~K$ で用意することになる。 | として考える。$j$ の範囲は $0~K$ で用意することになる。 | ||
行 211: | 行 303: | ||
| | ||
- | この各遷移の各 $j$ につき、$DP[i-1]$ の参照と $DP[i]$ への加算が発生するので、$i-1$ から $i$ への遷移で計算が $K \times a_i$ 回発生することになる。それぞれ上限 $10^5$ なので、間に合わない。 | + | この、○個配ったときの各遷移の各 $j$ につき、$DP[i-1]$ の参照と $DP[i]$ への加算が発生するので、$i-1$ から $i$ への遷移で計算が $K \times a_i$ 回発生することになる。それぞれ上限 $10^5$ なので、間に合わない。 |
+ | |||
+ | 擬似コード | ||
+ | for i in 1..N: | ||
+ | for k in 0..a: | ||
+ | for j in 0..K: | ||
+ | dp[i][j+k] += dp[i-1][j] | ||
===圧縮=== | ===圧縮=== | ||
行 229: | 行 327: | ||
| | | | ||
+ | /* | ||
なんか規則性がありそう。 | なんか規則性がありそう。 | ||
行 248: | 行 346: | ||
上限を設けない場合、配り方のパターン数は、直前の状態(1, | 上限を設けない場合、配り方のパターン数は、直前の状態(1, | ||
- | よって、累積和でまとめてしまえば、1回の遷移にかかる計算を $K$ 回に省略でき、間に合う。 | + | よって、累積和でまとめてしまえば、1回の遷移にかかる計算を上限 |
+ | */ | ||
+ | |||
+ | $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> | <sxh python> | ||
行 265: | 行 383: | ||
print(dp[k]) | print(dp[k]) | ||
</ | </ | ||
+ | |||
+ | このような行列同士の四則演算はNumPyを使いたくなるけど、一括で累積和を計算したらオーバーフローを起こすのか、WAになってしまった。 | ||
+ | |||
+ | う~ん、$K$の上限が$10^6$で、各項が剰余を取って$10^9+7$未満なので、最大でも$10^{15}$強にしかならないはずなんだけどなあ。WAの原因は他にあるのだろうか。 | ||
+ | |||
+ | |||
+ |