ABC266E - Throwing the Die

考え方

残り$n$ターンのときの期待値を$f(n)$とすると，

\begin{aligned}
f(1) &= \sum_{i = 1}^{6} i \times \frac{1}{6} \\
f(n) &= \sum_{i = 1}^{6} \max\Bigl(i, f(n - 1) \Bigr) \times \frac{1}{6}
\end{aligned}

回答例

再帰関数

N = int(input())

def f(x):
    if x == 1:
        return sum(range(1, 7)) / 6
    ans = 0
    prev = f(x - 1)
    for i in range(1, 7):
        ans += i / 6 if prev < i else prev / 6
    return ans

print(f(N))

DP的

N = int(input())

prev = 0
for _ in range(N):
    ans = 0
    for i in range(1, 7):
        ans += max(i, prev)
    ans /= 6
    prev = ans

print(ans)