ある区間から遷移する問題． 貰うDPなら累積和（ある区間からの遷移），配るDPならいもす法（ある区間への遷移）となる．個人的には，いもす法の方がわかりやすい． 方法1 (貰うDP & 累積和) 考え方 回答例 方法2 (配るDP & いもす法) 考え方 回答例 背景 方…

考え方 回答例 考え方エラトステネスの篩-likeな考え方で解ける． AtCoder - 解法パターンの整理 - 競プロはじめました以下のループは$O(N \log N)$であることがポイント． for i in range(N): for j in range(i, N + 1, i): # 処理 回答例 from collections…

考え方 回答例 考え方全部大文字かどうかは文字列.isupper()，全部小文字かどうかは文字列.islower()で判定できる．回答例 S = input() if len(S) != len(set(S)) or S.isupper() or S.islower(): exit(print('No')) print('Yes')

考え方 回答例 考え方以下と同じ考えで解ける． ABC246F - typewriter - 競プロはじめました文字列を26bitで管理し，$N$個のうちどの文字列を選ぶかをbit全探索する．すべての場合について，26文字が何回出てくるかカウントする．最後に，$K$回出てくる個数…

考え方 回答例 考え方左から見ていくと，コの字の辺を追加していく形になっている（初期状態のみ特殊）．各ステップで3辺のうちどれを切るかをきめるとdpで解ける．dp[i][j][k]を， 左から$i$番目まで決まっていて， $j$本の辺を取り除かれていて， 上と下が…

考え方（包除原理） 回答例 考え方（包除原理）dpで解いたが，組み合わせ＋包除原理でも解けそうと思いつつ実装できなかったのでメモ． Editorial - UNIQUE VISION Programming Contest 2022（AtCoder Beginner Contest 248）$\sum_{i=1}^{N} A_{i} = x$の場…

考え方 回答例 考え方$K=1$ならInfinityなので，その他の場合を考える．2点を決めれば傾きが決まる．このとき，何点通るかをカウントする．「$x$個の点が一直線上に乗っているとき，この直線はxx回カウントされる」という考え方ができる． ※これに気付かずに…

考え方 回答例 考え方区間$[1, N]$を，区間$[i, j]$で $X \leq A_{k} \leq Y \:(\forall k \in [i, j])$ を満たすものに分割して考える．あとはこの区間ごとに個数を数えれば良い．区間の左端を$L = i$に固定して，$X, Y$の両方が出てくるまで右端を一つずつ…

考え方 回答例 考え方 包除原理 Editorial - AtCoder Beginner Contest 246$k$段目のキーにどの文字が含まれるかを26bitで表す．キーの組み合わせをbit全探索する（1 〜1 ）．各キーの組み合わせにおいて，選んだ全てのキーに共通して含まれる文字種の数を求…

考え方 回答例 考え方逆順に操作していって$A$を空の数列にまで戻せるかを確かめる．flip回数の偶奇性を記録しておき，「操作Bを逆順に（できるだけ）行う→操作Aを逆順に行う」を繰り返す．flip回数が奇数なら0を1で置き換えて考えれば良い．操作Bを逆順に（…

解法1 考え方 回答例 解法1考え方$S_{1} = [A_{1},...,A_{K}]$と$S_{2} = [A_{K + 1},...,A_{N}]$の中から1つずつ$A_{i} $S_{2}$を前から見ていって，$A_{i - 1} > A_{i}$となる$i$があれば，$A_{i}$を$A_{i - 1}$で置き換える．こうしてできた配列を$S_{2}^…

単一始点 BFS ダイクストラ法 01BFS 単一始点ある頂点からの最短距離を求めたい場合．負の辺がないとする．未確定頂点のうち，最短距離のものは確定できる（他の頂点からの更新で小さくなりえない）．つまり，最短距離の未確定頂点の集合を取り出せるデータ…

ABC246E - Bishop 2 - 競プロはじめましたの類題． 考え方 回答例 考え方最短経路問題 - 競プロはじめました コストゼロで行けるものを優先してみればBFSで解ける． キューからpopしたものから更新される頂点はコスト＋1される．コストゼロで到達できる頂点…

【参考】最短経路問題 - 競プロはじめました 方法1 考え方 回答例 方法2 考え方 回答例 参考 方法1考え方ダイクストラ法と同じように，最短距離が未確定の頂点のうち，最小のものから確定させて更新すれば良さそう．1マスずつ動かす問題に帰着するにはどうす…

考え方 回答例 考え方式変形（因数分解など）で何かを見出そうとしても上手く行かない．2変数の問題は， 2次元平面で考える 1変数を固定して考える とよい．$0 \leq N \leq 10^{18}$だから，$0 \leq a,b \leq 10^{6}$である．よって，$a,b$の全探索はできな…

考え方 回答例 考え方以下がすごくわかりやすい．ゲームの後退解析（負けにしか遷移できない状態から考える）みたいな考え方． Editorial - AtCoder Beginner Contest 245 トポロジカルソートっぽく実装できる（トポロジカルソート - 競プロはじめました）．…

DAG（閉路のない有向グラフ）の辺が左から右に向くように，頂点を左から右に一列に並べる方法．「有向グラフをトポロジカルソートできなければ閉路がある」という使い方もできる．考え方 各頂点に入ってくる辺の本数（入次数，indegree）を配列indegに記録す…