AtCoder
解法1： 考え方 解法1：考え方（解放のみメモ） N〜1の橋を封鎖したときのツアーの長さを基準にして，順番に隣の橋を封鎖した場合を差分で計算する．$a これに気づくとimos法が使える．アライグマ「D問題は、1とNを結ぶ橋を封鎖したときを基準にすると、「ど…
解法1：dp 考え方 回答例 解法1：dp考え方Editorial - HHKB Programming Contest 2023(AtCoder Beginner Contest 327)アライグマ「E問題はDPなのだ！ 分子のところだけ見ると、コンテストに参加するたびに、新分子＝パフォ＋旧分子×0.9になるのだ。残りはkだ…
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：頂点を倍にする考え方フェネック「いま車に乗ってるのか電車に乗ってるのかで頂点を倍にして、1つのグラフで1回だけダイクストラをする解法もあるよ。ちょっと違うけどこういうイメージだねー」https://t.co/9au…
考え方 回答例 考え方DFSで帰りがけを見る． スタックで実装できる． 【関連】 非再帰 Euler Tour を Python でやる - Qiita ABC284E - Count Simple Paths - 競プロはじめました回答例DFSをするためのseenと，すでにansに加えたかを管理するseen2を使った．…
考え方 回答例 考え方止まるマスと訪れたマスを別に管理してBFSをする．回答例 from collections import deque N, M = map(int, input().split()) S = [input() for _ in range(N)] seen = [[False]*M for _ in range(N)] stop = [[False]*M for _ in range(…
考え方 回答例 考え方Editorial - freee Programming Contest 2023（AtCoder Beginner Contest 310） アライグマ「D問題はDFSの練習問題なのだ！ 1番目の選手から順に、何番目のチームにいれるかDFSで決めて、最後にチーム数をチェックすればいいのだ」 pic.…
考え方 回答例 考え方使ったクーポンの$D_{i}$の総和を最大化する．クーポン$i$は「(定価)$\geq L_{i}$」を満たす商品に適用できる．同じクーポンならなるべく定価が小さいものに使ったほうが有利． 商品の定価を小さい順に見ていき 定価$p$の商品に対して$S…
考え方 回答例 考え方$S_{i}S_{j}S_{k}=$MEXとなるとき，$(A_{i}, A_{j}, A_{k})$の値の組は$3^{3}$通りある． それぞれの出現回数$\mathrm{cnt}$をカウントできれば，答えは\begin{aligned} \sum_{a,b,c} \mathrm{cnt}(a,b,c)\times \mathrm{mex}(a,b,c) \e…
考え方 回答例 考え方アライグマ「D問題はスタックなのだ！ 「前から見て')'が来たら、直前の'('からここまでを削除」とすればいいのだ。今までに'('が何個あるかを覚えておいて、1個以上のときだけ'('を探せば全体でO(N)になるのだ！」— 競技プログラミング…
考え方 回答例 考え方A, B, Xは少なくとも1つの黒マスを含むため，A, BはXと必ず重なる． Xの左上のマスの座標を(9, 9)として，A, Bそれぞれの左上のマスが(0, 0)〜(19, 19)となる場合を全探索する．全部の黒マスを使ったかどうかをsetで管理する．回答例 HA…
解法1：DP 考え方 回答例 解法1：DP考え方dp[i][j] = i品目を食べて状態がj(0:お腹を壊していない/1:壊している)のときの食べた料理の美味しさの総和の最大値回答例 N = int(input()) XY = [list(map(int, input().split())) for _ in range(N)] dp = [[0]*2…
解法1：DP 考え方 回答例 解法1：DP考え方dp[i][j] = i個目まで決めて，capslockON(j=1), OFF(j=0)のときの最小値回答例 X, Y, Z = map(int, input().split()) S = input() dp = [[0]*2 for _ in range(len(S) + 1)] dp[0][1] = 1 << 60 for i in range(len(…
解法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問…
解法1： 考え方 回答例 解法1：考え方各数字（0〜9）の出現回数偶奇性が$l -1$と$r$で一致する場合に「嬉しい列」となる． よって，bitで$i$文字目までの0〜9の出現回数の偶奇性だけを抑えておく．回答例$l - 1 = 0$の場合をd[0] = 1として考える． from col…
考え方1 考え方2 考え方1閉路ができたかどうかをUnionFind木で見る（閉路検出 - 競プロはじめました）． N, M = map(int, input().split()) # --- UnionFind --- p = [-1] * (N + 1) def root(x): if p[x] < 0: return x p[x] = root(p[x]) return p[x] def …
考え方 回答例 考え方全通りの経路を再帰でみていけば良い．回答例 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 < …
考え方 回答例 考え方アライグマ「E問題は、要するに「直接辺で繋がってないけど移動できる頂点の組の個数」を求める問題で、「移動できる頂点の組－辺の個数」なのだ！ 全部の頂点からDFSすれば求められるのだ！」— 競技プログラミングをするフレンズ (@kyo…
考え方 回答例 考え方UnionFind木（UnionFind木 - 競プロはじめました）で辺で結ばれる頂点をマージする．辺の数は，UnionFind木の親に対応付けて管理する．回答例 N, M = map(int, input().split()) E = [] for _ in range(M): u, v = map(int, input().spl…
考え方 回答例 考え方$1\leq n \leq N$を満たす$n$の約数はそれぞれ$O(\sqrt{n})$で求められる（Pythonで蟻本2-6 - 数学的な問題を解くコツ - 競プロはじめました）．よって，$1\leq n \leq N$なるすべての$n$に対して約数を調べる計算量は$O(N\sqrt{N})$で…
考え方 回答例（UnionFind） 考え方辺を順番に見ていき，閉路でないならつなぐ．つなげない辺の数をカウントすれば良い． 閉路検出 - 競プロはじめました アライグマ「ABC288だったのだ！ C問題は、「辺0本から始めて、閉路にならないように何本追加できるか…
考え方 回答例（UnionFind） 考え方置換になっている組が存在するとダメなことがわかる．変更前と変更後の名前に辺を貼ったグラフで考えれば，閉路があるということ． 閉路検出 - 競プロはじめました アライグマ「D問題は、入力例2みたいに、変えたい名前が…
