ABC236 E - Throwing the Die
https://atcoder.jp/contests/abc266/tasks/abc266_e (opens in a new tab)
水色下位、期待値
各ターンにおいて、サイコロの投げる・投げないは自分に委ねられる。そのため、投げた場合の期待値・投げない場合の期待値を自分で計算し、値の大きい方をそのターンの期待値としてやることで、求める期待値を求める事が出来る。
条件付き期待値の知識が前提となる。 参考：期待値 DP を極めたい
直感的には次のような DP テーブルが思いつく。
dp[i][j] := iターン目にjの目が出る場合の期待値
ここで重要なポイントは各ターンで振りなおした場合、それまでの出目や期待値は関係ないという点である。
さて、dp[0][j] := 0ターン目においてjの目が出る場合の期待値ではサイコロを投げないので、スコアも何もなく、dp[0][j] = 0とするのが自然である。
次に、dp[1][j] := 1ターン目においてjの目が出る場合の期待値では、ただ 1 回の試行でjの目が出ることが確定している以上、期待値は 、dp[1][j] = jと定まる。（但し次のように考えても同じ結果が得られる。）
その後は次のように考える。
dp[2][1]は、2 回目のサイコロを投げる時に、1 の目が出る場合の期待値である。
振りなおした場合の期待値は （100%1 が出る。1 が出る事象しか考えない）
振りなおさない場合の期待値は、それまでの試行での期待値が答えとなるが、直前に振ったサイコロの目がkだった場合の条件付き期待値から、1 * 1/6 + 2 * 1/6 + ... + 6 * 1/6 = 3.5となる
大きい方の 3.5 を選択すればよい。
dp[3][5]は、3 回目のサイコロを投げる時に、5 の目が出る確率である。
振りなおした場合の期待値は
振りなおさない場合の期待値は、3.5 * 1/6 + 3.5 * 1/6 + ... + 6 * 1/6 = 4.25となる
大きい方の 5 を選択すればよい。
i = 0: [0, 0, 0, 0, 0, 0]
i = 1: [1, 2, 3, 4, 5, 6]
i = 2: [3.5, 3.5, 3.5, 4, 5, 6]
i = 3: [4.25, 4.25, 4.25, 4.25, 5, 6]
...
以上より、dp[i][j] = max(j, sum(dp[i-1][:]) * 1/6)と遷移式が定まる。
最終的にはi回目の試行でkが出る場合の条件付き期待値（sum(dp[i][:]) * 1/6)）が答えとなる。
実はもっと単純に求める事が出来るらしいが、初心者にはこれで十分であろう。
n = int(input())
dp = [[0] * 6 for _ in range(n + 1)]
for i in range(n):
for j in range(6):
dp[i + 1][j] = max(j + 1, sum(dp[i]) / 6)
print(sum(dp[n]) / 6)