【関連】 F - Valid payments 考え方 回答例 考え方まず，$X$を「$\{A_{i}\}_{i}$を使った進数」で表す．つまり，「$X$を最小の硬貨でピッタリ払うときに必要な各硬貨の枚数」を決める．これは，大きい硬貨から使えるだけ使えば良い．これにより，$X$を\begi…

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

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