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

falconlee236

·

2021. 12. 19. 15:39

반응형

문제 설명

두 정수 nm이 주어진다. 수열 n0,n1,...,nmMEX값을 구하시오.

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

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

각 테스트 케이스의 첫번째 줄에는 두 정수 n,m(0n,m109) 이 주어진다.

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를 구하는 방법을 알려주는 것과 같은 의도를 가지고 출제했다는 것이었다. 두 정수 nm이 주어졌을 때, MEX값을 어떻게 구할까?

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

  1. N0=N
  2. NN=0
  3. AB=C 이면 AC=B 이다.

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

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

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

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