目次
Educational DP Contest I,J,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:]))
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の恩恵を享受できる、とのこと。
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])
K - Stones
問題
- $K$ 個の石が積まれた山があり、2人が交互に取っていく
- 一度に取る石の数は、$a_1,a_2,...,a_N$ のいずれかでないといけない
- これ以上操作を行えない状態で渡された方の負け
- 先手と後手、どちらが必勝か
解法
必敗パターンがある。必敗パターンというのは、「山がある個数で渡されたら、どう取ろうと、（その後相手が適切に取ることで）また必敗パターンが渡され続け、最終的に負ける」状態を指す。
例えば0個はこれ以上操作できないので必敗パターンである。
初期状態で必敗パターンなら後手必勝、それ以外は先手必勝である。
必敗パターンかどうかは、最小の必敗パターンである「山が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
x x x o o o o x x x o o o o x x x o o o o
(x: 必敗 o: 必敗ではない)
20は必敗パターンでは無いので、先手必勝
- 一度に3個、4個、10個のいずれかの個数取れる
- 12は、4個取って残り8個にして相手に渡せば、相手が[3 or 4]個取って[5 or 4]個で渡されても、次に4個取ることで[1 or 0]個で渡せ、必ず勝てる
- 16は、取れる選択肢(13, 12, 6) のいずれも必敗ではないので、必敗パターン
- どう取っても、上記のように相手が必ず勝てる手がある
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$ なので、間に合わない。
擬似コード
for i in 1..N:
for k in 0..a:
for j in 0..K:
dp[i][j+k] += dp[i-1][j]
圧縮
遷移
全体を把握するため、もう少し少ない例でやってみる。
↑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_3$ に着目すると、
- $j=0～3$ に $DP[2][0]=1$ を加算
- $j=1～4$ に $DP[2][1]=2$ を加算
- $j=2～5$ に $DP[2][2]=2$ を加算
- $j=3～6$ に $DP[2][3]=1$ を加算
という区間加算で表される。よって、いもす法による累積和で高速化できる。
- $DP[3][0]$に1、$DP[3][4]$に-1を加算
- $DP[3][1]$に2、$DP[3][5]$に-2を加算
- $DP[3][2]$に2、$DP[3][6]$に-2を加算
- $DP[3][3]$に1、$DP[3][7]$に-1を加算
- $DP[3]$の累積和を取る
ここで、正の加算の部分はそのまま$DP[2]$で流用でき、負の部分は$DP[2]$を$a_i+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])
このような行列同士の四則演算はNumPyを使いたくなるけど、一括で累積和を計算したらオーバーフローを起こすのか、WAになってしまった。
う～ん、$K$の上限が$10^6$で、各項が剰余を取って$10^9+7$未満なので、最大でも$10^{15}$強にしかならないはずなんだけどなあ。WAの原因は他にあるのだろうか。
