XOR 문제. bit단위로 max(a_i xor X)를 최소로 하는 값 구하기

Codeforces Round #613 Div2. D - Dr. Evil Underscores

Problem - D - Codeforces

Q. XOR 문제. bit단위로 max(a_i xor X)를 최소로 하는 값 구하기

---

콘테중 못푸는 문제가 있는데,

그 중 어떤 문제는 답을 봐도 내가 나중에 절대 풀 수 있을 것 같지 않은 문제가 있다.

이 문제가 그런 문제중 하나..

 

[0, 2^30-1] 범위의 정수를 N개(최대 10만) 받고,

max(a_i xor X)을 구하는데, 이 값이 최소가 되도록 X라는 정수값을 골라보자.

문제는 X를 구하는게 아니라 max(a_i xor X)의 가능한 최소값을 구하는 것이다.

 

푸는 방법.

최상위 비트부터 X값을 만들어본다고 생각하자.

a배열의 최상위 비트(ex. 30번째 bit)는 0 or 1 모두 존재한다고 하면,

가능한 최소값을 구하는 X의 최상위 비트는 0 or 1을 모두 선택할 수 있다.

어떤 값을 선택하든 우리가 구하고자 하는 가능한 최소값의 최상위 비트는 1이 될 것이기 때문이다.

하지만 X의 최상위 비트는 0이나 1중에 아무거나 선택할 수 없다.

왜냐하면 X의 최상위 비트로 0을 선택하게 된 경우,

a_i의 최상위 비트가 0인 경우는 그 아래의 하위비트가 뭐든지 간에 max(a_i xor X)값이 될 수 없다.

(즉, max값이 될 수 없다.)

당연한 얘기지만, a_i xor X의 최상위 비트가 1이 만들어질 수 있는 환경에서 0이 되었다는 것은 절대 max값이 아니란 얘기기 때문이다.

 

그럼 a_i의 최상위 비트가 0만 있는 경우는 어떨까?

X의 최상위 비트는 0이 될 수 밖에 없다.

a_i xor X 연산중 최상위 비트끼리의 연산은 0이 되는것이 max(a_i xor X)의 가능한 최소값을 구하는 일이기 때문이다.

 

a_i의 최상위 비트가 1만 있는 경우는 위와 반대로 X의 최상위 비트가 1이 될 수 밖에 없다.

 

그럼 그 다음 하위 bit(최상위 비트의 바로 다음 bit)를 고려해보자.

max(a_i xor x)의 가능한 최소값을 구하는 것이 목적이므로

가장 최하위 비트부터 어떻게 구해왔든간에 max(a_i xor X)중 최소값을 답으로 가지고 있다면,

현재 최상위 비트의 상태에 따라 답을 갱신해주기만 하면 된다.

 

이는 현재 보고 있는 bit가 0이나 1인 a_i가 있을 땐 가능한 최소값이 min(solve(left, bit-1), solve(right, bit-1)) | (1<<bit) 꼴이 될 것이고,

현재 보고 있는 bit가 모두 0이거나 모두  1로 구성되어 있을 땐 가능한 최소값이 solve(right, bit-1) or solve(left, big-1)이 될 것이다.

 

이를 코드로 구현하면 아래와 같다.

 

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> a;
int f(vector<int> &v, int bit) {
    if(v.empty() || bit<0) return 0LL;
 
    vector<int> l,r;
    for(int &x: v) {
        if((x>>bit)&1) r.push_back(x);
        else l.push_back(x);
    }
 
    if(l.empty() || r.empty()) return f(l.empty()?r:l, bit-1);
    else return min(f(l,bit-1), f(r,bit-1)) | (1<<bit);
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    a.clear(); a.resize(n,0);
    for(int i=0; i<n; i++) cin >> a[i];
 
    printf("%d", f(a,30));
    return 0;
}