from 動的計画法
-
- なんらかの列を扱う問題で、その列の任意の要素を入れ替えても問題に影響ない場合、順序を持った列であることは問題に必要ではない
- 列の長さがNで、値域がMの時、順序付きではM
- 順序を奪うと多重集合になり、値ごとの個数で持てばよいのでN
- この問題の場合4通りの値を取るものが100個あるので素朴にやると4^100だが、これが100^4になって格段に狭くなる
- なんらかの列を扱う問題で、その列の任意の要素を入れ替えても問題に影響ない場合、順序を持った列であることは問題に必要ではない
-
- 「期待値DP」は「所要時間期待値DP」とでも言ったほうが明確になりそうな概念
- 状態を定義域として、確率を値とする、いわゆる「確率分布」が、1ステップの操作で確率的遷移をして別の分布に変わっていく時に、ある終状態に到達するまでの時間の期待値を求める問題。
- 素朴に1ステップの更新を繰り返すのではなく、値として「終状態に至るまでの時間の期待値」を持たせて、終状態ではその値が0であることから計算していって始状態の期待値を得るDP
- 「期待値DP」は「所要時間期待値DP」とでも言ったほうが明確になりそうな概念
-
もっと簡単な問題として「4つの飛び石があって、1/2の確率で次の石に移る、ゴールにたどり着く時間の期待値は？」を考える
- 所要時間の期待値を値とするDPを考える
- aから1ステップ後には、1/2でa、1/2でbにいる
- 確率を掛けて足し合わせたものが「aの1ステップ後の期待値」
- 式の両辺にaが出てくる
- 1/2の確率で自己遷移するから
- 整理すると、bからaを求める式が得られる
-
今回の問題における遷移
-
素朴に実装すると12TLE python
def solve(N, AS):
"void()"
from collections import Counter
count = Counter(AS)
expect = {}
expect[(0, 0, 0)] = 0
def f(a, b, c):
if (a, b, c) in expect:
return expect[(a, b, c)]
p = 1.0
if a > 0:
p += f(a - 1, b, c) * a / N
if b > 0:
p += f(a + 1, b - 1, c) * b / N
if c > 0:
p += f(a, b + 1, c - 1) * c / N
p *= N / (a + b + c)
# debug("f: a,b,c,p", a, b, c, p)
expect[(a, b, c)] = p
return p
return f(count[1], count[2], count[3])
少し書き直してAC python
def solve(N, AS):
from collections import Counter
count = Counter(AS)
expect = [[[-1] * (N + 1) for i in range(N + 1)] for j in range(N + 1)]
expect[0][0][0] = 0
def f(a, b, c):
p = N
if a > 0:
v = expect[a - 1][b][c]
if v == -1:
v = f(a - 1, b, c)
p += v * a
if b > 0:
v = expect[a + 1][b - 1][c]
if v == -1:
v = f(a + 1, b - 1, c)
p += v * b
if c > 0:
v = expect[a][b + 1][c - 1]
if v == -1:
v = f(a, b + 1, c - 1)
p += v * c
p /= (a + b + c)
# debug("f: a,b,c,p", a, b, c, p)
expect[a][b][c] = p
return p
return f(count[1], count[2], count[3])