クリーク
な bit DP としてよく知られている問題ですね! 問題へのリンク EDPC U - Grouping の類題と言える! atcoder.jp 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。頂点集合を、いくつかの頂点部分集合に分割したい。ただし、分割してできる各部分グラ…
Codeforces
グラフ問題
NP困難(特殊構造なので解ける)
クリーク
後退解析
queue
葉から考える
制約条件:グラフの次数列
どちらかの条件を満たすものの構築
Yes/No判定問題
復元
1つ求める
定数倍高速化
部分グラフ列挙問題
見積り大事
O(√N)まで考えれば十分
CodeforcesDIV1-B
CodeforcesR2600
TLE が厳しくて話題になってた 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフ [tex G] が与えられる。また、正の整数 が与えられる。 以下のいずれかの条件を満たすものが存在するかどうかを判定し、存在するならばそれを出力せよ。 type 1: の…
Codeforces
グラフ問題
二部グラフ
最小全域木
Kruskal法
色に関する問題
クリーク
denseなグラフをスーパーノードでsparseにする
操作
最小コスト
制約:複数系列の長さの合計が10^5以下
条件の言い換え
必要条件を列挙したら十分条件になる
補集合を考える
CodeforcesOthers
CodeforcesR2400
カラフルにする
種類数
むずかしい 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。これらはある操作のコストを決めるためのパラメータである。 さらに、 系列の数列が与えられる。 番目の数列の項数は で与えられる 数列の各項 は 以上 以下の値である 今、…