TopCoderOpen 2020 Round1A : Hard BlindBoxSets

これなら出なくて良かったかな…。
https://community.topcoder.com/stat?c=problem_statement&pm=15979&rd=17907

問題

N種類のアイテムからなるキットがある。
1個アイテムを購入すると、いずれかがランダムで手に入る。
全アイテムをM個以上そろえるのにかかる購入回数の期待値を求めよ。

解法

典型問題かな。Mが高々4なので
p(a,b,c,d) := あと4個買う必要があるアイテムがa個、あと3個買う必要があるアイテムがb個、あと2個買う必要があるアイテムがc個、あと1個買う必要があるアイテムがd個である状態に至る確率と、その時の購入回数の期待値
を状態として、各状態に対し到達確率で重みづけ平均を取りながら購入回数の期待値を計算していく。

double prob[51][51][51][51];
double num[51][51][51][51];

class BlindBoxSets {
	public:
	double expectedPurchases(int numSets, int N) {
		ZERO(prob);
		ZERO(num);
		if(numSets==1) prob[0][0][0][N]=1;
		if(numSets==2) prob[0][0][N][0]=1;
		if(numSets==3) prob[0][N][0][0]=1;
		if(numSets==4) prob[N][0][0][0]=1;
		
		int a,b,c,d;
		for(a=N;a>=0;a--) for(b=N;b>=0;b--) for(c=N;c>=0;c--) for(d=N;d>=0;d--) if(prob[a][b][c][d]>0 && a+b+c+d) {
			int all=a+b+c+d;
			double ex=N*1.0/all;
			double p=prob[a][b][c][d];
			double n=num[a][b][c][d]/p;
			
			if(a) {
				prob[a-1][b+1][c][d]+=p*a/all;
				num[a-1][b+1][c][d]+=(ex+n)*p*a/all;
			}
			if(b) {
				prob[a][b-1][c+1][d]+=p*b/all;
				num[a][b-1][c+1][d]+=(ex+n)*p*b/all;
			}
			if(c) {
				prob[a][b][c-1][d+1]+=p*c/all;
				num[a][b][c-1][d+1]+=(ex+n)*p*c/all;
			}
			if(d) {
				prob[a][b][c][d-1]+=p*d/all;
				num[a][b][c][d-1]+=(ex+n)*p*d/all;
			}
		}
		
		return num[0][0][0][0];
	}
}

まとめ

今の参加人数でRoundを4つも分ける必要あるのかな…。