TopCoder SRM 503 Div1 Medium: KingdomXCitiesandVillages

解法

村vについて考える。

• 村vが最初に選ばれる確率は1/M
• 村vからj番目に近い村wに道路を敷く時、
  • 村wは接続済みでなければならない
  • 村wよりも村vに近い村は接続されていてはならない
  • それ以外の村が接続されているかどうかは答に影響しないので、「それ以外の村がk個接続されている時」というようにまとめてkを変化させれば良い。

解法

import java.util.ArrayList;
import java.util.Collections;

public class KingdomXCitiesandVillages {

	public double determineLength(int[] cX, int[] cY, int[] vX, int[] vY) {
		int N = cX.length;
		int M = vX.length;

		double ans = 0;
		for (int v = 0; v < M; v++) {
			// 村vから道を敷く場合を考える　

			// 街への最短距離
			double cityDist = 1e9;
			for (int j = 0; j < N; j++) {
				cityDist = Math.min(cityDist, dist(vX[v], vY[v], cX[j], cY[j]));
			}

			// 自身以外の村への距離
			ArrayList<Double> villageDist = new ArrayList<>();
			for (int v2 = 0; v2 < M; v2++) {
				if (v2 != v) {
					villageDist.add(dist(vX[v], vY[v], vX[v2], vY[v2]));
				}
			}
			Collections.sort(villageDist);

			// 村vが最初に選ばれる
			ans += cityDist / M;

			for (int j = 0; j < M - 1; j++) {
				// 村vからj番目(0-indexed)に近い村が選ばれる時、少なくともj個の村は街と接続されていない
				int otherVillages = M - 1 - j;
				double dist = Math.min(villageDist.get(j), cityDist);
				for (int k = 1; k <= otherVillages; k++) {
					// 村vが接続される前に、 確実に接続されていないj個の村以外の村のうち、k個の村が接続されているとする。

					// j番目の村を除くotherVillages-1のうちk-1個が選ばれる組み合わせの数
					double combi1 = mCn(otherVillages - 1, k - 1);
					// 全ての街からk個を選ぶ組み合わせ
					double combi2 = mCn(M, k);

					ans += dist * combi1 / combi2 / (M - k);
				}
			}
		}

		return ans;
	}

	private double mCn(int m, int n) {
		// 愚直にやっても大した量にならない
		double combi = 1.0;
		for (int i = 0; i < n; i++) {
			combi *= (m - i);
			combi /= (i + 1);
		}
		return combi;
	}

	private double dist(int x1, int y1, int x2, int y2) {
		long dx = x1 - x2;
		long dy = y1 - y2;
		return Math.sqrt(dx * dx + dy * dy);
	}
}