dp 考え方 回答例 dp考え方操作が終わる方から決まるので，$N$から小さい順に考える． $\mathrm{dp}[i]=i$が出たあとでもらえる給料の期待値． $\mathrm{dp}[N]=A[N]$ $\displaystyle \mathrm{dp}[i] = A[i] + \sum_{j=i+1}^{N}\mathrm{dp} [j] \times \frac…

解法1：メモ化再帰 考え方 回答例 解法1：メモ化再帰考え方$f(n)=$1から初めて最終的にピッタリ$n$になる確率． $n=1$：$f(1)=1$ $n\neq 1$：$\displaystyle f(n) = \frac{1}{6} \sum_{k} f(n/\!/k)$（$(n\% k =0$かつ$k \in \{1,2,\ldots,6\})$） $n\neq 1$…

解法1：DP 考え方 回答例 解法2：再帰 考え方 回答例 解法1：DP考え方 後退解析をする（先手の勝ち負けが確定している最終状態から，逆に考えていく）． modの逆数：modの逆数 - 競プロはじめました youtu.be 回答例dp[i][j][k] = 先手がiにいて, 後手がjに…

解法1：メモ化再帰 考え方 回答例 解法1：メモ化再帰考え方modの逆数（modの逆数 - 競プロはじめました）さえわかれば，再帰的に計算できる． 回答例 import sys sys.setrecursionlimit(10 ** 6) from functools import lru_cache N, P = map(int, input().s…

考え方 回答例 再帰関数 DP的 考え方残り$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}回答例再…