目次
文書の過去の版を表示しています。
Educational DP Contest I,K,L,Mメモ
I - Coins
問題
- $N$ 枚(奇数)のコイン
- 各コインの表の出る確率は、$p_1,p_2,...,p_N$ (裏はそれぞれの余事象)
- 同時に振った時、表が半分以上出る確率を求めよ
解法
データ
$DP[i][j]=i$ 枚目のコインまで考慮した時、$j$ 枚が表になる確率
初期条件
$DP[0][0]=1$、他は $0$
遷移
$(i-1)$ 枚目まで考慮済みで、$i$ 枚目の遷移を考える。
- $p_i$ の確率でそれぞれの$j$ が1枚増えて $j+1$ になる
- $(1-p_i)$ の確率でそれぞれの$j$ が変化せず $j$ のままになる
↑j| | ↗ 2| p1p2 → | ↗ ↗ 1| p1 → p1(1-p2) + (1-p1)p2 → | ↗ ↗ ↗ 0| 1 → (1-p1) → (1-p1)(1-p2)→ -+---------------------------------------- 0 1 2 →i
それぞれの縦の列をまとめて1つの配列として $C_i$ とすると、以下のようになる。
$$C_{i}=C_{i-1}(1-p_i) + C_{i-1}'p_i$$
ただし、$C'$ は、$C$ を1つ上にシフトした列とする。
Pythonなら、こういった、配列の各要素に同じ演算を適用する計算はNumPyで高速化できる。
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人が交互に取っていく
- 一度に取れる石の数は、数列 $a_1,a_2,...,a_N$ の項のいずれかでないといけない
- これ以上操作を行えない状態で渡された方の負け
- 先手と後手、どちらが必勝か
解法
必敗パターンというか、「山がある個数で渡されたら、どう取ろうと、その後相手が適切に取ることでまた必敗パターンが渡されることが繰り返され、最終的に負ける」状態がある。
初期状態で必敗パターンなら後手必勝、それ以外は先手必勝である。
必敗パターンかどうかは、最小の必敗パターンである「山が0個の状態」から $i=1 ... K$ まで積み上げて求めていく。
データ
$DP[i]=$山が $i$ 個の時、必敗パターンかどうか(bool)
初期条件
$DP[0]=True$
遷移
山が $i$ 個の状態から、$a_1,a_2,...,a_N$ 個のいずれかを取った状態の中に必敗パターンがあれば、必敗パターンでは無い。どの取り方をしても「必敗パターンでは無い状態」にしか出来なければ、必敗パターン。
言い換えると、$DP[i-a_1],DP[i-a_2],...,DP[i-a_N]$(ただし添字が負を除く)が全て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のように相手が必ず勝てる手がある
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
問題
- 数列 $\{a_1,a_2,...,a_N\}$ を使って2人が交互にゲームをする
- 自分の番では、数列の「先頭」か「末尾」のどちらかを選んで、配列から除き、自分の得点に加算する
- 数列が無くなったら終わり
- 最終的な先手の得点を $X$、後手の得点を $Y$ とする
- 先手は$X-Y$ を最大化するように、後手は$X-Y$を最小化するように最善手を尽くす
- $X-Y$ はいくつになるか
解法
後手の行動原理は、つまり $Y-X$ を最大化するということなので、要はどちらも「自分-相手が最大」となるように行動する。
なので仮に、同じ配列が先手に渡された時と後手に渡された時、2人が取る行動は(先手と後手を逆にして)全く同じとなる。(同じ配列が先手にも後手にも渡されることは同一ゲーム内ではありえないが、別のゲームの途中経過として)
これで、先手の番か後手の番か考えなくても、単に「その時の番である方が、相手の得点との差を最大化」するようにDPすればよいことになる。
データ
$DP[l][r]=$仮に数列$\{a_l,a_{l+1},...,a_{r-1}\}$ からゲームが始まった時、最終的な(先手-後手)はいくつになるか
初期条件
$DP[i][i]=0$、($i=0 ... N$)
遷移
$l~r$の長さ($w$とする)を、1から$N$まで順に増やしていく。
そのループの中で、$l$ をずらしていき、満遍なく $w$ におけるテーブルを埋める。
$DP[l][r]$ があった時、先頭と末尾のどちらを取るかは、以下の大きい方となる。
- $-DP[l-1][r]+a_l$
- $-DP[l][r-1]+a_{r-1}$
$w$ が1少ないDPを参照する時、入っている値は「今の後手が、もし“先手”だった時の“先手-後手”」なので、実際には後手-先手の値であるため、正負逆転させる。
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])
M - Candies
問題
- $K$ 個のキャンディを、余りなく $N$ 人の子供に分ける
- 各子供には上限 $a_1,a_2,...,a_N$ が決められており、$i$ 人目の子供には 0以上$a_i$以下の個数のキャンディをあげることができる
- 配り方のパターン数を、$\MOD{10^9+7}$ で求めよ
- $1 \le N \le 100$
- $1 \le K \le 10^5$
解法
愚直にやる方法は基本的なDPで実装できるけど、遷移が多くてTLEになるので、上手く圧縮する。
愚直な方法
データ
$DP[i][j]=i$人目までの子供に、$j$ 個の飴を配るパターン数
として考える。$j$ の範囲は $0~K$ で用意することになる。
初期状態
$DP[0][0]=1$、後は0
遷移
$i-1$ までのDPが以下のような感じで、$a_i=2$ だった場合の遷移を考える。
↑j | ... ... 5 | 25 25 +20 +15 = 60 4 | 20 20 +15 + 9 = 44 3 | 15 15 + 9 + 8 = 32 2 | 9 9 + 8 + 1 = 18 1 | 8 8 + 1 = 9 0 | 1 1 = 1 ----+------------------------- | i-1 i ↑2個配った時の遷移 ↑1個配ったときの遷移 ↑0個配ったときの遷移
この各遷移の各 $j$ につき、$DP[i-1]$ の参照と $DP[i]$ への加算が発生するので、$i-1$ から $i$ への遷移で計算が $K \times a_i$ 回発生することになる。それぞれ上限 $10^5$ なので、間に合わない。
圧縮
遷移
全体を把握するため、もう少し少ない例でやってみる。
↑j | 1=1 5 | 1+2=3 4 | 1+2+2=5 3 | 1=1 1+2+2+1=6 2 | 1+1=2 2+2+1 =5 1 | 1=1 1+1 =2 2+1 =3 0 | 1 1 =1 1 =1 1 =1 ----+-----+-------+---------+----------- | 0 a1=1 a2=2 a3=3
なんか規則性がありそう。
「$a_i$ による上限を設けない」場合との差を考えてみる。
↑j | ... 7 | 1+2+2+1=6 1+2+2+1=6 6 | 1+2+2+1 =6 2+2+1 =5 5 | 1+2+2+1 =6 2+1 =3 4 | 1+2+2+1 =6 1 =1 3 | 1 1+2+2+1 =6 2 | 2 2+2+1 =5 1 | 2 2+1 =3 0 | 1 1 =1 ----+----+-------------------+-------------------- | i=2 i=3 i=3における上限あるなしの差分
上限を設けない場合、配り方のパターン数は、直前の状態(1,2,2,1)の累積和となる。また、差分は、累積和をそのまま $a_i+1$ だけずらしたものとなる。
よって、累積和でまとめてしまえば、1回の遷移にかかる計算を $K$ 回に省略でき、間に合う。
from itertools import accumulate, starmap from operator import sub n, k = map(int, input().split()) aaa = list(map(int, input().split())) MOD = 10 ** 9 + 7 dp = [0] * (k + 1) dp[0] = 1 for a in aaa: dp = list(accumulate(dp)) dp[a + 1:] = starmap(sub, zip(dp[a + 1:], dp[:-a - 1])) dp = [x % MOD for x in dp] print(dp[k])