kmjp's blog

競技プログラミング参加記です

TopCoder SRM 636 Div1 Medium ClosestRabbit

SRM

これは難しいけど面白かった。
http://community.topcoder.com/stat?c=problem_statement&pm=13366

問題

N*Mのグリッドがあり、いくつか壁のセルがある。
壁以外のセルにランダムにr匹の兎を配置する。
(各セルへの兎の配置確率は等しい)

各兎は、そこから他の最寄の兎に辺を張る。
最寄の定義は以下の通り。

  • 兎同士の距離はユークリッド距離である。
  • 同じ距離の兎が複数いる場合、行番号が最小なものの方が近いとみなす。行番号も等しい2匹の兎は、列番号が小さいものの方が近いとみなす。

r匹の兎を頂点とみなし、各兎から張る計r本の辺と合わせたグラフを考える。
このグラフが何個の連結成分からなるか、期待値を答えよ。

解法

r個の頂点とr個の辺なので、サイクルが1個できるごとに連結成分が1個できる。
また、サイクルは常に2頂点だけであり３頂点以上のサイクルはできない。

３頂点以上のサイクルがないことを示す。
頂点1,2,3,...Nが互いに2,3,4,...,N,1に辺を張っているとする。
頂点x,yの距離をd(x,y)とすると、

  • d(1,N) ≦ d(1,2)
  • d(2,1) ≦ d(2,3)
  • d(3,3) ≦ d(4,5)
  • ...
  • d(N,N-1) ≦ d(N,1)

これらの不等式は循環関係にあるので、これがすべて満たされるにはすべてのd(x,x±1)が等しくなければならない。
次に距離が全部等しい場合、上記の行番号列番号の制限より、行番号列番号が最小となる頂点pがあると、頂点p-1と頂点p+1が両方頂点pに辺を張ってしまいサイクルにならない。
これが問題とならないのは頂点p-1とp+1が同一、すなわち２頂点のサイクルの場合である。

あとは２頂点のサイクル数の期待値を求める。
それには候補の２頂点x,yを総当たりし、これらがサイクルになる確率の総和を取ればよい。
x,yがサイクルになるのは、d(x,z)＜d(x,y)かつd(y,z)＜d(y,x)となる頂点zが選択されないことである。
よってzを総当たりし、d(x,z)＜d(x,y)かつd(y,z)＜d(y,x)とならないものがp個あったとする。
するとx,yを除き(r-2)個の頂点を選択するとき、それらがp個の中からだけ選ばれる確率なので \frac{{}_{p} C_{r-2}}{{}_{N-2} C_{r-2}}を計算すればよい。

Combinationはdouble型変数でパスカルの三角形を作って計算すればよい。

double comb(int P_,int Q_) {
	static const int N_=1020;
	static double C_[N_][N_];
	
	if(C_[0][0]==0) {
		int i,j;
		FOR(i,N_) C_[i][0]=C_[i][i]=1;
		for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j]);
	}
	if(P_<0 || P_>N_ || Q_<0 || Q_>P_) return 0;
	return C_[P_][Q_];
}

ll dist[21][21][21][21];

class ClosestRabbit {
	public:
	
	double getExpected(vector <string> B, int r) {
		int H,W,N;
		int y,x,y2,x2,y3,x3;
		H=board.size();
		W=board[0].size();
		N=0;
		
		FOR(y,21) FOR(x,21) FOR(y2,21) FOR(x2,21)
			dist[y][x][y2][x2]=((x2-x)*(x2-x)+(y2-y)*(y2-y))*1000LL+y2*30+x2;
		FOR(y,21) FOR(x,21) dist[y][x][y][x]=0;
		FOR(y,H) FOR(x,W) N+=board[y][x]=='.';
		
		double ret=0;
		FOR(y,H) FOR(x,W) if(B[y][x]=='.') {
			FOR(y2,H) FOR(x2,W) if((y2>y || (y2==y&&x2>x)) && B[y2][x2]=='.') {
				int ok=0;
				FOR(y3,H) FOR(x3,W) if(B[y3][x3]=='.' && dist[y][x][y3][x3] && dist[y2][x2][y3][x3]) {
					if(dist[y][x][y3][x3]<dist[y][x][y2][x2] || dist[y2][x2][y3][x3]<dist[y2][x2][y][x]) ok++;
				}
				if(N-2-ok<r-2) continue;
				ret+=comb(N-2-ok,r-2)/comb(N-2,r-2);
			}
		}
		return ret*r*(r-1)/(N*(N-1));
		
	}
}

まとめ

２頂点サイクルができる確率の総和だと気づけばすぐ。
自分は本番２点がペアにならない確率の総和を求めようとして失敗した。