CSA Round 84

https://csacademy.com/contest/round-84/task/manhattan-center/
つら…
A Nが小さいので何しても通ります
B O(N)でやろうとしたんですがバグらせたので普通ににぶたん書いた…
C まず奇数長の棒が奇数本だとできません。そうでなければ奇数長を2本ずつ組み合わせればいいです。偶数長は真ん中で切ればいいです。
D 三分探索…?と思ったけど、冷静にsetを書いてAC。本番バグらせそう。

ll N, K;
vector<pl> P;
vector<vector<ll>> Q;
vector<ll> vx;
set<pl> pos, neg;
vector<pl> L;

int fd(ll v) {
	return lower_bound(all(vx), v) - vx.begin();
}

void solve() {
	cin >> N >> K;
	P.resize(N);
	rep(i, 0, N) {
		cin >> P[i].fst >> P[i].sec;
		vx.pb(P[i].fst);
	}
	sort(all(vx));
	vx.erase(unique(all(vx)), vx.end());
	Q.resize(sz(vx));
	rep(i, 0, N) {
		int at = fd(P[i].fst);
		Q[at].pb(i);
	}
	L.resize(N);
	ll sneg = 0, spos = 0;
	rep(i, 0, N) {
		L[i] = pl(P[i].fst + P[i].sec, i);
	}
	sort(all(L));
	rep(i, 0, K) {
		neg.insert(L[i]);
		sneg += L[i].fst;
	}
	int at = K;
	ll res = linf;
	rep(i, 0, sz(vx)) {
		ll x = vx[i];
		while(at < N && !pos.empty()) {
			if(P[L[at].sec].fst < x) at++;
			else if((*(--pos.end())).fst + x > L[at].fst - x) {
				spos -= (*(--pos.end())).fst;
				sneg += L[at].fst;
				pos.erase(--pos.end());
				neg.insert(L[at]);
				at++;
			}
			else break;
		}
		// debug(vector<pl>(all(pos)), vector<pl>(all(neg)));
		// debug(spos, sneg);
		MIN(res, (-x * sz(neg) + sneg) + (x * sz(pos) + spos));
		rep(j, 0, sz(Q[i])) {
			int v = Q[i][j]; //index;
			if(neg.count(pl(P[v].fst + P[v].sec, v))) {
				sneg -= P[v].fst + P[v].sec;
				spos += P[v].sec - P[v].fst;
				neg.erase(pl(P[v].fst + P[v].sec, v));
				pos.insert(pl(P[v].sec - P[v].fst, v));
			}
		}
	}
	cout << res << "\n";
}

E 複数の直線の最小値になって、傾き0になってから更に値が小さくなることはないのでこっちは三分探索できます。あとは全方位木DPして...と思ったんですが、再帰するの忘れて永遠にバグらせました。悲しい。バグが直ってもTLE。黄金比探索にしてもダメです。でもよくよく考えると、実は頂点0から普通にdfsするだけで答えが求まります。これは面白い(手のひら返し)。下のコードは黄金比探索です。

int N; ll D;
int S[250010], T[250010];
ll C[250010], A[250010];
vector<pi> G[250010];
ll ans = 0;


ll dfs(int v, int p, ll m) {
	ll res = 0;
	rep(i, 0, sz(G[v])) {
		int n = G[v][i].fst;
		if(n == p) continue;
		ll u = dfs(n, v, m); //don't forget this
		u += C[G[v][i].sec] + A[G[v][i].sec] * m;
		MAX(ans, res + u);
		MAX(res, u);
	}
	return res;
}



ll val(ll m) {
	ans = 0;
	dfs(0, -1, m);
	return ans;
}

void solve() {
	cin >> N >> D;
	rep(i, 0, N - 1) {
		cin >> S[i] >> T[i] >> C[i] >> A[i];
		S[i]--;
		T[i]--;
		G[S[i]].pb(pi(T[i], i));
		G[T[i]].pb(pi(S[i], i));
	}

	ll lv = 0, rv = D + 1;
	double phi = (1.0 + sqrt(5)) / 2.0;
	while(rv - lv > 2) {
		ll m1 = (lv * phi + rv) / (1 + phi);
		ll m2 = (lv + rv * phi) / (1 + phi);
		if(val(m1) <= val(m2)) {
			rv = m2;
		}
		else lv = m1;
	}
	pl ans = pl(linf, -1);
	rep(i, 0, 2) {
		if(lv + i <= D) MIN(ans, pl(val(lv + i), lv + i));
	}
	cout << ans.sec << "\n";
	cout << ans.fst << "\n";
}

F グラフさえできればあとはkruskalをやれば答えが求まります。45度回転して、ある点vを中心に平面を8分割(y=0,x=0,y=x,y=-x)すると、分割された各領域について、一番vに近い点以外は、vと結ぶ必要がないことが証明できるので、斜めに平面走査してそのような点を求めればいいです。TLEがきつくていろいろ不毛な高速化をしてAC。

int N, E = 0;
struct edge { int u, v, cost; };

bool comp(const edge& e1, const edge& e2) {
	return e1.cost < e2.cost;
}

//int N, E; add this////////////////////////////
edge es[2000010];

ll kruskal() {
	sort(es, es + E, comp);
	UF uf(N);//init union_find
	ll res = 0;
	for(int i = 0; i < E; i++) {
		edge e = es[i];
		if(!uf.same(e.u, e.v)) {
			res += 1LL * e.cost * uf.sd(e.u) * uf.sd(e.v);
			uf.unite(e.u, e.v);
		}
	}
	return res;
}

int X[MAX_N], Y[MAX_N];

int fd(const vi& vec, int v) {
	return lower_bound(all(vec), v) - vec.begin();
}

vector<int> Q[MAX_N];

void pre() {
	vector<int> qx;
	vector<int> vx;
	vector<int> vy;
	segtree sx, sy;
	rep(i, 0, N) {
		qx.pb(X[i] + Y[i]);
		vx.pb(X[i]); vy.pb(Y[i]);
		Q[i].clear();
	}
	sort(all(qx));
	qx.erase(unique(all(qx)), qx.end());
	sort(all(vx));
	vx.erase(unique(all(vx)), vx.end());
	sort(all(vy));
	vy.erase(unique(all(vy)), vy.end());
	sx.init(sz(vy));
	sy.init(sz(vx));
	rep(i, 0, N) {
		int at = fd(qx, X[i] + Y[i]);
		Q[at].pb(i);
	}
	rep(i, 0, sz(qx)) {
		rep(j, 0, sz(Q[i])) {
			int x = X[Q[i][j]], y = Y[Q[i][j]], id = Q[i][j];
			int xat = fd(vx, x), yat = fd(vy, y);
			sx.update(0, yat, T(pi(xat, id)));
			sy.update(0, xat, T(pi(yat, id)));
		}
		rep(j, 0, sz(Q[i])) {
			int x = X[Q[i][j]], y = Y[Q[i][j]], id = Q[i][j];
			int xat = fd(vx, x), yat = fd(vy, y);
			pi px = sx.get(yat, sz(vy)).v;
			pi py = sy.get(xat, sz(vx)).v;
			if(px.sec != -1) add_edge(id, px.sec, (X[id] - X[px.sec]) / 2);
			if(py.sec != -1) add_edge(id, py.sec, (Y[id] - Y[py.sec]) / 2);
			sx.update(0, yat + 1, T(pi(xat, id)));
			sy.update(0, xat + 1, T(pi(yat, id)));
		}
	}
}

void solve() {
	cin >> N;
	rep(i, 0, N) {
		int x, y;
		cin >> x >> y;
		X[i] = x - y;
		Y[i] = x + y;
	}
	rep(q, 0, 4) {
		pre();
		rep(i, 0, N) {
			int x = X[i], y = Y[i];
			X[i] = -y;
			Y[i] = x;
		}
	}
	cout << kruskal() << "\n";
}

CSAたくさんやれば実装強くなりそうですね。