TopCoder SRM 313 Div1 Medium CrazyRunning

問題

中心からn本の通路が伸びた建物がある。
それぞれの通路の長さはcorridors[i]である。

0番の通路の端からスタートして、
「中心へ行き、今来た通路でない通路を等確率で一つ選んでその通路の端まで行く」
ということを繰り返して、全ての通路を一度以上歩きたい。

最後の一つの通路を歩き終えたら、その場で終了し中心へは戻らない。
このとき、全ての通路を歩き終えるまでにかかる移動距離の期待値を求めよ。

制約条件

n≦50
corridors[i]≦10^6

方針

0番以外の通路は全て対称なので、
距離の期待値を計算する上では、距離を平均化してしまってよい。
（Σ[0以外]corridors[i] / (n - 1)の通路がn - 1あると考える）

すると、E[今0にいるかどうか][今までにいくつ通路を訪れたか]:= ゴールするまでの期待値について、漸化式が立つ。

漸化式は連立一次方程式なので解いてもよいが、
収束するまで回すのが簡単。10000回くらい回せば十分な精度が出る。

ソースコード

int n;
double E[2][51][2];

class CrazyRunning {
	public:
	double expectedTime(vector <int> corridors) 
	{
		n = corridors.size();
		double s = 0;
		for(int i = 1; i < n; i++) s += corridors[i];
		s /= n - 1;
		
		memset(E, 0, sizeof(E));
		double (*cur)[2] = E[0], (*next)[2] = E[1];
		
		rep(it, 10000){
			memset(next, 0, sizeof(next));
			
			for(int i = n - 1; i > 0; i--){
				next[i][0] = corridors[0] + (i - 1.0) / (n - 1) * (s + cur[i][1]) + 
				(1 - (i - 1.0) / (n - 1)) * (s + cur[i + 1][1]);
				
				next[i][1] = s + 1.0 /(n - 1) * (corridors[0] + cur[i][0]) + 
				(i - 2.0) / (n - 1) * (s + cur[i][1]) +
				(1 - (i - 1.0) / (n - 1)) * (s + cur[i + 1][1]);
			}
			swap(cur, next);
		}
		return cur[1][0];
	}
};