Google Code Jam 2013 Round 1B : B. Falling Diamonds

さてB。これはなかなか面白いと感じた問題。
https://code.google.com/codejam/contest/2434486/dashboard#s=p1

問題

座標(0,+∞)からX,Y軸方向から45度回転させた斜めの正方形がN個落下し、Y=0以上の位置に積み重なっていく。
各正方形が落下して、すでに落ちた正方形の頂点にぶつかった場合、左右等確率でどちらかに落ちる。
ここで、座標(X,Y)が与えられたとき、N個の正方形落下後に、その位置を中心とする正方形が存在する確率を答える。

解法

一定数ごとに落下した正方形群が同じ形(三角形状)に積み重なることに注意。
1,(1+5),(1+5+9),,,(1+5+9+...+(4K+1) )個毎に三角形状になる。
(1+5+...+(4K+1) ) < N <= (1+5+...+(4(K+1) +1) )となるKに対し、

• |X|+Y < 2Kなら(X,Y)はこの三角形内に確実に含まれるので確率は1.0となる。
• |X|+Y > 2Kなら(X,Y)はこの三角形の外側なので確率は0.0となる。
• |X|+Y == 2Kなら、N-(1+5+...+(4K+1) )個分の正方形が三角形の頂点にぶつかってY個以上左に落ちる確率を求めればよい。

最後の確率はDPで求めればよい。

double DP[2][4020];
double calc(int N,int Y,int P) {
	ZERO(DP);
	DP[0][0]=1.0;
	int i,x,y;
	FOR(i,N) {
		int cur=i%2;
		int tar=1-cur;
		ZERO(DP[tar]);
		
		FOR(x,i+1) {
			y=i-x;
			if(x>=P-1) DP[tar][x] += DP[cur][x];
			else if(y>=P-1) DP[tar][x+1] += DP[cur][x];
			else {
				DP[tar][x] += DP[cur][x]/2.0;
				DP[tar][x+1] += DP[cur][x]/2.0;
			}
		}
		
	}
	double r=0;
	for(x=Y+1;x<=N;x++) r+=DP[N%2][x];
	return r;
}

void solve(int _loop) {
	int i,j,x,y,ne=0;
	int NP,TP,PP;
	int N,X,Y;
	
	GET3(&N,&X,&Y);
	NP=TP=0;
	while(TP+(NP+1)*4-3<=N) TP+=++NP*4-3;
	
	PP=1+(abs(X)+Y)/2;
	
	if(PP<=NP) {
		_PE("Case #%d: %.10f\n",_loop,1.0);
	}
	else if(PP>NP+1 || X==0) {
		_PE("Case #%d: %.10f\n",_loop,0.0);
	}
	else {
		double res=calc(N-TP,Y,1+(abs(X)+Y));
		_PE("Case #%d: %.10f\n",_loop,res);
	}
	
}

まとめ

よくこういう問題思いつくな…。