面白かったです。
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個選ぶ選び方は通り。
そのうち、1~25がmで表現されるようなN個の数字の選び方は、残り74個から(N-C(m))個を選ぶ選び方なので通り。
よって解は。
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マスだったし。