これは面倒な問題…。
http://community.topcoder.com/stat?c=problem_statement&pm=11840
問題
円形の花壇があり、N個のブロックからなる。
各ブロックの色は、(R,G,B)の3色の度合いで表現され、各色は0~maxR、0~maxG、0~maxBの間の整数を取る。
花壇の状態が良いというのは、隣接するブロックの色合いが以下の条件を満たす場合である。
- R同士・G同士・B同士の差の絶対値がいずれもd2以下である。
- R同士・G同士・B同士の差の絶対値のうち、d1以上の色要素が1つはある。
ここで、花壇が円形であることを忘れ、0番から(N-1)番までは上記条件を満たすように色を付けてみたが、花壇が円形であるために(N-1)番と0番が条件を満たさない可能性が出てきた。
0番から(N-1)番までは条件を満たす色を等確率でつけてきた場合、最後(N-1)番と0番が条件を満たさない確率を求めよ。
解法
i番の色から遷移できる(i+1)番の色は上記条件よりDPで求められる。
ただし、愚直にDPすると(N*maxR^2*maxG^2*maxB^2)かかりTLEする。
そこで、上記条件に対し事前に求めた累積和と包除原理を適用することで(N*maxR*maxG*maxB)まで計算量を落とすことができる。
double dpdp[2][51][51][51]; double sum[4][55][55][55]; class RandomColoring { public: double calc(int r2,int r1,int g2,int g1,int b2,int b1) { double ret=0; int r,g,b; if(r1>r2 || g1>g2 || b1>b2) return 0; r2++,b2++,g2++; return sum[3][r2][g2][b2]-(sum[3][r1][g2][b2]+sum[3][r2][g1][b2]+sum[3][r2][g2][b1]) + (sum[3][r2][g1][b1]+sum[3][r1][g2][b1]+sum[3][r1][g1][b2])-sum[3][r1][g1][b1]; } double getProbability(int N, int maxR, int maxG, int maxB, int startR, int startG, int startB, int d1, int d2) { ZERO(dpdp); int r,b,g,i; dpdp[0][startR][startG][startB]=1.0; FOR(i,N-1) { int cur=i%2,tar=cur^1; ZERO(dpdp[tar]); ZERO(sum); double tot=0; FOR(r,maxR) FOR(g,maxG) FOR(b,maxB) { tot+=dpdp[cur][r][g][b]; int inin[3],out[3]; inin[0]=(d1==0)?0:(min(r+d1-1,maxR-1)-max(r-d1+1,0)+1); inin[1]=(d1==0)?0:(min(g+d1-1,maxG-1)-max(g-d1+1,0)+1); inin[2]=(d1==0)?0:(min(b+d1-1,maxB-1)-max(b-d1+1,0)+1); out[0]=min(r+d2,maxR-1)-max(r-d2,0)+1; out[1]=min(g+d2,maxG-1)-max(g-d2,0)+1; out[2]=min(b+d2,maxB-1)-max(b-d2,0)+1; int num=out[0]*out[1]*out[2]-inin[0]*inin[1]*inin[2]; if(num>0) sum[0][r+1][g+1][b+1]=dpdp[cur][r][g][b]/num; } FOR(r,maxR) FOR(g,maxG) FOR(b,maxB) sum[1][r+1][g+1][b+1]=sum[1][r+1][g+1][b]+sum[0][r+1][g+1][b+1]; FOR(r,maxR) FOR(g,maxG) FOR(b,maxB) sum[2][r+1][g+1][b+1]=sum[2][r+1][g][b+1]+sum[1][r+1][g+1][b+1]; FOR(r,maxR) FOR(g,maxG) FOR(b,maxB) sum[3][r+1][g+1][b+1]=sum[3][r][g+1][b+1]+sum[2][r+1][g+1][b+1]; FOR(r,maxR) FOR(g,maxG) FOR(b,maxB) { dpdp[tar][r][g][b] = calc(min(r+d2,maxR-1),max(r-d2,0),min(g+d2,maxG-1),max(g-d2,0),min(b+d2,maxB-1),max(b-d2,0)); dpdp[tar][r][g][b] -= calc(min(r+d1-1,maxR-1),max(r-d1+1,0),min(g+d1-1,maxG-1),max(g-d1+1,0),min(b+d1-1,maxB-1),max(b-d1+1,0)); } } double ret=1; FOR(r,maxR) FOR(g,maxG) FOR(b,maxB) { if(abs(r-startR)<=d2 && abs(g-startG)<=d2 && abs(b-startB)<=d2 && (abs(r-startR)>=d1 || abs(g-startG)>=d1 || abs(b-startB)>=d1)) ret-=dpdp[(N-1)%2][r][g][b]; } return ret; } }
まとめ
こういうDPは面倒なだけで面白くないな…。