文書の過去の版を表示しています。


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

遷移

(i1)(i1) 枚目まで考慮済みで、ii 枚目の遷移を考える。

  • pipi の確率でそれぞれのjj が1枚増えて j+1j+1 になる
  • (1pi)(1pi) の確率でそれぞれの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=Ci1(1pi)+Ci1pi

ただし、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[ia1],DP[ia2],...,DP[iaN](ただし添字が負を除く)が全て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 とする
  • 先手はXY を最大化するように、後手はXYを最小化するように最善手を尽くす
  • XY はいくつになるか

解法

後手の行動原理は、つまり YX を最大化するということなので、要はどちらも「自分-相手が最大」となるように行動する。

なので仮に、同じ配列が先手に渡された時と後手に渡された時、2人が取る行動は(先手と後手を逆にして)全く同じとなる。(同じ配列が先手にも後手にも渡されることは同一ゲーム内ではありえないが、別のゲームの途中経過として)

これで、先手の番か後手の番か考えなくても、単に「その時の番である方が、相手の得点との差を最大化」するようにDPすればよいことになる。

データ

DP[l][r]=仮に数列{al,al+1,...,ar1} からゲームが始まった時、最終的な(先手-後手)はいくつになるか

初期条件

DP[i][i]=0、(i=0...N

遷移

lrの長さ(wとする)を、1からNまで順に増やしていく。

そのループの中で、l をずらしていき、満遍なく w におけるテーブルを埋める。

DP[l][r] があった時、先頭と末尾のどちらを取るかは、以下の大きい方となる。

  • DP[l1][r]+al
  • DP[l][r1]+ar1

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])

programming_algorithm/contest_history/atcoder/2019/0106_educational_dp.1547083849.txt.gz · 最終更新: by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0