kmjp's blog

競技プログラミング参加記です

TopCoder SRM 626 Div1 Easy FixedDiceGameDiv1、Div2 Medium FixedDiceGameDiv2

SRM626に参加。
せっかくEasyをそこそこの時間で解いたのに、しょうもないミスで落としてしまいレート激減…。
http://community.topcoder.com/stat?c=problem_statement&pm=13239
http://community.topcoder.com/stat?c=problem_statement&pm=13240

問題

2人でサイコロを振って、目の総和を競う。
先手は1~aの目を持つa面サイコロをb個振る。
後手は1~cの目を持つc面サイコロをd個振る。

先手の総和が後手を上回るとき、先手の総和の期待値を求めよ。

なお、Div2 Mediumはサイコロ数b,dが1である。

解法

まず先手後手DPで各総和が出る確率を求める。
先手の総和xに対し、その先手を取る確率をP(x)、後手がx未満の総和を取る確率をQ(x)とする。
総和xをP(x)*Q(x)で重みづけして期待値を取ればよい。

Div2 Mediumはサイコロの数が1つであり、各目が出る確率は均一なのでだいぶコードを簡略化できる。

class FixedDiceGameDiv1 {
	public:
	double dp[2][2602];
	double getExpectation(int a, int b, int c, int d) {
		int x,y,z,i;
		if(a*b<=c) return -1.0f;
		ZERO(dp);
		
		dp[0][0]=dp[1][0]=1;
		FOR(x,a) {
			for(y=a*b;y>=0;y--) if(dp[0][y]) {
				FOR(z,b) dp[0][y+z+1]+=dp[0][y]/(double)(b);
				dp[0][y]=0;
			}
		}
		FOR(x,c) {
			for(y=c*d;y>=0;y--) if(dp[1][y]) {
				FOR(z,d) dp[1][y+z+1]+=dp[1][y]/(double)(d);
				dp[1][y]=0;
			}
		}
		
		double ret=0,ho=0;
		FOR(i,2501) {
			double tt=0;
			FOR(x,i) tt+=dp[1][x];
			ret+=i*dp[0][i]*tt;
			ho+=dp[0][i]*tt;
		}
		if(ho==0) return -1.0f;
		return ret/ho;
	}
}

class FixedDiceGameDiv2 {
	public:
	double getExpectation(int a, int b) {
		int x,y;
		int tot=0,num=0;
		for(x=1;x<=a;x++) for(y=1;y<=min(x-1,b);y++) num++,tot+=x;
		return tot/(double)num;
		
	}
}

まとめ

ミスがしょうもなさ過ぎて残念すぎる。