解法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$…

考え方 回答例 考え方素数はエラトステネスの篩（ふるい）で列挙できる．$a^{5} $2^{2}\times 3 \times c^{2} \leq 10^{12}$より$c \leq 10^{6}/\sqrt{12} この範囲で全て調べれば良い．回答例 N = int(input()) MAX = 300000 prime = [] is_prime = [True] …

解法1 考え方 回答例 解法2：深さ優先探索 解法1考え方サイズ1のバツの中心をメモしておく．その後，それぞれの中心に対し，サイズがどれだけか調べる．回答例 H, W = map(int, input().split()) C = [list(input()) for _ in range(H)] N = min(H, W) ans =…

考え方 回答例 考え方隣接頂点との距離が1なので，BFSで最短距離を求められる． 最短経路問題 - 競プロはじめました各$p_{i}$からの各頂点の最短距離$d$を求めて，$d 各$i$について$p_{i}$からの最短距離が$d_{i}$に等しい頂点の集合をbとする．bがwhiteに包…

考え方 回答例 考え方両端にある0と1の位置を，二分探索の要領で隣り合うまで寄せていけば良い． 回答例 N = int(input()) zero = 1 one = N while one - zero > 1: mid = (zero + one) // 2 print('?', mid) ans = int(input()) if ans == 1: one = mid eli…

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

考え方 回答例 考え方 余りだけを管理する． $10^n$の計算は，先に計算しておくか，繰り返し二乗法（繰り返し二乗法 - 競プロはじめました）を使う． ※Python の剰余演算子%は，除数（割る方の数）と同じ符号の結果を返す．回答例 from collections import d…

考え方 回答例 考え方探索範囲を絞ったあと，全探索できる．アライグマ「D問題はa≦bの条件をつけて考えるのだ！ a≦ceil(√M)の範囲だけ調べればいいのだ。aを決めたら、abがギリギリM以上になるようなbを求めて、a,bがN以下なら答えの候補なのだ！」— 競技プ…

考え方 回答例 (Functional Graphであることを利用) 回答例 (UnionFind) 考え方$x$から$A_{x}$に辺を張った有向グラフを考える． グラフの閉路に含まれる頂点であることが，高橋君の勝つ必要十分条件． この頂点の個数をカウントすれば良い．アライグマ「E問…