M - グループ分け / Grouping 解説
by 
Rssll_Krkgrd
（注：この解説で紹介する解法により得られるアルゴリズムは、結果的にはpotato167さんの解法と同じものです。）
この問題を\(O(N2^N)\)で解きます。
まず、公式解説の関数\(f_1\)を用いると、「\(X_1\cup X_2\cup\cdots\cup X_k=\{1,2,\ldots,N\}\)かつ\(f_1(X_1)=f_1(X_2)=\cdots=f_1(X_k)=1\)」を満たす\(X_1,X_2,\ldots,X_k\)が存在するような最小の正整数\(k\)を求めればよいことになります。
ここで、彩色数を求めるアルゴリズム（参考：指数時間アルゴリズム入門）を思い出すと、\(I(S):=(Sの部分集合Xのうち、f_1(X)=1となるものの個数)\)の値を全ての\(S\subset\{1,2,\ldots,N\}\)に対して\(O(N2^N)\)で求められれば、もとの問題も\(O(N2^N)\)で解けることがわかります。
補足
以下は前述のスライドの該当箇所を今回の問題用に言い換えたものです。
$P:=\{S|f_1(S)=1\}$とします。また、$P^k$を$k$個の$P$の直積集合とし、以下のように関数$g_k,h_k$を定めます。
$\begin{aligned}g_k(S)&:=\left|\left\{(X_1,X_2,\ldots,X_k)\subset P^k\mid X_1\cup X_2\cup \cdots \cup X_k=S\right\}\right|\\ h_k(S)&:=\left|\left\{(X_1,X_2,\ldots,X_k)\subset P^k\mid X_1,X_2,\ldots,X_k\subset S\right\}\right|=\sum_{T\subset S}g_k(T)\end{aligned}$
すると、包除原理により、
$g_k(S)=\sum_{T\subset S}(-1)^{|S\setminus T|}h_k(T)$
が成り立つことがわかり、$h_k(S)=I(S)^k$であることとあわせて
$g_k(S)=\sum_{T\subset S}(-1)^{|S\setminus T|}I(T)^k$
となることがわかります。
もとの問題の答えは$g_k(\{1,2,\ldots,N\})>0$を満たす最小の$k$であるため、$k=1,2,\ldots,N$に対する$g_k(\{1,2,\ldots,N\})$の値を求めることができれば、元の問題も解くことができます。
また、全ての\(S\subset\{1,2,\ldots,N\}\)に対する\(f_1(S)\)がわかっているとき、高速ゼータ変換により、\(O(N2^N)\)で全ての\(S\subset\{1,2,\ldots,N\}\)に対する\(I(S)\)を求めることができます。全ての\(S\subset\{1,2,\ldots,N\}\)に対する\(f_1(S)\)は愚直な計算により\(O(N2^N)\)で求めることができるため、結局もとの問題も\(O(N2^N)\)で解くことができました。
投稿日時:
最終更新: