[BOJ 11191 // C++] Xor Maximization

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

 

이번에 볼 문제는 백준 11191번 문제인 Xor Maximization이다.
문제는 아래 링크를 확인하자.

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

11191번: Xor Maximization

주어진 정수들을 적절히 골라 xor해 얻을 수 있는 최댓값을 찾는 문제이다.

 

각 (60자리) 이진수를 각 자리가 \(F_2\)의 원소인 벡터로 생각하면 \(k\)개의 정수의 xor을 \(k\)개의 벡터의 합으로 나타낼 수 있다. 또한 이러한 벡터의 합의 (이진수로써의) 최댓값은 각 정수를 이진수로 나타낸 벡터들을 모은 행렬 위에서 기저(basis)를 가우스 소거법(Gaussian elimination)을 활용해 구하는 것으로 계산해낼 수 있다. 이를 구현해 문제를 해결하자.

 

위의 개념을 이해했다면 코드를 작성할 때 굳이 각 정수를 이진수의 각 자리로 분리해 비효율적으로 구현할 필요는 없다. 아래와 같이 xor을 이용해 구현해주자.

 

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

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

int N;
ll arr[100000];

ll mx = 0;

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

	cin >> N;
	for (int i = 0; i < N; i++) cin >> arr[i];

	ll dgt = (1LL << 60);
	while (dgt) {
		int idx = 0; ll ival;
		for (; idx < N; idx++) {
			if (arr[idx] & dgt) {
				ival = arr[idx];
				if ((mx & dgt) == 0) mx ^= ival;
				break;
			}
		}
		for (; idx < N; idx++) {
			if (arr[idx] & dgt) arr[idx] ^= ival;
		}

		dgt >>= 1;
	}
	
	cout << mx;
}