BOJ 33276 XOR 머신

문제 링크입니다.

문제 요약

비어 있는 수열 $B$에 수열 $A$의 원소 혹은 원하는 값을 XOR해 수열 $A$의 짝수 길이 부분 수열의 XOR합 중 최댓값을 구하는 전략을 두 개 구상해야 합니다. 두 전략을 통틀어,

• $B$에 $A$의 원소를 총 $3N$번 XOR할 수 있습니다.
• $B$에 원하는 값을 총 $2N$번 XOR할 수 있습니다.
• 두 번을 합쳐 총 $2N$개의 $B$의 원소에 대한 최대 부분 XOR합을 얻을 수 있습니다. 예를 들어 각 전략에서 $N$개의 원소에 대한 최대 부분 XOR합을 얻을 수 있어요.

풀이

투 스텝은 아닌데 문제를 두 번 풀어야 됩니다. 그리고 두 번 푸는 동안 사용할 수 있는 총 쿼리 횟수가 정해져 있네요. 서로 다른 두 전략을 세워 문제를 해결하라는 출제자의 의도를 엿볼 수 있습니다.

어쨌거나 $A_1$ 부터 $A_N$까지의 값을 $B$에 집어넣어야 뭘 알아내든 말든 할테니 두 전략에 각각 $N$번의 A 쿼리를 나눠 줍시다. 그러면 $N$번의 A 쿼리랑 $2N$번의 C 쿼리가 남겠네요.

전략 I. A 쿼리 $2N$번이 주어졌을 때

남은 $N$개의 A 쿼리를 한쪽에 몰아줍시다. 그러면 $B$의 $N$개 항에 두 $A$의 원소를 XOR한 값을 저장할 수 있습니다. 여기서 $x \oplus x = 0$임을 활용해 짝수 길이의 부분 배열만을 뽑아낼 수 있도록 조작해 봅시다.

$i = 1..N-1$까지, $B_i := A_i \oplus A_{i+1}$로 만들어 줍시다. 총 $(2N-2)$번의 A 쿼리가 필요하겠네요. 그러면 $B$의 원소를 여럿 골랐을 때, $B_1 \oplus B_2 = ( A_1 \oplus A_2 ) \oplus ( A_2 \oplus A_3 ) = A_1 \oplus A_3$과 같이 항상 짝수 개의 $A_i$들의 XOR로 총 XOR 값이 정해짐을 확인할 수 있어요.

전략 II. A 쿼리 $N$번, C 쿼리 $2N$번이 주어졌을 때

$i = 1..N$까지 $B_i = A_i$라고 생각합시다. 우리는 여기서 짝수 개만 선택하는 경우가 홀수 개만 선택하는 경우보다 항상 더 큰 XOR 값이 나오도록 C 쿼리를 적당히 활용해 볼 거에요.

만약 홀수 개만 선택하는 게 이득이도록 만드는 거였다면 좀 더 간단했을 겁니다. $A_i < 2^{29}$이므로, 각 $B_i$에 $2^{29}$를 XOR해 주면 홀수 개의 $B_i$를 골랐을 때만 $2^{29}$가 XOR 값에 더해져 항상 $A_i$들의 XOR 값보다 큰 값이 나오게 되거든요.

우리는 짝수 개일 때를 골라내야 하니, 임의로 $2^{29}$를 포함하는 항을 하나 더 만들고 그 항을 고르지 않으면 안 되도록 만들어 그 항을 포함해 홀수 개의 항을 고르도록 만들 수 있습니다. $2^{30}$이 다행히 쿼리로 보낼 수 있는 $x$ 범위 안에 들어가므로, $B_{N+1} = 2^{30}+2^{29}$를 만들어 총 $N+1$개의 항의 최대 XOR을 구하면, $A$에서의 최대 XOR + $B_{N+1}$을 답으로 얻을 수 있습니다.

이상의 과정에서 전략 I에서는 $N-1$개의 항에 대해 q 쿼리를 날리게 되고, 전략 II에서는 $N+1$개의 항에 대해 q 쿼리를 날리게 되므로 총 $2N$개 이하의 항에 대해 쿼리를 날린 것이 됩니다. 문제의 조건에 딱 맞게 떨어지네요.

코드

#include<bits/stdc++.h>
using namespace std;

int main(){
	int n; cin >> n;
	for(int i = 1; i < n; i++){
		cout << "A " << i << ' ' << i << endl;
		cout << "A " << i << ' ' << i+1 << endl;
	}
	cout << "Q " << n-1 << ' '; for(int i = 1; i < n; i++) cout << i << ' '; cout << endl;
	int ans; cin >> ans; cout << "! " << ans << endl;
	
	for(int i = 1; i <= n; i++) cout << "A " << i << ' ' << i << endl;
	for(int i = 1; i <= n; i++) cout << "C " << i << ' ' << (1<<29) << endl;
	cout << "C " << n+1 << ' ' << (1<<29)+(1<<30) << endl;
	cout << "Q " << n+1 << ' '; for(int i = 1; i <= n+1; i++) cout << i << ' '; cout << endl;
	cin >> ans; cout << "! " << ans-(1<<29)-(1<<30) << endl;
	return 0;
}