VK Cup 2018 - Round 1

http://codeforces.com/problemset/problem/923/D

A
良問。どこまで減らせるかが貪欲で求まる。
B
雪山について独立に考えれば。
C
よくあるbitのやつ。これtrieでやるのかなぁ…segtreeっぽくしちゃったけど。また使いそうなので貼っときます。

int K = 1;

struct node {
	int lat, rat, sum;
	node() {
		lat = -1, rat = -1, sum = 0;
	}
};

node seg[30 * MAX_N];

void update(int a, int v, int k, int l, int r) { //a.. at, k... segat
	// debug(a, v, k, l, r, seg[k].lat, seg[k].rat);
	if(r - l == 1) {
		seg[k].sum += v;
	}
	else {
		int m = (l + r) / 2;
		if(a < m) {
			if(seg[k].lat == -1) {
				seg[k].lat = K; K++;
			}
			update(a, v, seg[k].lat, l, m); //k
		}
		if(m <= a) {
			if(seg[k].rat == -1) {
				seg[k].rat = K; K++;
			}
			update(a, v, seg[k].rat, m, r);
		}
		seg[k].sum = seg[seg[k].lat].sum + seg[seg[k].rat].sum;
	}
}

int get_min(int a, int bat, int k, int l, int r) {
	if(bat == -1) return l;
	if(!(a & (1 << bat))) { //bat is 0. 0 is preferred
		if(seg[k].lat != -1 && seg[seg[k].lat].sum) {
			return get_min(a, bat - 1, seg[k].lat, l, (l + r) / 2);
		}
		else {
			return get_min(a, bat - 1, seg[k].rat, (l + r) / 2, r);
		}
	}
	else {
		if(seg[k].rat != -1 && seg[seg[k].rat].sum) {
			return get_min(a, bat - 1, seg[k].rat, (l + r) / 2, r);
		}
		else {
			return get_min(a, bat - 1, seg[k].lat, l, (l + r) / 2);
		}
	}
}

void seg_show(int k, int l, int r) {
	debug(k, l, r, seg[k].lat, seg[k].rat, seg[k].sum);
	if(seg[k].lat != -1) {
		seg_show(seg[k].lat, l, (l + r) / 2);
	}
	if(seg[k].rat != -1) {
		seg_show(seg[k].rat, (l + r) / 2, r);
	}
}

int N;
int A[MAX_N], B[MAX_N];

const int mv = 30;

void solve() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];
	rep(i, 0, N) {
		cin >> B[i];
		update(B[i], 1, 0, 0, (1 << mv));
	}
	// seg_show(0, 0, (1 << mv));
	rep(i, 0, N) {
		int t = get_min(A[i], mv - 1, 0, 0, (1 << mv));
		cout << (A[i] ^ t) << "\n";
		// debug(A[i], t);
		update(t, -1, 0, 0, (1 << mv));
	}
}

D
B->Cとできるし、Bの偶数個だけ数えれば良いやんと思ったらいろいろ考えてないケースがたくさんあって場合分け地獄にハマった…
煩雑になったら、何で場合分けするかちゃんと考えなおしたほうがいいですね。