CODE FESTIVAL 2016 Grand Final,E: Water Distribution

https://cf16-exhibition-final-open.contest.atcoder.jp/tasks/cf16_exhibition_final_e

初手が難しい…。

グラフの水の容量がB,水をやり取りする辺の距離の合計をA,都市の数をKとすると、なんと最大値は(B-A)/Kであることが証明できます。
Aは都市K個の最小全域木のコストにするのが最適なのは自明ですね。
あとは連結成分が複数ある場合を考えればいいです。これはよくあるO(N*3^N)のDPでできます。

絶対二分探索でしょ、って思いましたが全然違いましたね…。見通し悪かったらすぐ方針を変えるべきなのはわかっているけどなかなかできないです…。必要条件が実は十分条件でもある場合のように、上界を見つけたらそれが最大値かどうか見てみるのも重要ですね。

typedef pair<pi, double> pd;

int N;
double C[(1 << 15)];
double dp[(1 << 15)];

double X[15], Y[15], cap[15];

int par[MAX_N];

int find(int p) {
	if(p == par[p]) return p;
	else return par[p] = find(par[p]);
}

double dist(int a, int b) {
	double dx = X[a] - X[b], dy = Y[a] - Y[b];
	return sqrt(dx * dx + dy * dy);
}

double pre(int bit) {
	vector<pd> e;
	rep(i, 0, N) {
		rep(j, i + 1, N) {
			if(!(bit & (1 << i)) || !(bit & (1 << j))) continue;
			e.pb(make_pair(pi(i, j), dist(i, j)));
		}
	}
	sort(all(e), [](const pd& p1, const pd& p2){return p1.sec < p2.sec;});

	rep(i, 0, N) par[i] = i;
	double res = 0;
	for(auto p : e) {
		int a, b;
		tie(a, b) = p.fst;
		double d = p.sec;
		a = find(a); b = find(b);
		if(a != b) {
			res -= d;
			par[a] = b;
		}
	}

	int cnt = 0;
	rep(i, 0, N) {
		if(!(bit & (1 << i))) continue;
		cnt++;
		res += cap[i];
	}
	return res / cnt;
}

void solve() {
	cin >> N;
	rep(i, 0, N) cin >> X[i] >> Y[i] >> cap[i];
	rep(bit, 1, (1 << N)) {
		C[bit] = pre(bit);
	}
	rep(i, 0, (1 << N)) dp[i] = -inf;

	dp[0] = inf;
	rep(bit, 0, (1 << N)) {
		vector<int> vec;
		rep(i, 0, N) {
			if(!(bit & (1 << i))) vec.pb(i);
		}
		int sn = sz(vec);
		rep(bit2, 1, (1 << sn)) {
			int sbit = 0;
			rep(i, 0, N) {
				if(!(bit2 & (1 << i))) continue;
				sbit |= (1 << vec[i]);
			}
			dp[bit | sbit] = max(dp[bit | sbit], min(dp[bit], C[sbit]));
		}
	}
	cout << dp[(1 << N) - 1] << "\n";
}

比較関数をオシャレにラムダ式でキメてみました。
あと3^N*DPのもっと良い書き方があるみたいなので後で見ておきます。今は配列使っていて定数倍めちゃくちゃ重いです。