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

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

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

考え方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 …

考え方 回答例 考え方アライグマ「E問題は、要するに「直接辺で繋がってないけど移動できる頂点の組の個数」を求める問題で、「移動できる頂点の組－辺の個数」なのだ！ 全部の頂点からDFSすれば求められるのだ！」— 競技プログラミングをするフレンズ (@kyo…

考え方 回答例 考え方UnionFind木（UnionFind木 - 競プロはじめました）で辺で結ばれる頂点をマージする．辺の数は，UnionFind木の親に対応付けて管理する．回答例 N, M = map(int, input().split()) E = [] for _ in range(M): u, v = map(int, input().spl…

考え方 回答例（UnionFind） 考え方辺を順番に見ていき，閉路でないならつなぐ．つなげない辺の数をカウントすれば良い． 閉路検出 - 競プロはじめました アライグマ「ABC288だったのだ！ C問題は、「辺0本から始めて、閉路にならないように何本追加できるか…

考え方 回答例（UnionFind） 考え方置換になっている組が存在するとダメなことがわかる．変更前と変更後の名前に辺を貼ったグラフで考えれば，閉路があるということ． 閉路検出 - 競プロはじめました アライグマ「D問題は、入力例2みたいに、変えたい名前が…

考え方 回答例（スタックでDFS） 回答例（再帰でDFS） 考え方DFSでできる．頂点に入ったときにフラグを立て，頂点を抜けるときにフラグを消す．回答例（スタックでDFS）頂点に入ったときと抜けるときは，行きがけと帰りがけに対応する．スタックを使って行き…

考え方 回答例 考え方原点から$\sqrt{M}$の距離にある点を求めておけば，任意の点についても原点をずらすだけで$\sqrt{M}$の距離にある点が求まる．半径$r$の円周上の格子点の個数は$2\pi r$以下なので，高々$O(N)$個．よって，全ての点を1回ずつみながら遷…

解法1 考え方 回答例 解法2：BFS 考え方 回答例 解法1考え方頂点を大きい方から見ていけば，「各街から到達できる街での最高値」がわかる． 求めたい答えは，「(街$i$から到達できる街での最高値) - (街$i$での購入価格)」．回答例 N, M = map(int, input().…

考え方 回答例 考え方「辺を切る問題」は，逆順に考えて「辺をつなぐ問題」に読み替える事を考えると，UnionFind（UnionFind木 - 競プロはじめました）が使える．UnionFindの初期化では， すべての発電所をつなぐ イベントで切られない辺をつなぐ とすればよ…

考え方 回答例 考え方$N$個の円を$1,...,N$の頂点に対応させ，円周が交わるなら辺を張った無向グラフを考える．こうすれば，$(s_{x}, s_{y})$に対応する頂点の集合から，$(t_{x}, t_{y})$に対応する頂点の集合へ到達できるかを判定する問題に帰着する．「中…

方法1 考え方 回答例 方法1考え方 各じゃがいもの種類$i$に対して，$i$スタートで重さの総和が$X$以上になるときの「個数」と「その次の箱に入るじゃがいもの種類$j$」を求めることができる． 上の結果から$i\to j$に辺を張った有向グラフを考えると，周期$N…

考え方 回答例 考え方ある文字列$S$に関する良いパス$A$がわかっていたとすると，そのパスの最後の頂点から隣の頂点に遷移してできたパス$A^{\prime}$は対応する文字列$S^{\prime}$に関する良いパス（の候補）である．よって，BFSで見ていけば良さそう． 最…

考え方 回答例 考え方答え（$S$）で二分探索（$O(\log \cdots)$）する．$S$を決めれば辺を$O(N^{2})$で張れる．スタート地点（$N$通り）を決めれば，BFS（$O(N^{2})$）で全ての頂点に行けるかどうかを計算できる．回答例すでに訪れた頂点はリストではなくset…

考え方 回答例 考え方入力例として， 3 3 1 2 2 3 3 1を考えると，DFSで辺を作れば$T_{1}$に，BFSで辺を作れば$T_{2}$になることがわかる．すでに頂点をつないだかどうかはsetで管理すれば良い．回答例スタックを使えばDFSになり，キューを使えばBFSになる．…

考え方 回答例 考え方全点対最短経路問題（すべての2頂点間の最短路を求める問題）が解けていれば， ある2頂点を結ぶ辺は， その2頂点を迂回する（複数の辺を使う）ことで，同じコスト「以下」で到達できるならなくてもよい（※1） ことからこの問題も解ける…

考え方 回答例 考え方アライグマ「E問題はサイクルを見つける問題なのだ！ 誰からも嫌われてない子にキャンディをあげていくと、嫌い関係がサイクルになってるところが残るのだ。サイクルのうち一番不満度が小さいところを諦めればいいのだ！」 pic.twitter.…

考え方 回答例 考え方制約から 距離0：1コ 距離1：1×3コ 距離2：1×3×3コ 距離3：1×3×3×3コ で，各クエリに対して40コ調べれば良いから，言われたとおり計算するだけでよい．回答例訪れた頂点の管理をするために全頂点の配列を用意するとTLEする（各頂点への…

考え方 回答例 考え方ある頂点から他の頂点への最短経路を求めると，最短経路からなる集合は木になる（最短経路木）． よって，最短経路で通る辺を列挙すれば良い．回答例 import heapq N, M = map(int, input().split()) G = [[] for _ in range(N)] E = {}…

考え方 回答例（再帰関数） 回答例（スタック） 考え方AtCoder Beginner Contest 220 - YouTube 頂点1からの答えがわかっていれば，頂点1に隣接する頂点$v$の答えは「(頂点1の答え) - ($v$の部分木の頂点数) + (N - $v$の部分木の頂点数)」で求められる．こ…

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

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

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

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

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

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