[XOR] codeforces #770: B. Fortune Telling

문제 링크: https://codeforces.com/contest/1634/problem/B
전체 코드: https://github.com/evelyn82ny/Algorithm/blob/master/bitwise/_ps/cf_770_b.cpp

Alice 와 Bob 은 초기 값과 n 개의 수로 덧셈과 XOR 연산하여 target 값을 누가 만들 수 있는지 구하는 문제이다.

vector<int> v;
bool isWinner(int sum, int index, const int target) {
	if(index == v.size()) 
    	return sum == target;
        
 	if(isWinner(sum + v[index], index + 1, target)) 
    	return true;
    return isWinner(sum ^ v[index], index + 1, target);
}

위와 같이 n 개의 수에 대한 모든 경우를 탐색하여 찾고자 하는 target 값과 같은지 판별할 수 있다. 하지만 n 은 최대 10^5개가 주어진다. 위 로직은 O(2^n) 의 시간복잡도이므로 최악의 경우 O(2^100,000) 으로 시간초과가 발생한다.

meet in the middle 방식을 적용하고자 n 을 반으로 나눠도 O(2^50000) 의 시간복잡도로 시간초과가 발생하므로 해결할 수 없다.

bitwise

덧셈 연산과 XOR 연산 결과의 마지막 비트가 같다는 점을 이용해 O(N) 의 시간복잡도로 해결할 수 있다.

홀수, 짝수로 연산할 수 있는 조합은 다음과 같다.

홀수, 홀수

• 홀수 + 홀수는 짝수로 마지막 bit 가 0이다.
• 홀수 ^ 홀수는 둘다 마지막 bit 가 1이므로 ^ 연산 후 0 이 된다.

짝수, 짝수

• 짝수 + 짝수는 짝수로 마지막 bit 가 0이다.
• 짝수 ^ 짝수는 둘다 마지막 bit 가 0이므로 ^ 연산 후 0 이 된다.

홀수, 짝수

• 홀수 + 짝수는 홀수로 마지막 bit 가 1이다.
• 홀수 ^ 짝수는 서로 마지막 bit 가 다르므로 ^ 연산 후 1 이 된다.
  
  

홀수, 짝수로 연산할 수 있는 모든 조합에서 덧셈, XOR 연산하면 모두 마지막 비트가 같은 결과가 나온다. 즉, 주어진 n 개의 수를 어떠한 조합으로 덧셈, XOR 연산을 한 결과의 마지막 비트는 주어진 n 개를 모두 더하거나, 모두 ^ 연산한 결과의 마지막 비트와 같다.

Alice 의 초기 값이 x 라면 Bob 의 초기 값은 x + 3 을 갖는다. 즉, Alice 의 초기 값이 짝수라면 Bob 의 초기 값은 홀수이므로 Alice 와 Bob 의 마지막 비트는 서로 다르다.

즉, Alice 의 마지막 비트와 n 개의 수를 연산한 마지막 비트를 ^ 연산한 결과가 target 의 마지막 비트와 같으면 Alice 는 target 을 만들 수 있다는 것을 알 수 있다.

vector<int> v;
int sumOfArrays, alice;

for(int i = 0; i < v.size(); ++i) {
	sumOfArrays = (sumOfArrays + v[i]) % 2;
    //마지막 비트만 필요하기 때문에 나머지 연산
}

if((alice + sumOfArrays) % 2 == target % 2) cout << "Alice";
else cout << "Bob";