Codeforces #193 Div2. D. Theft of Blueprints

少しずつ難しくなってきた。
http://codeforces.com/contest/332/problem/D

問題

S個の惑星があり、互いの移動可否および移動可能ならそのコストが与えられる。
惑星の移動可否情報は、S個中任意のK個を選ぶと、K個のすべてに隣接するK個以外の星は1つしかないことが保証される。

S個中任意のK個を選んだ時、K個の確保しからその１個の星へ移動するコストの総和の平均値を答えよ。

解法

題意より、ある星がK個以上の星L個と隣接しているとき、L個中K個選ぶやり方は通りあり、各星は通りに含まれる。

よって、K個以上の星と隣接する星があれば、各コストを倍して加算していく。
最後に全選択パターンので割ればよい。

途中をdouble型で計算しておいても途中でオーバーフローしないようだ。

int N,K;
int M[2010][2010];
double C[2010][2010];

void solve() {
	int r,i,j,k,l,x,y,tx,ty;
	
	cin>>N>>K;
	FOR(x,N-1) FOR(y,N-1-x) M[x][x+1+y]=M[x+1+y][x]=GETi();
	
	FOR(i,2001) C[i][0]=C[i][i]=1;
	for(i=1;i<2001;i++) for(j=1;j<i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j]);
	double R=0;
	FOR(x,N) {
		double T=0;
		j=0;
		FOR(y,N) if(x!=y && M[x][y]!=-1) j++,T+=M[x][y];
		if(j>=K) R+=T*C[j-1][K-1];
	}
	R/=C[N][K];
	cout << (ll)R << endl;
}

まとめ

こちらの方がCよりは解きやすかった。