SRM 547 250pt : Pillars

TopCoder

問題概要

hypot(w, x-y)の期待値を求める。xは[1,X]から一様に、yは[1,Y]から一様に選ばれる。X,Y<10^5。

考えたこと

  • とりあえずオーバーフローが撃墜ケースになることは分かる。
  • 何はともあれ全探索だ。xとyを全部回すのはO(X*Y)だし、(x-y)^2もO(X*Y)だから残念ながら無理。
    • Oh…。
  • こういうのは片方を全探索してもう一方を綺麗な式で求めるのが定石。
  • うーんsqrtのせいで加法性が使えない。
  • じゃあ二乗だ。求める期待値はsqrt(w*w + x*x + y*y - 2*x*y)で、2乗をとると加法性が使える。x*xの期待値やy*yの期待値はO(X+Y)で求められるしxとyは独立だからE[x*y]=E[x]*E[y]で美味しい。
  • で、後はsqrt(w*w + x*x + y*y - 2*x*y)の分散さえ求められれば…って無理だこれ。
  • 分散はちょっと捨てよう。うーんうーん…。あっ、(x-y)の範囲ってO(X+Y)でしかないじゃないか！
  • (x-y)のとる値の出現回数をそれぞれカウントするのは、いもす法でいける。
    • いもす法とは、区間への加算をうまく処理するテクニック。
    • 多分もっと綺麗に式一発で書けるとは思うけど、ミスが怖いので確実な方法でやるのが一番。
  • 後は書くだけ。ちょっと焦って凡ミス連発したけど何とか通った。

acceptされたコード

#include <cmath>
using namespace std;

typedef long long int64;

const int MAX_X = (int)(1e5);

int64 count[2*MAX_X + 2];

double sq(double x) {
	return x * x;
}

struct Pillars {

	double getExpectedLength(int w, int x, int y) {

		const int SHIFT = MAX_X;
		for (int i = 1; i <= x; ++i) {
			count[i-y+SHIFT]++;
			count[i+SHIFT]--;
		}
		for (int i = 1; i < 2*MAX_X+2; ++i) {
			count[i] += count[i-1];
		}
		int64 total = 0;
		double ret = 0.0;
		for (int i = 0; i < 2*MAX_X+2; ++i) {
			ret += count[i]*sqrt(sq(w) + sq(i - SHIFT));
			total += count[i];
		}
		ret /= total;

		return ret;
	}

};