Educational DP Contest I,K,L,Mメモ

Educational DP Contest / DP まとめコンテスト - AtCoder

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_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の原因は他にあるのだろうか。