TopCoder SRM 785 : Div1 Medium EllysTwoRatings

こっちも方針ミス。
https://community.topcoder.com/stat?c=problem_statement&pm=16084&rd=17965

問題

2つのコンテストサイトがあり、プレイヤーの現レートはA,Bである。
両コンテストは火曜・木曜に行われる。
コンテスト後のレートは現在値から±100のうち、[1,1000]の範囲に収まる値のいずれかを等確率で取る。

これからN週コンテストに参加し続けるとき、途中で両レートが一致する確率はいくつか。

解法

f(i,A,B) := i週目の火曜前のレートがA,Bで、これまでまだレートが一致したことない状態に至る確率
g(i,A,B) := i週目の木曜前のレートがA,Bで、これまでまだレートが一致したことない状態に至る確率

と両レートで2次元、あと時間の軸の3つの状態を持つテーブルを考える。
f(i,A,B)の値はg(i,*,B)のある矩形範囲に均等に分配されるし、g(i,A,B)の値はf(i+1,A,*)のある矩形範囲に分配される。
この手続きは累積和を使うと1回あたりO(R^2) (Rはレートの最大値)で終わる。
よって全体でO(N*R^2)で処理できる。

double F[1010][1010];
double T[1010][1010];


class EllysTwoRatings {
	public:
	double getChance(int N, int A, int B) {
		
		ZERO(F);
		ZERO(T);
		F[A][B]=1;
		double sum=0;
		int x,y;
		while(N--) {
			ZERO(T);
			
			for(y=1;y<=1000;y++) {
				int L=max(1,y-100);
				int R=min(1000,y+100);
				int C=R-L+1;
				for(x=1;x<=1000;x++) if(F[y][x]) {
					T[L][x]+=F[y][x]/C;
					T[R+1][x]-=F[y][x]/C;
				}
			}
			swap(F,T);
			for(y=1;y<=1000;y++) {
				for(x=1;x<=1000;x++) {
					F[y][x]+=F[y-1][x];
				}
			}
			for(y=1;y<=1000;y++) {
				sum+=F[y][y];
				F[y][y]=0;
			}
				
			ZERO(T);
			
			for(y=1;y<=1000;y++) {
				int L=max(1,y-100);
				int R=min(1000,y+100);
				int C=R-L+1;
				for(x=1;x<=1000;x++) if(F[x][y]) {
					T[x][L]+=F[x][y]/C;
					T[x][R+1]-=F[x][y]/C;
				}
			}
			swap(F,T);
			for(y=1;y<=1000;y++) {
				for(x=1;x<=1000;x++) {
					F[x][y]+=F[x][y-1];
				}
			}
			for(y=1;y<=1000;y++) {
				sum+=F[y][y];
				F[y][y]=0;
			}
		}
		return sum;
		
	}
}

まとめ

2次元テーブルの累積和を、縦横交互に取っていく問題。
最初O(N*R^3)の解法思いついてからそこに至るのに時間をかけすぎたのが失敗。