Codeforces Round #742 (Div. 2)-B. MEXor Mixup

문제 설명

엘리스는 밥에게 두 정수 $a$와 $b(a>0,b\le 0)$ 를 제시했다. 호기심 많은 소년인 밥은 모든 음이 아닌 정수를 원소로 가지는 배열의 모든 원소의 $MEX$ 값이 $a$이고, 배열의 모든 원소의 $XOR$ 값이 $b$를 만족하는 배열을 만들었다.

밥이 적은 가능한 최소길이를 가진 배열은 무엇일까?

배열의 $MEX$(Minimum EXcluded)는 배열의 원소가 아닌 값 중에서 가장 작은 음이 아닌 정수를 말하고, 배열의 $XOR$은 배열의 모든 원소를 XOR 비트 연산을 한 값을 말한다.

Input
첫번째 줄에는 테스트 케이스의 개수 $t$가 주어진다. $(1\le t\le 5\cdot {10}^4)$

각 테스트케이스는 각각 배열의 $MEX$ 값과 $XOR$ 값을 나타내는 두 정수 $a$ 와 $b(1\le a\le 3\cdot {10}^5,0\le b\le 3\cdot {10}^5)$ 가 주어진다.

Output
각 테스트 케이스마다 배열의 $MEX$ 값이 $a$이고, $XOR$ 값이 $b$인 가장 작은 배열의 길이를 나타내는 정수 하나를 출력한다. 그리고 그러한 답이 존재하는 테스트케이스만 주어진다.

Example
input
5
1 1
2 1
2 0
1 10000
2 10000

output
3
2
3
2
3

문제 접근

사용한 알고리즘: 비트마스킹, 구현
걸린 시간 : 00:20
이 문제는 구현이 어려운게 아니라 이 MEX라는 값의 개념을 모르면 그냥 풀수가 없다. 나도 이 문제를 풀면서 MEX라는 개념을 처음 알았는데, 다음과 같다. 배열에 들어있는 원소가 음이 아닌 정수를 만족한다고 가정할 때, 배열에 있는 원소가 아닌 정수 중에서 가장 작은 값을 말한다.

이렇게만 적으면 당최 뭔 소린지 전혀 이해할 수 없다. 그렇기 때문에 예시를 들어서 설명을 하자.
배열 $a$가 $[0,3,4,6,20,10101010101]$ 라고 할때, $a$의 MEX는 뭘까? 답은 $1$이다.
$a$가 $[0,1,2,3,4,5,6,101203124,6435645335345]$ 라고 할때, $a$의 MEX는 뭘까? 답은 7이다.
첫번째 예시에서는 배열 $a$에 없는 원소를 오름차순으로 적어보자면 $1,2,5,7,8,9,10,11\cdots$ 이다. 이 값중에서 가장 작은 값이 바로 1이기 때문에 답이 1이다.
두번째 예시에서는 배열 $a$에 없는 원소를 오름차순으로 적어보자면 $7,8,9,10,11,12,13,14\cdots$ 이다. 이 값중에서 가장 작은 값이 바로 7이기 때문에 답이 7이다.

이정도면 MEX값은 완벽히 이해했을 것이라고 믿는다. 그러면 MEX값이 $a$가 되기 위해서는 배열을 어떻게 구성하면 최소 길이로 만들 수 있을까? 배열에 없는 원소중에서 가장 작은 값이 $a$가 되면 된다. 즉 배열을 $[0,1,2,\cdots ,a-2,a-1]$ 이렇게 구성한다면 MEX의 값이 $a$ 가된다. 즉 MEX가 $a$가 되기 위해서 필요한 최소 배열의 길이는 $a$이다.

XOR값은 그냥 모든 배열의 XOR값을 계산하면 되는데, 계산의 편의를 위해서 $a$의 최대값인 $300000$ 까지의 bitwise XOR값을 계산하자. 왜냐하면 MEX값이 $a$ 이면 반드시 배열의 구성이 $[0,1,2,\cdots ,a-2,a-1]$ 이렇게 되어야 한다는 것을 알았기 때문이다. 정답 코드에 있는 dp[i]는 $0$ 부터 $i$ 까지의 bitwise XOR값을 계산해 놓았다. 그리고 bitwise XOR 연산의 성질 3가지를 알아두자.

1. $A\oplus 0=A$
2. $A\oplus A=0$
3. $A\oplus (B\oplus C)=(A\oplus B)\oplus C$

그렇다면 이 값을 왜 계산해 뒀을까? 문제 풀이에 반드시 필요한 값이기 때문이다. 출력값이 a, b이고 $0$ 부터 $a-1$ 까지 XOR한 값을 $k$ 라고 하자. 이때 나올 수 있는 경우가 총 3가지 있다.

1. $b=k:$ 모든 경우를 그냥 만족하기 때문에 배열에 추가로 원소를 삽입할 필요가 없다. 이 때 배열의 길이는 $a$
2. $b\ne k$인 경우, 두가지 경우가 추가로 존재한다.
   • $b\oplus k\ne a:$인 경우 $b\oplus k$ 값이 $a$가 아니므로 배열에 $b\oplus k$ 를 추가하면 된다. 그러면 $k\oplus (k\oplus b)=b$ 이므로 문제 조건을 만족한다. 이때 배열의 길이는 $a+1$ 이다.
   • $b\oplus k=a:$인 경우 $b\oplus k$ 값이 $a$이므로 배열에 $b\oplus k$ 를 추가 할 수 없다. 추가하면 MEX값이 $a$가 아니게 되기 때문이다. 그래서 우회하는 방법을 써야하는데, 이것 또한 bitwise XOR연산의 성질을 사용한다. 임의의 매우 큰 수를 $d$라고 하자. $k\oplus (k\oplus b\oplus d)\oplus d=b$ 이므로 배열에 $k\oplus b\oplus d$ 와 $d$ 을 추가하면 되므로 이때 배열의 길이는 $a+2$ 이다.

정답 코드

#include <cstdio>

int dp[300001];

int main(){
    for(int i = 1; i <= 300000; i++) dp[i] = (dp[i - 1] ^ i);
    int t; scanf("%d", &t);
    while(t--){
        int a, b; scanf("%d %d", &a, &b);
        int k = dp[a - 1];
        if(k == b) printf("%d\n", a);
        else{
            if((k ^ b) != a) printf("%d\n", a + 1);
            else printf("%d\n", a + 2);
        }
    }
}