TopCoderOpen 2014 Round1C Hard RedPaint

なんか嘘くさいO(N)解法で通してしまった。
http://community.topcoder.com/stat?c=problem_statement&pm=13063

問題

１次元の無限に続くセルの列があり、初期状態でロボットが原点にいるとする。
Nターンそれぞれで1/2の確率で左右の隣接マスに移動する。
ロボットが通ったマスは赤く塗られる。

ターン数Nが与えられたとき、赤く塗られるマス数の期待値を答えよ。

解法

赤く塗られるマス数は(右端のセルの座標)-(左端のセルの座標)+1である。
するとさっと思いつくのは状態として[到達した左端座標][到達した右端座標][今の座標]を持つDPである。
ただ、このDPはO(N^4)かかるのでN<=500ではTLEする。

O(N^3)の解法

こちらは自分が本番で導けなかった解法。
最終的に欲しいのは(右端のセルの座標)-(左端のセルの座標)+1の値なので、左端と右端を個別に状態として管理する必要はない。
状態として[通過したセル数][今いる座標の到達した左端マスからの距離]とすることで計算量をO(N^3)に落とすことができる。

O(N)の解法

こちらは自分の本番解法。
O(N^3)解法が思いつかなかったので、とりあえず上記O(N^4)をN<=100程度まで解いて傾向を見てみた。
xターンの時の答えをP(x)とし、隣接項同士の差分を取ってみるとなんか法則が見えた。
P(1)-P(0)=1
P(2)-P(1)=0.5=1/2
P(3)-P(2)=0.5=1/2
P(4)-P(3)=0.375=3/8=(1/2)*(3/4)
P(5)-P(4)=0.375=3/8=(1/2)*(3/4)
P(6)-P(5)=0.3125=5/16=(1/2)*(3/4)*(5/6)
P(7)-P(6)=0.3125=5/16=(1/2)*(3/4)*(5/6)

偶数xごとに差分が(x-1)/x倍していることがわかる。
よってここから漸化式を求めてO(N)で求めることができる。

# ただ、なぜこの漸化式が成り立つのかはよくわからず。

以下のコードは両方の解法を含んでいる。

double dpdp[2][520][520];

class RedPaint {
	public:
	/*
	double expectedCells(int N) {
		int i;
		double dd[1010];
		dd[0]=1;
		FOR(i,500) {
			dd[i*2+1]=dd[i*2+2]=dd[i*2]*(i*2+1)/(i*2+2.0);
		}
		double ret=1;
		FOR(i,N) ret+=dd[i];
		
		return ret;
	}
	*/
	double expectedCells(int N) {
		ZERO(dpdp);
		int x,y,z,i;
		dpdp[0][0][0]=1;
		
		FOR(i,N) {
			int cur=i%2,tar=cur^1;
			ZERO(dpdp[tar]);
			FOR(x,i+1) FOR(y,i+1) {
				// right
				if(x==y) dpdp[tar][x+1][y+1] += dpdp[cur][x][y]/2;
				else dpdp[tar][x][y+1] += dpdp[cur][x][y]/2;
				// left
				if(y==0) dpdp[tar][x+1][y] += dpdp[cur][x][y]/2;
				else dpdp[tar][x][y-1] += dpdp[cur][x][y]/2;
			}
		}
		
		double ret=0;
		FOR(x,N+1) FOR(y,N+1) ret += dpdp[N%2][x][y]*(x+1);
		return ret;
	}
};

まとめ

O(N)解法はあまり自身がなかったけど通ってしまった。