考え方 回答例 考え方まずは，$X$を偶数回云々を抜きにした，一段簡単な問題を考える．再帰で全ての道順を試して，$K$個の辺を通ったらreturnする方針では間に合わない（$\pmod{998244353}$を要求されていることからもわかるように）．そこで「ある頂点に行…

子ノードの情報を結合してソート 考え方 回答例 子ノードの情報を結合してソートEditorial - Denso Create Programming Contest 2022(AtCoder Beginner Contest 239)の方法． 毎回ソートして間に合う！考え方各頂点$v$に対し，「頂点$v$の部分木に含まれる頂…

考え方 回答例 考え方$0$$,1, 2, ..., N$を頂点とするグラフで考える．「$(l, r)$が与えられる」を「頂点$(l - 1)$と頂点$r$の間に（無向）辺が張られる」と読み替えれば，\begin{aligned} & a_{1} + a_{2} + \cdots a_{N} \text{が計算できる} \\ &\Leftrig…

「スコアの符号を変えればダイクストラが使える！」と思って嘘解法で通してしまいました．．．負の辺を含まない形に問題を修正しなければなりません． Editorial - AtCoder Beginner Contest 237 考え方 符号の反転 ポテンシャルの導入 解くべき問題 回答例 …

最小全域木（MST）については以下： 最小全域木（MST - Minimum Spanning Tree） - 競プロはじめましたUnionFindについては以下： UnionFind木 - 競プロはじめました 考え方 回答例 考え方クラスカル法を使う．以下のようにすれば良い．一度のクラスカル法で…

用語 アルゴリズム 例題 用語用語を整理しておきます（蟻本p. 99-）： 全域木：無向グラフの部分グラフで，任意の2頂点が連結である木． 最小全域木：辺のコストの和が最小の全域木． アルゴリズム プリム法：木$T$に，木$T$の頂点と木$T$に含まれない頂点を…

考え方 回答例 考え方 「重みなし」グラフの最短経路を求める問題になる→BFS 桁が減る操作はないので，10 ** 6を超えたら打ち切ることができる 回答例 from collections import deque a, N = map(int, input().split()) q = deque() q.append(1) dist = [-1]…

考え方 回答例 参考 考え方連結成分ごとの答えをかけ合わせれば良い．「どの頂点についても、その頂点から他の頂点に向かう辺がちょうど 1 本ずつ存在する」とき，頂点と辺は1セットと考えることができ (頂点数) = (辺数) という条件を満たす．また，「(頂点…

考え方 回答例 UnionFind DFS 考え方「$A$と$B$が隣あっている」を「$A$と$B$に辺がはられている」と読み替えればグラフの問題になる．横一列に並べられる条件は， すべての頂点から出ている辺の本数が2以下であること 閉路がないこと である．閉路検出は次…

無向グラフ UnionFind DFS 有向グラフ トポロジカルソート 無向グラフ【例】 ABC231D - Neighbors - 競プロはじめました UnionFindUnionFind（UnionFind木 - 競プロはじめました）を使えば，次で検出できる． 辺を張るたびに頂点をマージする 新たに$a,b$に…

実装 基本形 例題 AtCoder Typical Contest 001 参考 実装基本形 p = [-1] * (N + 1) # 親の配列 (いなければ-1), N要素 (1-indexed, P[0]はダミー) def root(x): # 親がいなければ自分(=根)を返す if p[x] < 0: return x # 自分の根 = 親の根 # & パス圧縮 …

考え方 回答例 注 考え方任意の頂点を根として考えて良い．根から順番に深さ方向に辺の色を決めていけば，まだ見ていない辺の色を決めるときに常に始点の色が定まった状態になっている．そこで，根から順番に，子ノードに辺を伸ばしていくことを考える．始点…

【関連問題】 ABC216D - Pair of Balls - 競プロはじめました 考え方「数字を頂点」，「順序関係を辺」と考えればグラフの問題になる．求められているものは，トポロジカルソートしたもので，辞書順で最小のものであるとわかる． （トポロジカルソートについ…

クラスカル法クラスカル法．コストの小さい順に辺を見ていき，閉路・二重辺でなければ追加する．UnionFindを使う．バラバラの状態からはじめ，辺の頂点が同じグループに属していないなら追加すれば良い．UnionFindコストが負の辺は取り除く意味がない（すべ…

【関連問題】 ABC223D - Restricted Permutation - 競プロはじめました 考え方 回答例 回答例 - カウンタで管理 回答例 - 1個ある集合・2個ある集合を別に持つ 回答例 - トポロジカルソート 考え方言われたとおりにやって間に合うというのに気付けるか，言わ…

解答の補足事項のみ書いておく．以下では，$l, m,n\in \mathbb{Z}$とする．はじめに$A_{i_{1}}$を選び，辺を張れるだけ張ったすると，$x$と同じ連結成分にできる頂点は\begin{aligned} & x + l A_{i_{1}} \pmod N \\ & \Leftrightarrow x + l A_{i_{1}} + m …