TopCoder SRM 518 Div2 Hard CoinReversing

ここらへん易しい問題が続く。
http://community.topcoder.com/stat?c=problem_statement&pm=11473

問題

初期状態でN枚のコインが表を向いている。
この後、要素数Lの配列Aに対し、「コインのうちランダムでA[i]枚選択してひっくり返す」という処理を行う。
最終的に表となるコイン枚数の期待値を答えよ。

解法

典型問題。
X枚表でN-X枚裏の状態において、A[i]中p枚表から選び、A[i]-p枚裏から選ぶ確率はであり、その後表の枚数はX-p+(A[i]-p)になる。
これをO(NL^2)程度DPするだけ。

double comb(int P_,int Q_) {
	static const int N_=1020;
	static 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_];
}
double dp[2][1001];

class CoinReversing {
	public:
	double expectedHeads(int N, vector <int> a) {
		int i,j,x,y;
		ZERO(dp);
		dp[0][N]=1;
		
		FOR(i,a.size()) {
			int cur=i%2,tar=cur^1;
			ZERO(dp[tar]);
			FOR(x,N+1) {
				FOR(y,a[i]+1) {
					int z=a[i]-y;
					if(y>x || z>N-x) continue;
					if(dp[cur][x]==0) continue;
					dp[tar][x-y+z] += dp[cur][x] * comb(x,y) * comb(N-x,z)/ comb(N,a[i]);
				}
			}
		}
		
		double ret=0;
		FOR(i,N+1) ret += i*dp[a.size()%2][i];
		return ret;
	}
};

まとめ

期待値の問題は以前は苦手意識だらけだったけど、少しは改善してきたかな…。