Codeforces Round #735 (Div. 2)-C. Mikasa

문제 설명

두 정수 $n$과 $m$이 주어진다. 수열 $n \oplus 0, n \oplus 1, ..., n \oplus m$의 $MEX$값을 구하시오.

음이 아닌 정수를 원소로 가진 수열의 $MEX$는 이 수열에 나타나지 않은 음이 아닌 정수중 가장 작은 값을 말한다. 예를 들어서 $MEX(0, 1, 2, 4) = 3$ 이다. 그리고 $MEX(1, 2021) = 0$ 이다.

Input
첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 30000)$ 이 주어진다.

각 테스트 케이스의 첫번째 줄에는 두 정수 $n, m (0 \le n, m \le 10^9)$ 이 주어진다.

Output
각 테스트케이스마다 문제의 답을 출력한다.

Example
input
5
3 5
4 6
3 2
69 696
123456 654321

output
4
3
0
640
530866

문제 접근

사용한 알고리즘: 비트마스크, 그리디 알고리즘, 수학
걸린 시간 : 00:11
이전 virtual contest에서 알았던 개념인 MEX를 그리디 알고리즘과 응용해서 나온 문제이다. 이 문제가 좋았던 점은 실제 MEX를 구하는 방법을 알려주는 것과 같은 의도를 가지고 출제했다는 것이었다. 두 정수 $n$과 $m$이 주어졌을 때, MEX값을 어떻게 구할까?

여기서 $XOR$의 성질을 이전과 추가해서 하나 더 알아야 한다. 1과 2는 이전에 알았던 것이지만 3은 이번 문제에서 추가된 것이다. 한번 자세히 알아보자. 왜냐하면 codeforce에서 bit 연산을 이용하는 문제가 많이 출제되기 때문이다.

1. $N \oplus 0 = N$
2. $N \oplus N = 0$
3. $A \oplus B = C$ 이면 $A \oplus C = B$ 이다.

3번 성질을 이 문제에서 사용할 것이다. 그렇다고 해서 1번과 2번을 이해하지 못하면 안된다. 왜냐하면 1번과 2번 성질을 이용해서 나온 성질이 3번이기 때문이다.

$0 \le x \le m$ 를 만족하는 $x$가 있다고 하자. 그렇다면 $n$과 $m$을 이용해서 만든 수열은 $n \oplus x$ 의 연산결과가 있을 것이고 그 값을 $k$라고 하자. 그렇다면 $n \oplus x = k$ 이 수식을 $XOR$의 성질 3번을 이용해서 바꿔보자. $n \oplus k = x$라는 식이 나온다. 그러면 $0 \le x \le m$ 이기 때문에, 이 식은 이 부등식을 만족한다. $0 \le n \oplus k \le m$. 그렇다면 우리가 구해야 하는 수는 수열에 나타나지 않는 수이기 때문에 $n \oplus k \ge m + 1$ 이라는 식을 만족해야 하고, 나올 수 있는 최소 값을 구해야 하기 때문에 위 식을 만족하는 최소 $k$를 구하는 문제로 간단하게 바뀌게 된다.

그렇다면 이 $k$는 어떻게 구할 수 있을까? 바로 여기서 그리디 알고리즘의 원리가 나온다. 우리가 구해야 하는 것은 최소 $k$값이기 때문이다. MSB부터 시작해서 LSB까지 경우를 다 탐색할 것이다. 즉 한 비트끼리 비교할 생각인데, 비트는 $0$ 과 $1$ 두가지 경우가 존재하기 때문에 우리가 생각해봐야할 경우는 $2^2 = 4$ 가지이다. 여기서 $m + 1$을 $p$라고 가정하자.

1. $n$의 한 비트가 0이고, $p$의 한 비트가 0일때, 이 경우는 두 비트가 같아야 0이 나오기 때문에 무조건 k의 값이 0이 될수밖에 없다.
2. $n$의 한 비트가 1이고, $p$의 한 비트가 1일때, 이 경우는 두 비트가 달라야 1이 나오기 때문에 무조건 k의 값이 0이 될수밖에 없다.
3. $n$의 한 비트가 1이고, $p$의 한 비트가 0일때, 이 경우는 일단 두 비트가 같아야 0이 나오는데, 우리는 $n \oplus k$ 값을 $p$보다 크게 만들어야 하는게 목적이다. 그렇다면 이 대응되는 비트를 0으로 만든다면 $n \oplus k$의 값이 1이 나오게 되고, 이 값은 대응대는 비트가 0인 $p$ 보다 반드시 크다. 그리고 최소 $k$값을 만들어야 하기 때문에 뒤의 비트들을 모두 0으로 만들면 최소 $k$값을 만들 수 있다. 즉 이 경우에 바로 뒤를 0으로 만들고 break를 하면 된다.
4. $n$의 한 비트가 0이고, $p$의 한 비트가 1일때, 이경우는 일단 두 비트가 달라야 1이 나오는데, $k$가 0이면 $n \oplus k$가 $p$보다 반드시 작기 때문에 이 경우의 비트는 반드시 1이 되어야 한다.

정답 코드

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n, m; cin >> n >> m;
        int p = m + 1;
        int ans = 0;
        for(int i = 30; i >= 0; i--){
            bool a = n & (1 << i);
            bool b = p & (1 << i);
            if(!a && b) ans |= (1 << i);
            if(a && !b) break;
        }
        cout << ans << "\n";
    }
    return 0;
}