SRM 547 div1 easy: Pillars

問題

TopCoder Statistics - Problem Statement

w だけ離れて二本の柱が立っている。
一方の長さは 1, 2, ..., x の長さを等確率で取り, もう一方の長さは 1, 2, ..., y の長さを等確率で取る。二本の柱の先端距離の期待値を求めよ。

解法

1 本目の柱と 2 本目の柱の diff が h になる場合の数がいくつあるのかを考えます。h = 0 の時は min(x, y) 通りだけあります。
h > 0 の時は,
(1, 1+h), ..., (y-h, y)
(1+h, 1), ..., (x, x-h)
の場合があります。

diff が h の場合の長さは sqrt(w*w + h*h) なので計算します。オーバーフローに注意です。

class Pillars {
public:
    double getExpectedLength(int w, int x, int y) {
    	double sum = 0;
    	sum += min(x, y)*w;
        for (int h = 1; h < 100000; h++) {
        	int cnt = 0;
        	if (y > h) cnt += min(y-h, x);
        	if (x > h) cnt += min(x-h, y);
        	sum += cnt*sqrt(w*w+(ll)h*h);
        }
        return sum/((double)x*y);
    }
};