TopCoder SRM 780 : Div1 Easy Div2 Hard BeatTheStar

うーむ、Mediumでヘマしてレート減。
https://community.topcoder.com/stat?c=problem_statement&pm=16012&rd=17853

問題

2人でN回勝負を行う。
i回目の試合の勝者はiポイント得る。
両者の勝率はともに5割である。

ポイントの合計は奇数、すなわちポイントの総和は両者同点になることはない。
G回目の試合が決定打になる(この試合の勝者が最終的に勝者になる)確率を求めよ。

解法

Nが小さいので、まずG回目以外の試合を行い、片方の獲得総ポイントに対するその状態に至る確率を求めよう。
あとは両者の点差がG未満の確率のケースの総和を取ればよい。

double from[6000];
double to[6000];


class BeatTheStar {
	public:
	double doesItMatter(int N, int G) {
		
		ZERO(from);
		from[0]=1;
		int i,x,sum=0;
		for(i=1;i<=N;i++) if(i!=G) {
			sum+=i;
			ZERO(to);
			FOR(x,5600) if(from[x]) {
				to[x]+=from[x]/2.0;
				to[x+i]+=from[x]/2.0;
			}
			swap(from,to);
		}
		
		double ret=0;
		FOR(i,sum+1) {
			int a=sum-i;
			if(abs(a-i)<=G) ret+=from[i];
		}
		return ret;
	}
}

まとめ

もう少しNが大きくてもよかったけど、O(N^3)だからこんなもんか。