さて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); } }
まとめ
よくこういう問題思いつくな…。