AtCoder Petrozavodsk Contest 001F: XOR Tree

https://apc001.contest.atcoder.jp/tasks/apc001_f

最近同じような問題を解いたのでわかったんですけども、O(3^N)DPをバグらせて悲しくなりました…。

頂点に隣接しているすべての辺のXORを書き込みます。すると、2つの頂点についてある値XでのXORを行い、すべての頂点を0にする問題になりました。そうすれば、頂点の値がiのものの数をciとして、i=0は考えなくて良くて、ci(i>=1)は[ci/2]個のペアを作るのが最適です。あと余ったものでO(3^N)DPをすればいいです。

XORを区間に施す際の一般的なテクニックについてですが、2項の差というよりも、2つの値のXORと考えたほうが良さそうですね。

bitとbit2を混同してWA出したのは情けない…。for(int j = (i - 1) & i; j ; j = (j -1)&i))みたいな書き方を速くマスターしましょう…。

これで1000点埋め完了です。

(3/4更新)

rep(bit, 0, (1 << N)) {
		for(int to = bit; to; to = (to - 1) & bit) {
			MAX(dp[bit], dp[to ^ bit] + ok[to]);
		}
	}
}

このようにしてもできます。vector使わず簡潔でいいですね。
bit^toがbitの部分集合(bitを含まない)となります。

int A[MAX_N];
int cnt[20];

int dp[(1 << 16)];
int ok[(1 << 16)];
vector<int> vec;

void solve() {
	cin >> N;
	rep(i, 0, N - 1) {
		int a, b, c;
		cin >> a >> b >> c;
		A[a] ^= c;
		A[b] ^= c;
	}
	rep(i, 0, N) cnt[A[i]]++;

	int ans = 0;
	rep(i, 1, 16) {
		ans += cnt[i] / 2;
		if(cnt[i] % 2) vec.pb(i);
	}

	M = sz(vec);

	rep(bit, 1, (1 << M)) {
		int tmp = 0, res = 0;
		rep(i, 0, M) {
			if(!(bit & (1 << i))) continue;
			tmp ^= vec[i];
			res++;
		}
		if(tmp == 0) ok[bit] = res - 1;
		else ok[bit] = M;
	}
	fill(dp, dp + (1 << M), M);
	dp[0] = 0;
	rep(bit, 0, (1 << M)) {
		vector<int> vt;
		rep(i, 0, M) {
			if(!(bit & (1 << i))) vt.pb(i);
		}
		rep(bit2, 1, (1 << sz(vt))) {
			int to = 0;
			rep(i, 0, sz(vt)) {
				if(bit2 & (1 << i)) to |= (1 << vt[i]);
			}
			MIN(dp[bit | to], dp[bit] + ok[to]);
		}
	}
	cout << ans + dp[(1 << M) - 1] << "\n";
}