TopCoder SRM 540 Div1 Medium RandomColoring

これは面倒な問題…。
http://community.topcoder.com/stat?c=problem_statement&pm=11840

問題

円形の花壇があり、N個のブロックからなる。
各ブロックの色は、(R,G,B)の３色の度合いで表現され、各色は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は面倒なだけで面白くないな…。