TopCoder SRM 802 : Div1 Easy Div2 Hard DisjointDiceValues

SRM結構久しぶりだったっぽいな。
https://community.topcoder.com/stat?c=problem_statement&pm=16815&rd=18537

問題

AliceはA個、BobはB個の6面ダイスを持っている。
それぞれがダイスを振ったとき、Aliceが出した目の集合と、Bobが出した目の集合で同じものが含まれる確率を求めよ。

解法

f(n,mask) := n個ダイスを振ったとき、出た目の集合がmaskに示す通りとなる確率
とすると、これはダイスの目の数をFとしてO(nF^2)で求められる。

あとはf(A,m1)*f(B,m2) (m1とm2は空でない共通部分を持つ)の総和を求めればよい。

double pat[18][1<<6];

class DisjointDiceValues {
	public:
	double getProbability(int A, int B) {
		ZERO(pat);
		
		pat[0][0]=1;
		int i,j,x,y,mask,mask2;
		FOR(i,16) {
			FOR(mask,1<<6) {
				FOR(j,6) pat[i+1][mask|(1<<j)]+=pat[i][mask]/6.0;
			}
		}
		
		double ret=0;
		FOR(mask,1<<6) FOR(mask2,1<<6) if(mask&mask2) {
			ret+=pat[A][mask]*pat[B][mask2];
		}
		return ret;
		
		
	}
}

まとめ

A,Bも目の数も小さいので、特に悩ましいところもないし、何がしたいかよくわからん問題だった。