Codeforces #456 Div2 D. Fishes

最難のCが解けたけどEは解けなかった。
http://codeforces.com/contest/912/problem/D

問題

H*Wの２次元グリッドがある。
このうちK個のセルを特殊なセルとして配置することを考える。
グリッド上で当確率でR*Rの正方形型の位置を指定したとき、特殊セルを含む数の期待値を最大化するように配置した場合の期待値を答えよ。

解法

H行のうち連続するR行を選ぶときにr行目が選ばれる確率をF(r)、W列のうち連続するR列を選ぶときにc列が選ばれる確率をG(c)とする。
r列c行目が選ばれる確率H(r,c)=F(r)*G(c)となる。

H(r,c)が大きい上位K個のセルを選べばよい。
ただし、H*Wは十分大きいためH(r,c)を列挙することはできない。
幸い、H(r,c)=F(r)*G(c)なので、例えばrを固定した場合、H(r,c)はG(c)の大きな順に大きくなる。
そこで、Priority_queueを使い、行枚に未使用な最大のG(c)を順に使うようにし、H(r,c)を求めていけばよい。

ll N,M,R,K;
int ID[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>R>>K;
	
	ll pat=(N-R+1)*(M-R+1);
	vector<ll> V,W;
	FOR(i,N) {
		x=max(0LL,i-R+1);
		y=min(N-R,(ll)i);
		V.push_back(y-x+1);
	}
	FOR(i,M) {
		x=max(0LL,i-R+1);
		y=min(M-R,(ll)i);
		W.push_back(y-x+1);
	}
	
	sort(ALL(V));
	reverse(ALL(V));
	
	priority_queue<pair<ll,int>> Q;
	FOR(i,M) Q.push({W[i]*V[0],i});
	
	double ret=0;
	while(K--) {
		auto a=Q.top();
		Q.pop();
		ret += a.first;
		x=a.second;
		ID[x]++;
		if(ID[x]<V.size()) Q.push({W[x]*V[ID[x]],x});
	}
	
	_P("%.12lf\n",ret*1.0/pat);
}

まとめ

Dは普通なのに、Cがなんだか妙な回だった。