drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ Codeforces グラフ 二部グラフ 最小全域木 Kruskal法 色に関する問題 クリーク グラフの辺数削減テク:スーパー頂点を用いてsparseに 操作 最小コスト 制約:複数系列の長さの合計が10^5以下 考察：操作・条件・目的関数を言い換える 考察：必要条件を列挙して十分性を示す 考察：補集合を考える CodeforcesOthers CodeforcesR2400 制約条件:カラフルにする 種類数 グラフテク:スーパー頂点 最適化問題 むずかしい 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。これらはある操作のコストを決めるためのパラメータである。 さらに、 系列の数列が与えられる。 番目の数列の項数は で与えられる 数列の各項 は 以上 以下の値である 今、以下の操作を行う。 、 を満たす を選ぶ これに要するコストは で与えられる 番目の数列に値 の項が存在するならば除去する これらの操作後に次のようなグラフを作る。 頂点集合は である 各 に対して、値 がともに 番目の数列に含まれるとき、二頂点 を色 の辺でむすぶ このグラフが「カラフルなサイクル」を持たないようにしたい。それが可能となる最小… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2020%2F10%2F02%2F235400" title="Codeforces Grakn Forces 2020 E. Avoid Rainbow Cycles (R2400) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1516148889515660 Hatena Blog https://hatena.blog 2020-10-02 23:54:00 rich https://drken1215.hatenablog.com/entry/2020/10/02/235400 1.0 100%