Union-Find上のDP
AtCoder
AtCoder600点
ABC-F
水色diff
マージテク
DP
Union-Find
Union-Findのマージ過程を表す木を考える
データ構造
クエリ処理問題
色に関する問題
Union-Find上のDP
Eulerツアー
in-place DP
クエリ先読み
中堅以上の典型要素を詰め合わせた教育的問題
マージテクを知らなくても雰囲気で通せるのかもしれない 問題へのリンク 問題概要 人の生徒がそれぞれクラス に所属している。 各生徒はそれぞれの家から出発したあと、他の生徒と合流を繰り返しながら学校へ向かう。一度合流した生徒が分かれることはない。…
Codeforces
Kruskal法
最小全域木
必要条件を列挙したら十分条件になる
条件の言い換え
グラフ
密グラフ
木
グラフの辺数を削減する
二乗の木DP
木DP
木DPのノード更新にDP
DP高速化:FFT
FFT
Union-Find
最適化テク:最適解の形を考える
各kに対して
数え上げ問題
グルーピング(算数)
グルーピングの数え上げ問題
探索順序を工夫して解く
DP
Union-Findのマージ過程を表す木を考える
最適化テク：変形しても悪化しない
全域木を考える
CodeforcesOthers
CodeforcesR2700
個人的要復習
Union-Find上のDP
思わず解きたくなる興味深い良問
【問題集】木DPのステップアップ
グラフの辺数削減テク:スーパー頂点を用いてsparseに
めちゃ好きだけど、実装重い 問題へのリンク 問題概要 頂点の重み付き無向完全グラフが与えられる。各 に対して、 頂点集合を 個の互いに disjoint な集合に分割する方法であって どの同族辺 (両端点が同一のグループに属する辺) の重みも、どの異族辺 (両端…
DP
Union-Find
グラフ
N個のペア値の問題
操作を逆順に見る
操作
ARC-F
AtCoder
AtCoder1000点
最小コスト
赤色diff
Union-Find上のDP
個人的要復習
価格に関する問題
Union-Findのマージ過程を表す木を考える
高度典型
最適化問題
本番中に解きたかった... ARC 098 F Donation 問題概要 N 頂点 M 辺の連結な単純無向グラフがあります。 頂点 i には二つの整数 Ai, Bi が定められています。 このグラフ上で次のようなゲームをします。 初めに、W 円を持った状態で好きな頂点に立つ。 ただ…
