考え方 回答例 考え方modの逆数（modの逆数 - 競プロはじめました）さえわかれば，普通のDP．回答例dはゴールまでの距離． nxt(次の位置) = move(今いる位置，出目) dp[i回目に][位置jにいる] 確率． N, M, K = map(int, input().split()) mod = 998244353 i…

考え方 回答例 考え方メモ化再帰する．Pythonではlru_cacheで簡単に実装できる． functools --- 高階関数と呼び出し可能オブジェクトの操作 — Python 3.11.0b5 ドキュメント AtCoder - 解法パターンの整理 - 競プロはじめました 回答例 from functools impor…

Decimal 例題 自分で実装する 例題 参考記事 Decimaldecimal --- 十進固定及び浮動小数点数の算術演算 — Python 3.10.6 ドキュメント例題B - Broken Rounding from decimal import Decimal, ROUND_HALF_UP X, K = map(int, input().split()) for i in range(…

周回回数を効率的に求め，残り$N$個以下になったら愚直に数えることを考える． 解法1：二分探索 考え方 回答例 解法2：シミュレーション 考え方 回答例 解法1：二分探索考え方Editorial - TOYOTA MOTOR CORPORATION Programming Contest 2022(AtCoder Beginn…

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

考え方 回答例 参考 考え方Editorial - AtCoder Beginner Contest 272 $N$個の整数に含まれない最小の非負整数は$0,1,...,N$のいずれか．各$i$を考える．$m$回目の操作のあとで$A_{i} \in [0, N]$となる$m$の個数は，\begin{aligned} & 0 \leq A_{i} + m i \…

考え方 回答例 考え方原点から$\sqrt{M}$の距離にある点を求めておけば，任意の点についても原点をずらすだけで$\sqrt{M}$の距離にある点が求まる．半径$r$の円周上の格子点の個数は$2\pi r$以下なので，高々$O(N)$個．よって，全ての点を1回ずつみながら遷…

考え方 回答例 考え方dp[i][j] = iコ目まですべてを使ってjにできる方法（HとTの文字列）．i + 1に遷移できるためには，dp[i][]が$i$コの文字列からなる必要がある．回答例初期化ではダミーの文字$X$を入れることで，遷移できるものを区別した． N, S = map(…

解法1：二分探索 考え方 回答例 解法2：消費する本の数に着目 考え方 解法1：二分探索考え方「$x$巻まで読むことができる」は， $x$巻以下で持っている本の種類の数 (↑以外の本の数) // 2 の和が$x$以上であることと同値．Editorial - KYOCERA Programming C…