Codeforces #275 Div1 C. Game with Strings

あと１歩だったんだけどなぁ。
http://codeforces.com/contest/482/problem/C

問題

N要素の文字列集合S[i]が与えられる。
各文字列の長さは同じMである。

ここで以下のゲームを行う。

• プレイヤーはS[i]をすべて知っている。
• マスターはN個の文字列のうち１つを等確率で選択する。
• プレイヤーはマスターに対し、選択した文字のある位置にどんな文字があるか問い合わせる。
  • 位置は任意には選べず、未選択のうち１か所が等確率でランダムに選択される。

プレイヤーがマスターの選択した文字列を特定するまでにかかる、問い合わせ回数の期待値を答えよ。

解法

O(N^2*2^M)なコードは割と思いつく。
マスターが選ぶ各文字列に対し、選択済な文字位置のbitmaskをbitdpで総当たりし、文字列を１つに特定できる確率を求める。
ただ、今回はN,Mの大きさからO(N^2*2^M)は時間がかかりすぎる。

マスターが行うN通りの文字選択分の確率計算をまとめて行いたい。
まず、S[i]中の２つの文字列x,yに対し、「その位置を選択しても両者を見分けられない」といった文字位置のbitmask表記を求める。
選択済みのbitmaskが、前期bitmaskに含まれる間、その両者は区別できない。

よってそのようなbitmaskである間、x・yはそれぞれ判断できない。
この判断できない文字列を、またbitmaskで管理する。

そして、前者のbitmask(選択済み文字位置を示すbitmask)に対し、区別不可能な文字列を示すbitmaskがわかるので、高速ゼータ変換を行って置く。

最後にbitdpで確率計算を行う。
選択済み文字位置を示すbitmaskを大きい順に処理し、bitmaskに１ケタ追加した場合の値を足しこんでいく。

最後のこの式がややこしいが、前半はbitmaskに追加可能なbitの数の分足しこんだdp[mask]の平均んを取っているだけ。
また、後半はこのようなbitmaskに到達する可能性(そのような文字列をマスターが選択した可能性)を求めている。その場合bitmaskに1bit足すため手数が1増えるので、そこに到達可能性を掛けている。

 dp[mask] = dp[mask]*1.0/(M-__builtin_popcount(mask)) + __builtin_popcountll(same[mask])*1.0/N;

int N,M;
string S[55];
ll same[1<<20];
double dp[1<<20];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>S[i];
	M=S[0].size();
	
	FOR(x,N) FOR(y,N) if(x!=y) {
		k=0;
		FOR(i,M) if(S[x][i]==S[y][i]) k|=1<<i;
		same[k] |= 1LL<<x;
	}
	
	for(int mask=(1<<M)-2;mask>=0;mask--) {
		FOR(y,M) if((mask & (1<<y))==0) {
			dp[mask]+=dp[mask|(1<<y)];
			same[mask] |= same[mask|(1<<y)];
		}
		dp[mask] = dp[mask]*1.0/(M-__builtin_popcount(mask)) + __builtin_popcountll(same[mask])*1.0/N;
	}
	_P("%.12lf\n",dp[0]);
}

まとめ

本番高速ゼータ変換までたどり着いたけど、最後の式がうまく出てこず失敗。