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

参加してみた。B,Cは1WAしつつも何とか解けたが、Dのバグが最後まで直らず微妙な順位に。
まぁEも途中まで解けて最後まで行けなさそうではあったが。
http://tenka1-2014-quala.contest.atcoder.jp/tasks/tenka1_2014_qualA_c

問題

M文字の文字列がN個与えられる。
各文字列はアルファベット小文字かアスタリスク(ワイルドカード)を含む。

ここで、M文字のアルファベット小文字で構成された文字列P個からなる文字列集合Xがあるとき、N個の文字列はX中最低１個はマッチする文字列があるようにしたい。
条件を満たす最小のPを求めよ。

解法

２つの文字列に両方マッチする文字列が存在するかどうかは1組あたりO(M)で判定できるので、全文字列ペアではO(N^2*M)で判定できる。
次に、２つ以上のQ個の文字列にマッチできる文字列があるかどうかは、Q個のうちどの２個をとってもマッチすることを確認すればいいので、上記のマッチ結果を利用するとO(N^2)。
文字列の選び方が2^N通りあることを考えると全体でO(N^2*2^N)。

上記Q個の文字列にマッチできる単一文字列がある場合、Pに１加えることでそれらQ個にマッチさせることができる。
あとはN個の全文字列にマッチする文字列の数Pを最小化すればよい。
本番はDFSで解いたが、下記の通りこの部分は数行のBitDPでも解くことができる。

int N,M;
string P[15];
int mat[15][15];
int mi[1<<15];
 
int match(string a,string b) {
	int i;
	FOR(i,M) if(a[i]!=b[i] && a[i]!='*' && b[i]!='*') return 0;
	return 1;
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M;
	FOR(i,N) cin>>P[i];
	FOR(i,N) FOR(j,N) mat[i][j]=match(P[i],P[j]);
	
	FOR(i,1<<N) {
		mi[i]=1;
		FOR(x,N) for(y=x+1;y<N;y++) if((i&(1<<x)) && (i&(1<<y)) && mat[x][y]==0) mi[i]=100;
	}
	
	FOR(i,1<<N) FOR(j,1<<N) mi[i|j]=min(mi[i|j],mi[i]+mi[j]);
	cout << mi[(1<<N)-1] << endl;
	
}

まとめ

最後のBitDPは賢いな…DFSで無駄に面倒な解き方をしてしまった。