TopCoder SRM 526.5 Div1 Medium MagicBlizzard

これは自力で解けなかった…。
http://community.topcoder.com/stat?c=problem_statement&pm=11690

問題

N匹のトナカイがいる。
各トナカイは、(-R[i], -R[i])～(R[i], R[i])に存在する格子点に均一な確率でA[i]個の雪玉を落とす。
最終的な地面の凸凹具合は、各格子点に落ちた雪玉の2乗和とする。

凸凹具合の期待値を求めよ。

解法

2乗和ということで分散や平均値の特性を使って解くことが考えられる。
Editorialには3つの考え方が書いてあるが、自分が一番すんなり来たのはAlternative Solution 1だった。

すなわち、各格子点で雪玉数の2乗和を計算するということは、同じ格子点にある雪玉ペア1つにつき1カウントすると考えられる。
(同じ雪玉同士のペアや、順序が異なるものも重複カウントする)

よって、後は各雪玉同士が同じ位置に行く確率を求めればよい。
2つの雪玉が同じ位置に行く確率は、2つの雪玉を落とすトナカイのうち、広範囲に雪玉を落とすトナカイのR[i]で定まる。

class MagicBlizzard {
	public:
	double expectation(vector <int> range, vector <int> amount) {
		int N=range.size();
		int i,x,y;
		
		double ret=0;
		FOR(x,N) FOR(y,N) {
			if(x==y) {
				double r=2*range[x]+1;
				ret+=amount[x];
				ret+=amount[x]*(ll)(amount[x]-1)/(r*r);
			}
			else {
				double r=max(2*range[x]+1,2*range[y]+1);
				ret+=amount[x]*amount[y]/(r*r);
			}
		}
		
		return ret;
	}
};

まとめ

ややこしめの期待値問題や幾何問題は周りも苦手な人が多いのか、正答率が低いイメージ。