差分

この文書の現在のバージョンと選択したバージョンの差分を表示します。

この比較画面にリンクする

両方とも前のリビジョン 前のリビジョン
次のリビジョン
前のリビジョン
programming_algorithm:contest_history:atcoder:2019:0106_educational_dp [2019/01/11]
ikatakos [解法]
programming_algorithm:contest_history:atcoder:2019:0106_educational_dp [2019/01/21] (現在)
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 =====
ライン 66: ライン 167:
  
   * $K$ 個の石が積まれた山があり、2人が交互に取っていく   * $K$ 個の石が積まれた山があり、2人が交互に取っていく
-  * 一度に取る石の数は、数列 ​$a_1,​a_2,​...,​a_N$ ​の項のいずれかでないといけない+  * 一度に取る石の数は、$a_1,​a_2,​...,​a_N$ のいずれかでないといけない
   * これ以上操作を行えない状態で渡された方の負け   * これ以上操作を行えない状態で渡された方の負け
   * 先手と後手、どちらが必勝か   * 先手と後手、どちらが必勝か
ライン 72: ライン 173:
 ==== 解法 ==== ==== 解法 ====
  
-必敗パターンという、「山がある個数で渡されたら、どう取ろうと、その後相手が適切に取ることでまた必敗パターンが渡されることが繰り返され、最終的に負ける」状態ある。+必敗パターンがある。必敗パターンというのは、「山がある個数で渡されたら、どう取ろうと、その後相手が適切に取ることでまた必敗パターンが渡され続け、最終的に負ける」状態を指す。 
 + 
 +例えば0個はこれ以上操作できないので必敗パターンである。
  
 初期状態で必敗パターンなら後手必勝、それ以外は先手必勝である。 初期状態で必敗パターンなら後手必勝、それ以外は先手必勝である。
ライン 85: ライン 188:
  
 === 遷移 === === 遷移 ===
-山が $i$ 個の状態から、$a_1,​a_2,​...,​a_N$ 個のいずれかを取った状態の中に必敗パターンがあれば、必敗パターンでは無いどの取り方をしても「必敗パターンでは無い状態」にしか出来なければ、必敗パターン+必敗かどうかは、相手に必敗パターンを渡すことが可能かどうかで決まる。 
 + 
 +  * 山が $i$ 個の状態から、$a_1,​a_2,​...,​a_N$ 個のいずれかを取った状態の中に必敗パターンがあれば、必敗パターンでは無い 
 +  * どの取り方をしても「必敗パターンでは無い状態」にしか出来なければ、必敗パターン
  
 言い換えると、$DP[i-a_1],​DP[i-a_2],​...,​DP[i-a_N]$(ただし添字が負を除く)が全てFalseなら、True。 言い換えると、$DP[i-a_1],​DP[i-a_2],​...,​DP[i-a_N]$(ただし添字が負を除く)が全てFalseなら、True。
ライン 91: ライン 197:
   K=20,  A={3, 4, 10}   K=20,  A={3, 4, 10}
   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
-  ​                    F+  ​                    
 +  (x: 必敗 ​ o: 必敗ではない)
   20は必敗パターンでは無いので、先手必勝   20は必敗パターンでは無いので、先手必勝
  
-  * 13は、4個取って残り9個にしたら、相手が[3 or 4]個取って[6 or 5]個で渡されても、次に4個取ることで必ず勝てる +  * 一度に3個、4個、10個のいずれかの個数取れる 
-  * 16は、取れる選択肢(13,​ 12, 6) のいずれもFalseなので、必敗パターンどう取っても、13のように相手が必ず勝てる手がある+  * 12は、4個取って残り8個にして相手に渡せば、相手が[3 or 4]個取って[5 ​or 4]個で渡されても、次に4個取ることで[1 or 0]個で渡せ、必ず勝てる 
 +  * 16は、取れる選択肢(13,​ 12, 6) のいずれも必敗ではので、必敗パターン 
 +    * どう取っても、上記のように相手が必ず勝てる手がある
  
 <sxh python> <sxh python>
ライン 151: ライン 260:
 $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}$
  
programming_algorithm/contest_history/atcoder/2019/0106_educational_dp.1547190256.txt.gz · 最終更新: 2019/01/11 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0