TopCoder SRM 775 : Div1 Medium CardDrawGame

あんまり好きな問題ではないな…。
https://community.topcoder.com/stat?c=problem_statement&pm=15830

問題

0～19の数字が書かれたカードの山があり、各カードの枚数が与えられる。
まず、このカードのうちランダムに３枚が手札として与えられたとする。
うち、何枚か残して何枚か捨てる。その後、山からランダムにカードを補充し、再び３枚になるようにする。

ここで、手札の数値の合計がTとなるようにしたい。
捨て方の最適手を取る場合、その確率はどの程度か。

解法

最初の３枚を総当たりし、入れ替わりで来るカードも総当たりしよう。
カードを0～3枚捨てる場合、一番条件を達成する確率が高い手を選べばよい。

class CardDrawGame {
	public:
	double winChance(int T, vector <int> C) {
		int N=C.size();
		int x,y,z,a,b,c;
		double ret=0;
		int S=0;
		FORR(c,C) S+=c;
		FOR(x,N) if(C[x]) {
			double p1=1.0*(C[x]--)/(S--);
			FOR(y,N) if(C[y]) {
				double p2=p1*(C[y]--)/(S--);
				FOR(z,N) if(C[z]) {
					double p3=p2*(C[z]--)/(S--);
					
					double ma=0;
					
					
					double PP[4][61]={};
					FOR(a,N) if(C[a]) {
						double q1=1.0*(C[a]--)/(S--);
						PP[1][a]+=q1;
						FOR(b,N) if(C[b]) {
							double q2=q1*(C[b]--)/(S--);
							PP[2][a+b]+=q2;
							FOR(c,N) if(C[c]) {
								double q3=q2*C[c]/S;
								PP[3][a+b+c]+=q3;
							}
							C[b]++,S++;
						}
						C[a]++,S++;
					}
					
					if(x+y+z==T) ma=1;
					if(T-x-y>=0) ma=max(ma,PP[1][T-x-y]);
					if(T-x-z>=0) ma=max(ma,PP[1][T-x-z]);
					if(T-z-y>=0) ma=max(ma,PP[1][T-z-y]);
					if(T-x>=0) ma=max(ma,PP[2][T-x]);
					if(T-y>=0) ma=max(ma,PP[2][T-y]);
					if(T-z>=0) ma=max(ma,PP[2][T-z]);
					ma=max(ma,PP[3][T]);
					//cout<<x<<y<<z<<" "<<p3<<" "<<ma<<endl;
					ret+=p3*ma;
					
					C[z]++,S++;
				}
				C[y]++,S++;
			}
			C[x]++,S++;
		}
		return ret;
		
	}
}

まとめ

なんか前回のMediumといいなんか安直な問題が多いな。