かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

ABC199 D - RGB Coloring 2

ABC グラフ数え上げ競技プログラミング解説

問題はこちら

問題概要
問題概要2
解説
別解
提出プログラム
感想

問題概要

${N}$ 頂点 ${M}$ 辺の単純無向グラフの各頂点を赤，緑，青で塗り分ける方法で隣接する頂点が異なる色で塗られているようなものは何通りあるか．

${1\leq N \leq 20\\ 0 \leq M \leq \frac{N(N-1)}{2}}$

問題概要2

グラフ理論っぽく書かれていますが，同じ箱に入れてはいけないようなボールの組がいくつか与えられるので区別できる ${N}$ 個のボールを区別できる ${3}$ つの箱にいれる方法の数を求める問題です．

解説

重要な考え方として，複雑な問題をいきなり解くのではなく単純な問題から考えるようにするとうまくいくことがあります．

今回の問題で言うと， ${3}$ 色に塗り分ける問題をいきなり解くのではなくて赤と緑の ${2}$ 色に塗り分ける問題を考えます．ある頂点を赤で塗ると，その頂点と隣接する頂点は青に塗られます．これを繰り返していくと ${1}$ つの連結成分につき，最初の頂点を赤に塗るか青に塗るかの ${2}$ 通りになります．ただし，グラフに奇閉路が存在する場合は ${2}$ 色に塗ることはできません．以上から，奇閉路が存在すれば ${0}$ 通り，存在しなければ連結成分数を ${C}$ として ${2^C}$ が答えになります．

では， ${3}$ 色の場合を考えます．青に塗る頂点を決めれば，残りの頂点を ${2}$ 色に塗る問題になります．青に塗る頂点は ${O(2^N)}$ の全探索をすればいいです．計算量は ${O( (N+M)2^N)}$ です．

他にもsubset convolutionを使った解があるらしい~~(未履修)~~ 勉強しました

別解

結局，頂点を ${3}$ つの独立集合に分ける問題です．全頂点集合を ${S}$ として

${\displaystyle\sum_{R\subseteq S,G\subseteq S\backslash R}f(R)×f(G)×f(S\backslash (R\cup G) )}$

が答えです．ここで ${f(S)}$ とは，頂点集合 ${S}$ が独立集合なら ${1}$ そうでないなら ${0}$ となる関数です．

このような畳み込みをSubsetConvolutionといい， ${O(N^22^N)}$ で解けることが知られています．参考

SubsetConvolutionを知っていたらそれにしか見えませんね．

提出プログラム

https://atcoder.jp/contests/abc199/submissions/22047215 スパゲッティ
https://atcoder.jp/contests/abc199/submissions/22138032 SubsetConvolution

感想

D問題にしては難しい．考察の沼にハマると抜け出せなさそう．
簡単な問題から考えるのは重要．