[BOJ 13339 // C++] XOR 수열

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 13339번 문제인 XOR 수열이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/13339 

13339번: XOR 수열

같은 자릿수로 표현된 서로 다른 두 이진수 x와 y의 대소는 처음으로 달라지는 가장 높은 자리가 0인지 1인지를 이용하면 판별할 수 있다.

 

위의 관찰을 이용하면 가장 높은 i개의 자리가 같고 i+1번째 자리가 존재하는 이진수들 사이의 i<j이면서 A[i]<A[j]인 쌍 (i,j)의 개수는 다음과 같이 구할 수 있다:

1) i+1번째 자리가 서로 다른 수들 사이의 대소 쌍의 개수를 구한다. 이는 DP를 이용해 O(집합의 크기)에 구할 수 있다.

2) 순서를 유지하며 i+1번째 자리까지 같은 수들끼리 모은다.

3) 2에서 구한 각 모음에 대해 1로 돌아간다.

 

위의 알고리즘을 구현하면서, 각 자릿수를 그대로 두는 경우와 반전시키는 경우 중 더 많은 쌍을 주는 경우를 골라 문제를 해결하자. 이 때 앞서 서로 다른 집합으로 분리된 집합이더라도 같은 자리는 그대로 유지되거나 반전되어야 함에 유의해 구현하자.

 

집합을 아무리 나눠도 원소의 개수는 변하지 않으므로 시간복잡도는 $O(MlgN)$이다.

위의 과정을 구현하면서 빈 집합을 계속 생성하면 총 N개의 집합이 만들어지므로 원소가 존재하는 집합만을 생성하도록 유의하자.

 

답이 32비트 정수 자료형 범위를 넘을 수 있으므로 유의해 구현하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <utility>
using namespace std;
typedef long long ll;

int N, K;
vector<vector<int>> vec;
vector<vector<int>> tmp;

ll ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> K >> N;
	K >>= 1;

	vec.emplace_back();
	vector<int>& v = vec[0];

	while (N--) {
		int x; cin >> x;
		v.emplace_back(x);
	}

	while (K) {
		ll val0 = 0, val1 = 0;
		for (auto& V : vec) {
			if (V.size() < 2) continue;
			ll cnt0 = 0, cnt1 = 0;
			tmp.emplace_back();
			tmp.emplace_back();
			vector<int>& V0 = tmp[tmp.size() - 2];
			vector<int>& V1 = tmp[tmp.size() - 1];

			for (auto& x : V) {
				if (x & K) {
					V1.emplace_back(x ^ K);
					x = 1;
				}
				else {
					V0.emplace_back(x);
					x = 0;
				}

				if (x) val1 += cnt0, cnt1++;
				else val0 += cnt1, cnt0++;
			}
		}

		ans += max(val0, val1);

		K >>= 1;
		swap(vec, tmp);
		tmp.clear();
	}

	cout << ans;
}