SRM547 Div1 Easy - Pillars

問題

2本の塔があり、距離はwである
これらの塔の高さは1本目が[1,x]、2本目が[1,y]の範囲から等確率で決まる
2本の塔それぞれの頂上同士をまっすぐなロープで繋ぐ
ロープの長さの期待値を求めよ

1 <= w <= 10^3
1 <= x, y <= 10^5

解法

1本目の塔の高さをkに固定する
更に2本目の高さがmになる場合、
ロープの長さ L(m) = sqrt(|k-m|^2 + w^2)
確率 p(m) = 1/xy
となる
1本目の塔の高さがkになる場合の期待値はΣL(i)p(m) = 1/xy * ΣL(m)である
ΣL(m)は累積和を使っていい感じに計算すればO(1)で求められる

・いい感じとは？
s[i]: Σ (|k-m|がjであるときのpの値) (0 <= j <= i)
を事前に求めておいて、

(kがyより大きいとき)
s[k-1] - s[k-y-1]
(そうじゃないとき)
m<=kのぶん: s[k-1]
k＜mのぶん: s[y-k] - s[0]

これらをxyで割ったものを答えに足していく

実装

s[]を埋めるときのiはlonglongです

class Pillars {
public:
	double getExpectedLength(int w, int x, int y) {
		double s[100100] = {}, res = 0;
		rep(i,100010) s[i] = sqrt(w*w + i*i) + (i ? s[i-1] : 0);
		reps(k,1,x+1) {
			if (y<k) res += s[k-1] - s[k-y-1];
			else res += s[k-1] + s[y-k] - s[0];
		}
		return res/x/y;
	}
};