BOJ 13505 두 수 XOR

집합 $S$가 주어졌을 때, 두 수 $x_1, x_2$ 를 골라서 $x_1 \bigoplus x_2$ 를 최대화하는 문제.

Description이 심플한데, 생각보다 알아야 할게 좀 있다.

 

우선 관찰해야 할 것은, 앞에서 $\bigoplus$ 값이 1인 비트가 있다면 무조건 먼저 골라야 한다는 점이다. 이진수 10000000 이 01111111보다 크기 때문에 무조건 앞 비트부터 먹을 수 있는 최대를 먹는 식으로 내려가야 결과값을 최대화할 수 있다.

 

Trie 자료 구조를 이용해서 0 또는 1의 Bit-string으로 집합 $S$를 압축하자. 이제, $S$의 각 원소에 대해 밑으로 내려가면서 최대한 지금 보는 원소와 다른 길을 따라가는 식으로 가기로 하자. 만약 지금 보는 원소와 $k$번째 비트에서 다른 길 (trie에 이미 들어 있는 다른 String) 이 없다면 어쩔 수 없이 같은 쪽을 따라가야 한다.

 

이렇게 하면, 처음 모든 원소를 Trie에 삽입할 때 드는 시간이 각 숫자의 길이를 $m$이라 했을 때 $\sum m$ 이므로 대략 $10N$ 정도, 각 원소를 다시 보면서 탐색하는 시간도 $m$씩 드는데 $m$개 있으므로 $O(nm)$ 시간에 풀 수 있고, $n = 1e5, m = 10$ 정도이므로 넉넉하다.

 

Trie 구현을 2차원 배열에 밀어넣어서 하는거에 익숙하지 않아서 엄청 헷갈렸었다 :(

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

int pt = 2;
int trie[2][3200000];
string int_to_binstr(int x)
{
    string res = "";
    for (int i = 30; i>=0; i--)
        res.push_back(((1<<i)&x)?'1':'0');
    return res;
}

void insert_trie(int x)
{
    string str = int_to_binstr(x);
    int curpt = 1;
    for (auto it:str)
    {
        int u = trie[it-'0'][curpt];
        if (u==0) 
        {
            trie[it-'0'][curpt] = pt;
            curpt = pt; 
            pt++;
        }
        else 
            curpt = u;
    }
    return;
}

int find_best(int x)
{
    int curpt = 1;
    int ans = 0;
    for (int i = 30; i>=0; i--)
    {
        int u = (x & (1<<i))?1:0;
        if (trie[1-u][curpt])
        {
            ans += (1<<i);
            curpt = trie[1-u][curpt];
        }
        else if (trie[u][curpt])
            curpt = trie[u][curpt];
        else break;
    }
    return ans;
}
int arr[101010];
int res = 0;
int main()
{
    int n; 
    scanf("%d",&n);
    for (int i = 0; i<n; i++)
    {
        int x;
        scanf("%d",&x);
        arr[i] = x;
        insert_trie(x);
    }
    for (int i = 0; i<n; i++)
        res = max(find_best(arr[i]),res);
    printf("%d\n",res);
}