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