CodeforcesR2700
Codeforces
CodeforcesCombined
CodeforcesR2700
グラフ
二部グラフ判定
二部グラフ
牛ゲー
最適化テク:緩和しても良い
Floyd-Warshall法
最短路問題
復元
どれか1つ求める
Yes/No判定問題
必要条件を列挙したら十分条件になる
個人的要復習
差分制約系
最大値と最小値の差を扱う問題
ある量を固定して考える
最大値の最大化
なんとなくできそうだけどできないみたいな問題だった。そうか、牛ゲーに帰着すれば明快だ... 問題へのリンク 問題概要 頂点数 、辺数 の連結グラフが与えられる。いくつかの辺は無向辺であり、いくつかの辺は有向辺である。 各頂点 に 0 以上の整数値 を割…
Codeforces
Kruskal法
最小全域木
必要条件を列挙したら十分条件になる
条件の言い換え
グラフ
密グラフ
木
グラフの辺数を削減する
二乗の木DP
木DP
木DPのノード更新にDP
DP高速化:FFT
FFT
Union-Find
最適化テク:最適解の形を考える
各kに対して
数え上げ問題
グルーピング(算数)
グルーピングの数え上げ問題
探索順序を工夫して解く
DP
Union-Findのマージ過程を表す木を考える
最適化テク:解を変形していく(最適性を失わずに)
全域木を考える
CodeforcesOthers
CodeforcesR2700
個人的要復習
Union-Find上のDP
思わず解きたくなる興味深い良問
【問題集】木DPのステップアップ
グラフの辺数削減テク:スーパー頂点を用いてsparseに
めちゃ好きだけど、実装重い 問題へのリンク 問題概要 頂点の重み付き無向完全グラフが与えられる。各 に対して、 頂点集合を 個の互いに disjoint な集合に分割する方法であって どの同族辺 (両端点が同一のグループに属する辺) の重みも、どの異族辺 (両端…
