−目次
文書の過去の版を表示しています。
Educational DP Contest I,K,Lメモ
I - Coins
問題
- NN 枚(奇数)のコイン
- 各コインの表の出る確率は、p1,p2,...,pNp1,p2,...,pN (裏はそれぞれの余事象)
- 同時に振った時、表が半分以上出る確率を求めよ
解法
データ
DP[i][j]=iDP[i][j]=i 枚目のコインまで考慮した時、jj 枚が表になる確率
初期条件
DP[0][0]=1DP[0][0]=1、他は 00
遷移
(i−1)(i−1) 枚目まで考慮済みで、ii 枚目の遷移を考える。
- pipi の確率でそれぞれのjj が1枚増えて j+1j+1 になる
- (1−pi)(1−pi) の確率でそれぞれのjj が変化せず jj のままになる
↑j| | ↗ 2| p1p2 → | ↗ ↗ 1| p1 → p1(1-p2) + (1-p1)p2 → | ↗ ↗ ↗ 0| 1 → (1-p1) → (1-p1)(1-p2)→ -+---------------------------------------- 0 1 2 →i
それぞれの縦の列をまとめて1つの配列として CiCi とすると、以下のようになる。
Ci=Ci−1(1−pi)+C′i−1pi
ただし、C′ は、C を1つ上にシフトした列とする。
Pythonなら、こういった、配列の各要素に同じ演算を適用する計算はNumPyで高速化できる。
1 2 3 4 5 6 7 8 9 10 11 |
import numpy as np n = int ( input ()) ppp = list ( map ( float , input ().split())) dp = np.array([ 0.0 ] * (n + 1 ), dtype = np.float64) dp[ 0 ] = 1 for p in ppp: ndp = dp * ( 1 - p) ndp[ 1 :] + = dp[: - 1 ] * p dp = ndp print ( sum (dp[n / / 2 + 1 :])) |
K - Stones
問題
- K 個の石が積まれた山があり、2人が交互に取っていく
- 一度に取れる石の数は、数列 a1,a2,...,aN の項のいずれかでないといけない
- これ以上操作を行えない状態で渡された方の負け
- 先手と後手、どちらが必勝か
解法
必敗パターンというか、「山がある個数で渡されたら、どう取ろうと、その後相手が適切に取ることでまた必敗パターンが渡されることが繰り返され、最終的に負ける」状態がある。
初期状態で必敗パターンなら後手必勝、それ以外は先手必勝である。
必敗パターンかどうかは、最小の必敗パターンである「山が0個の状態」から i=1...K まで積み上げて求めていく。
データ
DP[i]=山が i 個の時、必敗パターンかどうか(bool)
初期条件
DP[0]=True
遷移
山が i 個の状態から、a1,a2,...,aN 個のいずれかを取った状態の中に必敗パターンがあれば、必敗パターンでは無い。どの取り方をしても「必敗パターンでは無い状態」にしか出来なければ、必敗パターン。
言い換えると、DP[i−a1],DP[i−a2],...,DP[i−aN](ただし添字が負を除く)が全てFalseなら、True。
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 T T T F F F F T T T F F F F T T T F F F F 20は必敗パターンでは無いので、先手必勝
- 13は、4個取って残り9個にしたら、相手が[3 or 4]個取って[6 or 5]個で渡されても、次に4個取ることで必ず勝てる
- 16は、取れる選択肢(13, 12, 6) のいずれもFalseなので、必敗パターン。どう取っても、13のように相手が必ず勝てる手がある
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
n, k = map ( int , input ().split()) aaa = list ( map ( int , input ().split())) dp = [ False ] * (k + 1 ) for i in range ( 1 , k + 1 ): win = None for a in aaa: j = i - a if j < 0 : break if dp[j] = = False : win = True break if win is None : win = False dp[i] = win print ( 'First' if dp[k] else 'Second' ) |
上記の解法とTrue/Falseが逆なので注意。
L - Deque
問題
- 数列 {a1,a2,...,aN} を使って2人が交互にゲームをする
- 自分の番では、数列の「先頭」か「末尾」のどちらかを選んで、配列から除き、自分の得点に加算する
- 数列が無くなったら終わり
- 最終的な先手の得点を X、後手の得点を Y とする
- 先手はX−Y を最大化するように、後手はX−Yを最小化するように最善手を尽くす
- X−Y はいくつになるか
解法
後手の行動原理は、つまり Y−X を最大化するということなので、要はどちらも「自分-相手が最大」となるように行動する。
なので仮に、同じ配列が先手に渡された時と後手に渡された時、2人が取る行動は(先手と後手を逆にして)全く同じとなる。(同じ配列が先手にも後手にも渡されることは同一ゲーム内ではありえないが、別のゲームの途中経過として)
これで、先手の番か後手の番か考えなくても、単に「その時の番である方が、相手の得点との差を最大化」するようにDPすればよいことになる。
データ
DP[l][r]=仮に数列{al,al+1,...,ar−1} からゲームが始まった時、最終的な(先手-後手)はいくつになるか
初期条件
DP[i][i]=0、(i=0...N)
遷移
l~rの長さ(wとする)を、1からNまで順に増やしていく。
そのループの中で、l をずらしていき、満遍なく w におけるテーブルを埋める。
DP[l][r] があった時、先頭と末尾のどちらを取るかは、以下の大きい方となる。
- −DP[l−1][r]+al
- −DP[l][r−1]+ar−1
w が1少ないDPを参照する時、入っている値は「今の後手が、もし“先手”だった時の“先手-後手”」なので、実際には後手-先手の値であるため、正負逆転させる。
1 2 3 4 5 6 7 8 9 10 |
n = int ( input ()) aaa = list ( map ( int , input ().split())) dp = [[ 0 ] * (n + 1 ) for _ in range (n + 1 )] for w in range ( 1 , n + 1 ): for l in range (n - w + 1 ): r = l + w dpl = - dp[l + 1 ][r] + aaa[l] dpr = - dp[l][r - 1 ] + aaa[r - 1 ] dp[l][r] = max (dpl, dpr) print (dp[ 0 ][n]) |