AGC007C: Pushing Balls

https://agc007.contest.atcoder.jp/assignments

期待値ってこんなこともできるのか…

まずf(d1,d2,....d2n)を距離の間隔がそれぞれd1...d2nの時の期待値と定義します。
簡単な例でf(1,2,3,4,5,6)を取り上げます。
1手進めてみましょう。すると
f(1,2,3,4,5,6)=(1+2+3+4+5+6)/6+1/6{f(3,4,5,6)+f(6,4,5,6)+f(1,9,5,6)+f(1,2,12,6)+f(1,2,3,15)+f(1,2,3,4)}
となります。ここで{}内について考えてみます。
f(a,b,c,d)=E1(a)+E2(b)+E3(c)+E4(d)となります。ここでEk(x)はk番目長さxの区間のみに注目した時の期待値とします。
さらにEk(x)=x*Ek(1)となります。なのでf(3,4,5,6)=3*E1(1)+4*E2(1)+5*E3(1)+6*E4(1)です。
なので{}内=13E1+23E2+33E3+43E4=13(E1+23/13E2+33/13E3+43/13E4)=13*f(1,23/13,33/13,43/13)となります。
あとはこれを繰り返すだけでO(N)で求められます。

同じような状態を平均化している感じですね。加法定理が使えるとこういうこともできるなんて勉強になりました。

あとlong doubleにしても誤差が10^-9以下にならずに辛いなぁと思ってましたが、相対誤差が10^-9でいいのでdoubleでもいいです。

int N;
long double d, x;

long double loop(int n, long double D, long double X) {
	if(n == 0) return 0.0;
	long double nD = (2 * n + 2.0) * D + 5.0 * X;
	long double nX = (2 * n + 4.0) * X;
	long double s = (2.0 * n * D + (2.0 * n - 1.0) * n * X) / (2.0 * n);
	return s + nD / (2.0 * n) * loop(n - 1, 1.0, nX / nD);
}

void solve() {
	cin >> N >> d >> x;
	cout << loop(N, d, x) << "\n";
}