SRM 409 DIV1 Hard GridColoring

SRM 確率 期待値の線形性 独立にやる

問題 Editorial

問題

rows×colsのグリッドがある。以下の操作をK回する：

  1. ランダムにセルを選び、それをAとする。
  2. ランダムにセルを選び、それをBとする。
  3. AとBを頂点とする矩形上に色を塗る

AとBは独立に選ばれる。セルは全て等確率で選ばれる。色は上書きされる。
K回操作をした後に色が塗られているセルの数の期待値を求めよ。

  • 1 ≦ rows, cols ≦ 1000
  • 0 ≦ K ≦ 100

解答

期待値の期待値より、それぞれのセルが塗られている確率がわかればよい。また、K回で塗られている確率は"1-(1回で塗られない確率)^K"である。よって単に塗られる確率を求める問題となった。
重要な観察として、これはx,y軸独立に考えることが出来るということ。つまり、(x,y)が塗られる確率 = このy行目が塗られる確率 * このx列目が塗られる確率。このそれぞれを求めるには実際にシミュレーションしてみれば良い。Θ(h^3+w^3+hw)だが、最内ループは連続したメモリ領域への足し算なのでそのままでも間に合うし、累積和の逆法でΘ(h^2+w^2+hw)にもなる。
Editorialによると、シミュレーションしなくても簡単な式として確率は出せるようだ。

コード

#include <vector>
#include <cmath>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
using namespace std;
struct GridColoring {
	vector<double> solve(int n) {
		vector<double> r(n);
		rep(i, n) rep(j, n) {
			int x = min(i, j), y = max(i, j);
			rer(k, x, y) r[k] += 1. / n / n;
		}
		return r;
	}
	double area(int K, int h, int w) {
		vector<double> y = solve(h), x = solve(w);
		double r = 0;
		rep(i, h) rep(j, w) {
			double p = 1 - y[i] * x[j];
			r += 1 - pow(p, K);
		}
		return r;
	}
};