天下一プログラマーコンテスト2014 予選A C.天下一文字列集合

問題

n個のパターン文字列が与えられる。パータン文字列は、小文字アルファベットか'*'で構成される長さMの文字列。
'*'の場合は任意のアルファベット1文字にマッチする。
与えられるパターン文字列は、文字列集合Xのどれか1つの文字列にマッチするように作られている。
文字列集合Xの要素数の最小値を求める。

制約
1<=N<=14
1<=M<=10^5

例：
パターン文字列が、
{a*b,ab*}
の場合は、文字列集合Xは、{abb}や{abb,abc}や{acb,abc,abd}などが考えられるが、
{abb}
の場合、最小の1個となる。

考え方

解説: http://tenka1.klab.jp/2014/explain/quala_c.html

超典型問題らしい。(たぶん、集合に対して部分集合のbitDPする典型問題)
twitterで見てたら2^28とか3^14とか飛び交っていたので、ちゃんと復習します。。。。

上記の問題は、各パターン文字列を頂点、同じ文字列を表す事ができるかどうかで辺を張ったグラフGでの「最小クリーク被覆問題」になる。
(クリークは、部分頂点集合T⊆Vで構成される部分グラフが完全グラフになっているようなもの)

解法は、dp[S]:=頂点集合Sが最小で何個のクリークで被覆できるか？のbitDP。
集合Sを2つに分割してそれぞれの最小クリーク数を足し合わせたものの最小値を求めていく。

O(n!)+枝刈り

nが14だけど、枝刈りしながら探索しても間に合うらしい。
頂点の選び方はO(n!)で、各頂点についてk色のどれかがあり得るので、O(n! * k^n)？
(14!=87,178,291,200)。

DEGwer3456さん
https://twitter.com/DEGwer3456/status/498113916371603456

O(2^{2*n})

以下のようなループをまわすと、O(2^n * 2^n)になっている。

for(int S=0; S<(1<<n); S++){ //O(2^n)
  if(Sがクリーク){ //集合Sのすべての2点間に辺があるO(n^2)
    dp[S] = 1;
  }

  for(int T=0; T<S; T++){ //O(2^n)
    if((S|T)!=S) continue; //集合Tが集合Sの部分集合でないなら無視

    int R = S ^ T; //集合Sで、集合Tに含まれない点集合
    dp[S] = min(dp[S], dp[T]+dp[R]);
  }
}

O(3^n)

集合Sの部分集合が欲しいが、上記の方法では、部分集合とは限らないものも生成している。
以下のようにすると、Sの部分集合のみ列挙できる。(蟻本だとdo-while形式)

for(int S=0; S<(1<<n); S++){
  //...

  for(int T=S; T>0; T=(T-1)&S){ //TとS^TはSの部分集合
    //...
  }
}

計算量は、各ビットについて考えると、集合SとTは、

Sのi番目のビットが0、Tのi番目のビットが0
Sのi番目のビットが1、Tのi番目のビットが0
Sのi番目のビットが1、Tのi番目のビットが1

のみ列挙しているため、各ビットが3通りあり、nビット分あるので、O(3^n)になるらしい。
(O(n^{2n})の方法では、Sが0、Tが1の場合も含めた4通り列挙しているので、O(4^n)=O(2^{2n}))

これについては、Sigmarさんがまとめられてた。
http://topcoder.g.hatena.ne.jp/jackpersel/20100804/1281196966

O(2^n * n)

さらに、包除原理と高速ゼータ変換を使った方法でO(2^n * n)まで計算量が落とせるらしい。

http://www.slideshare.net/wata_orz/ss-12131479

彩色数と最小クリーク被覆の関係

「補グラフの彩色数χ(G^c)=グラフGの最小クリーク被覆」

http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1584-20.pdf
http://www.slideshare.net/wata_orz/ss-12131479

グラフの彩色について以下の事が言える。
「グラフGがk-彩色可能 <=> 頂点集合Vをk個の安定集合で被覆できる」
(安定集合(独立集合)は、その集合内の2頂点間につなぐ辺が存在しない頂点集合)

グラフG=(V,E)について、補グラフG^c=(V,E^c)を考える。
辺集合E^cは、辺集合Eに含まれない辺全体の集合を表す。(E^C=V×V-E)
このとき、補グラフG^cにおける安定集合は、グラフGにおけるクリークを構成する頂点集合になる。
(証明は・・・)

れどこだ目指すよ！　(；`・ω・）