差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:contest_history:atcoder:2019:0106_educational_dp [2019/01/11] – [解法] 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 \\ | ||
+ | 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) \\ | ||
+ | DP[i][j][k] &=& \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 ===== | ||
行 212: | 行 302: | ||
この、○個配ったときの各遷移の各 $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] | ||
===圧縮=== | ===圧縮=== |