再帰
考え方 回答例 考え方Editorial - freee Programming Contest 2023（AtCoder Beginner Contest 310） アライグマ「D問題はDFSの練習問題なのだ！ 1番目の選手から順に、何番目のチームにいれるかDFSで決めて、最後にチーム数をチェックすればいいのだ」 pic.…
解法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$…
考え方 回答例 考え方全通りの経路を再帰でみていけば良い．回答例 H, W = map(int, input().split()) A = [list(map(int, input().split())) for _ in range(H)] def f(x, y, seen): global ans if x == H - 1 and y == W - 1: ans += 1 return if x + 1 < …
考え方 回答例（スタックでDFS） 回答例（再帰でDFS） 考え方DFSでできる．頂点に入ったときにフラグを立て，頂点を抜けるときにフラグを消す．回答例（スタックでDFS）頂点に入ったときと抜けるときは，行きがけと帰りがけに対応する．スタックを使って行き…
解法1：メモ化再帰 考え方 回答例 解法1：メモ化再帰考え方modの逆数（modの逆数 - 競プロはじめました）さえわかれば，再帰的に計算できる． 回答例 import sys sys.setrecursionlimit(10 ** 6) from functools import lru_cache N, P = map(int, input().s…
考え方 回答例 考え方メモ化再帰する．Pythonではlru_cacheで簡単に実装できる． functools --- 高階関数と呼び出し可能オブジェクトの操作 — Python 3.11.0b5 ドキュメント AtCoder - 解法パターンの整理 - 競プロはじめました 回答例 from functools impor…
考え方 回答例 再帰関数 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}回答例再…
考え方 回答例 考え方トーナメントは再帰で一つ下の階層の勝者を求められる．解法2がきれい． Editorial - AtCoder Beginner Contest 188 （Pythonの例：Submission #19320967 - AtCoder Beginner Contest 188）回答例 N = int(input()) A = list(map(int, i…
【関連】 C - Large RPS Tournament 考え方 回答例 (Python) 回答例 (C++) 参考 考え方倍々に増えていく．逆に，再帰をすれば半分になっていく．$k \leq 10^{18} = 1000^{6} \sim 2^{60}$だから，60回再起すれば $S^{(t)}[0]$に行き着く（$S^{(t)}[0]$は$t$…
