C - 天下一文字列集合

[Q] https://atcoder.jp/contests/tenka1-2014-quala/tasks/tenka1_2014_qualA_c
1. NC2通り探索し、マージさせていったら、WA。マージさせる優先度とか、マージさせないほうがいいペアがあるっぽい。

2. けつあなが少ない文字列を優先的にマージしたほうがいいケースに気づく。しかしWA。20点。

反例
5 2
*a
*b
c* // caを作るとだめ。
d*
da

2 
da
cb
にできる。daからマージしたほうがいい。

 3. 補集合DP O(3^N)でAC。
DP[ 1<<n ] = そのペアを作るのに基底がいくつ？で管理。
DP[(1<<n)-1] = DP[111...1111] がこたえ。

入力例
3 1
a
b
*

・{a,*}がペアになるので
DP[101]=1
・{b,*}がペアになるので
DP[011]=1
・項の数0とか1は必然的に 1 にしちゃっていい。

そうして初期入れ。
DP[000]=1
DP[001]=1
DP[010]=1
DP[011]=1
DP[100]=1
DP[101]=1
DP[110]=inf
DP[111]=inf

・補集合DP
こんなかんじ。

 rep(i, (1<<n)){ // 補集合DP
	  ll all = (1<<n)-1;
	  ll op = all^i;
	  for(ll j=op; j>0; j=(j-1)&op){
		  chmin(DP[i|j], DP[i] + DP[j]) ;
	  }
 }
 cout << DP[(1<<n)-1] << endl;
}

DP[111] = 2がとれる。

実装

ll DP[1<<14];
bool B[14][14];

int main(){
 cincout();

 ll n, m;
 cin >> n >> m;
 string S[n];
 rep(i, n) cin >> S[i];
 // ペアにできるか判定。Bの作成
 rep(i, n){
	  for(ll j=i+1; j<n; ++j){
		  bool ok=true;
		  rep(k, m){
			  if (S[i][k] == '*' || S[j][k] == '*' || S[i][k] == S[j][k]) continue;
			  else ok = false;
			  if (!ok) break;
		  }
		  B[i][j] = ok;
	  }
 }
 // DPの初期入れ ペアにできるなら1組。できないならinf
 rep(i, (1<<n)){
	  bool ok=true;
	  rep(k, n){
		  if ((i>>k)&1){
			  for(ll j=k+1; j<n; ++j){
				  if ((i>>j)&1) if(B[k][j] == false) ok = false;
				  if (!ok) break;
			  }
			  if(!ok) break;
		  }
	  }
	  if(ok) DP[i] = 1;
	  else DP[i] = oo;
 }

 rep(i, (1<<n)){ // 補集合DP
	  ll all = (1<<n)-1;
	  ll op = all^i;
	  for(ll j=op; j>0; j=(j-1)&op){
		  chmin(DP[i|j], DP[i] + DP[j]) ;
	  }
 }
 cout << DP[(1<<n)-1] << endl;
}

https://atcoder.jp/contests/tenka1-2014-quala/submissions/26238022