差分

このページの2つのバージョン間の差分を表示します。

この比較画面へのリンク

両方とも前のリビジョン前のリビジョン
次のリビジョン
前のリビジョン
最新のリビジョン両方とも次のリビジョン
programming_algorithm:contest_history:atcoder:2019:0106_educational_dp [2019/01/11] – [解法] ikatakosprogramming_algorithm:contest_history:atcoder:2019:0106_educational_dp [2019/01/18] ikatakos
行 1: 行 1:
-======Educational DP Contest I,K,L,Mメモ======+======Educational DP Contest I,J,K,L,Mメモ======
  
 [[https://atcoder.jp/contests/dp|Educational DP Contest / DP まとめコンテスト - AtCoder]] [[https://atcoder.jp/contests/dp|Educational DP Contest / DP まとめコンテスト - AtCoder]]
行 58: 行 58:
 print(sum(dp[n // 2 + 1:])) print(sum(dp[n // 2 + 1:]))
 </sxh> </sxh>
 +
 +===== J - Sushi =====
 +
 +[[https://atcoder.jp/contests/dp/tasks/dp_j|J - Sushi]]
 +
 +==== 問題 ====
 +
 +  * 寿司が乗った皿が $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だと制限時間が厳しい。
 +
 +Pythonでは変数に何でも入れられるため普段あまり意識しないが、データ型の概念はしっかりとある。
 +変数を扱うたびに「この変数の型はなんぞや」のチェックから入るのが、Pythonが便利な反面、遅い一因となっている(要出典)。
 +
 +PyPyでは、事前の型推論によりチェックを一部省略することで高速化を図っている部分があるが、処理の中でintもfloatも取り得る変数にしてしまうとその推論が上手く働かない。
 +
 +今回のように小数が入るとわかっている場合は、初期化する値も小数にしておけば、よりPyPyの恩恵を享受できる、とのこと。
 +
 +  * [[https://twitter.com/Kentarokumura/status/1084735265053147136|けんたろうさんのツイート: "提出 https://t.co/5JM02DmyNs EDPCのJ Sushiがpypy3でも通ったわ [0]による初期化を[0.0]にしただけなんだが・・・"]]
 +
 +<sxh python>
 +from collections import Counter
 +
 +n = int(input())
 +cnt = Counter(input().split())
 +c1, c2, c3 = cnt['1'], cnt['2'], cnt['3']
 +total = c1 + 2 * c2 + 3 * c3
 +c23 = c2 + c3
 +dp = [[[0.0] * (c3 + 1) for _ in range(c2 + c3 + 1)] for _ in range(n + 2)]  # ←ここを0で初期化するとTLE
 +
 +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])
 +</sxh>
 +
  
 ===== K - Stones ===== ===== K - Stones =====
行 151: 行 252:
 $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}$
  
行 212: 行 313:
  
 この、○個配ったときの各遷移の各 $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]
  
 ===圧縮=== ===圧縮===
programming_algorithm/contest_history/atcoder/2019/0106_educational_dp.txt · 最終更新: 2019/01/21 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0