なもりグラフ
AtCoder
AtCoder400点
ABC-D
グラフ問題
DFS
サイクル
愚直シミュレーション
なもりグラフ
周期性に着目する
ダブリング
K回操作後の結果を求める
茶色diff
操作後の結果を求める問題
回操作した後の結果を求めよ (ただし がめちゃくちゃ大きい) という問題は、 同じ処理の繰り返しとなっているところを見抜く ダブリングする というパターンが多いと思われる。 問題へのリンク 問題概要 個の町 がある。町 からは、町 へテレポートできる。…
AtCoder
AtCoder800点
Greedy
マトロイド
グラフ問題
二次元情報を二部グラフにして考える
二部グラフ
Union-Find
Kruskal法
操作
操作の順序は関係ない
条件の言い換え
判定関数を考える
グリッド
なもりグラフ
操作後の結果の最適化問題
橙色diff
ARC-like
マトロイドだ!!!!!!! 問題へのリンク 問題概要 のボード上の 個のコマがあってそれぞれ重みがつけられている。同じマスに複数のコマが置かれていることもある。 今、各行から 1 個以下のコマを取り去る。次に各列から 1 個以下のコマを取り去る。 最…
こういう系の問題、なかなか提出が怖くなるやつ。こういうのは背水の陣状態じゃないと躊躇してしまいそう... 問題へのリンク 問題概要 頂点数 、辺数 の有向グラフが与えられる。 どの頂点から出る辺数も 1 どの頂点から出発しても必ずノード 1 (root) にた…
なもりなもり。サイクルが 1 個だけある連結グラフ、すなわち「木」に辺を 1 個くわえてできるグラフのことなん。 問題へのリンク 問題概要 N 頂点のなもりグラフが与えられる。以下の Q 個のクエリに答えよ。 2 頂点 a, b の間を分断するのに最小何個の辺を…