kmjp's blog

競技プログラミング参加記です

yukicoder : No.242 ビンゴゲーム

面白かったです。
http://yukicoder.me/problems/638

問題

1-99の99個の数字のうち、ランダムで(重複しない)25個の数字が書かれたビンゴカードが与えられる。
99個中N個の数字が等確率で呼ばれたとする。

この時成立するビンゴの数の期待値は幾つか。

解法

Editorialはもっと単純な解法なので、そちらを見てもらった方がいいです。

カードに書かれる数字も呼ばれる数字も等確率で選ばれるので、カードに書かれる数字が端から順に1~25だと決め打ちしてしまおう。
そして1~25が呼ばれる/呼ばれないケースを(2^25)通り試していく。

1~25の呼ばれる/呼ばれないを表現したbitmaskをmとする。
m中で呼ばれた数字の数をC(m)、m中のビンゴ数をB(m)とする。

99個中N個選ぶ選び方は {}_{99} C_N通り。
そのうち、1~25がmで表現されるようなN個の数字の選び方は、残り74個から(N-C(m))個を選ぶ選び方なので {}_{74} C_{N-C(m)}通り。

よって解は \displaystyle \sum_{m} (B(m) \times \frac{{}_{74} C_{N-C(m)}}{{}_{99} C_N})

long double comb(int P_,int Q_) {
	static const int N_=102;
	static long double C_[N_][N_];
	
	if(C_[0][0]==0) {
		int i,j;
		FOR(i,N_) C_[i][0]=C_[i][i]=1;
		for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j]);
	}
	if(P_<0 || P_>N_ || Q_<0 || Q_>P_) return 0;
	return C_[P_][Q_];
}

int N;
long double ret;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	long double tot=comb(99,N);
	for(int mask=0;mask<1<<25;mask++) {
		x=0;
		if(__builtin_popcount(mask)>N) continue;
		long double prob = comb(74,N-__builtin_popcount(mask))/tot;
		if(prob==0) continue;
		
		FOR(i,5) {
			if((mask & (((1+(1<<5)+(1<<10)+(1<<15)+(1<<20)))<<i))==(((1+(1<<5)+(1<<10)+(1<<15)+(1<<20)))<<i)) x++;
			if((mask & (31<<(i*5)))==(31<<(i*5))) x++;
		}
		if((mask & ((1+(1<<6)+(1<<12)+(1<<18)+(1<<24))))==((1+(1<<6)+(1<<12)+(1<<18)+(1<<24)))) x++;
		if((mask & (((1<<4)+(1<<8)+(1<<12)+(1<<16)+(1<<20))))==(((1<<4)+(1<<8)+(1<<12)+(1<<16)+(1<<20)))) x++;
		ret += prob*x;
	}
	
	_P("%.10Lf\n",ret);
}

まとめ

ビンゴゲームの25マスってのがbitdpや2^N通りの総当たりにちょうどいいサイズですね。
前回のABC(Beginner向けではない)も25マスだったし。