Codeforces #233 Div1. B. Painting The Wall

ちょっと考えるAより、解法がすぐ思いつくBの方が簡単では…。
http://codeforces.com/contest/398/problem/B

問題

NxNのグリッドがあり、そのうちのいくつかがすでに塗られている。

コスト１を払うと、ランダムでどこかのマスが塗られる(1度塗ったマスが再度塗られることもある)。
全ての行に1個以上塗られているマスがあり、かつ全ての列に1個以上塗られているマスがある状態になれば終了する。

終了までにかかるコストの期待値を答えよ。

解法

状態として(塗られていない行の数,塗られていない列の数)を持ち、再帰的に確率を求めていけばよい。
今の状態を(R,C)とすると、コスト１で以下のように遷移する。

1. (N-R)(N-C)/(N^2)の確率ですでに塗った行・すでに塗った列が選ばれる。この時状態は変わらない。
2. R(N-C)/(N^2)の確率でまだ塗られてない行ですでに塗った列が選ばれる。この時状態(R-1,C)になる。
3. (N-R)C/(N^2)の確率ですでに塗った行でまだ塗られてない列が選ばれる。この時状態(R,C-1)になる。
4. RC/(N^2)の確率でまだ塗られてない行・列が選ばれる。この時状態(R-1,C-1)になる。

状態はN^2で、各状態からの遷移は高々3つと定数なので、全体の計算量はO(N^2)。

int N,M;
double dpdp[2001][2001];
int visr[2001],visc[2001];

double dodo(ll x,ll y) {
	if(x>y) swap(x,y);
	if(dpdp[x][y]>=0) return dpdp[x][y];
	if(x==0 && y==0) return 0;
	
	if(x==0) {
		dpdp[x][y]=dodo(x,y-1)+N/(double)y;
	}
	else {
		dpdp[x][y]=N*(ll)N+x*(N-y)*dodo(x-1,y)+(N-x)*y*dodo(x,y-1)+x*y*dodo(x-1,y-1);
		dpdp[x][y]/=(double)(N*(x+y)-x*(ll)y);
	}
	return dpdp[x][y];
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		visr[x-1]=1;
		visc[y-1]=1;
	}
	FOR(x,N+1) FOR(y,N+1) dpdp[x][y]=-1;
	_P("%.12lf\n",dodo(N-count(visr,visr+N,1),N-count(visc,visc+N,1)));
	
}

まとめ

昔より期待値問題に慣れてきたな。