BOJ 21099 - Four XOR (P4)

사용 알고리즘

Pigeon Principle, Brute Force

 

풀이

A,B,C,D는 대충 배열에서 서로 다른 4개를 뽑은 값이라 하자.

A xor B xor C xor D = 0이므로

A xor B = C xor D를 얻는다.

즉 두 수를 xor한 값이 같은 순서쌍이 존재하는지 판별하는 문제와 동치이다.

그럼 이제 이걸 어떻게 푸느냐?

를 고민하면 굉장히 어렵다. 적어도 O(Nlog^2N) 정도에는 해야할 것 같은데 쉽지 않다. 아니 애초에 A xor B = k인 거 찾기도 O(NlogN) 정도는 걸린다.

그런데 사실 이건 함정이다. 고민하다 보면, 가능한 순서쌍 개수는 O(N^2)개인데 이게 다 다를 수 있는가? 에 대한 의문을 가지게 된다. 한번 생각해보자.

수 범위가 10^5 이하이므로 xor한 값은 범위가 2^17 미만이다. 그럼 순서쌍 개수가 2^17 이상이라면 비둘기집의 원리에 의하여 적어도 같은 순서쌍이 하나는 존재한다는 말이 된다. 그럼 순서쌍 개수가 2^17 미만인 n은 몇일까? 대충 어림잡아서 nC2 < 2^17이어야 하며 대충 그러한 n은 400~500 정도 된다는 사실을 알 수 있다. 결론은 뭐냐면 n>500이면 무조건 답이 Yes라는 것이다. 따라서 n<500만 어떻게 풀든 naive하게 풀면 끝.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll n;
multiset<ll> a, b;
int main(){
    fast;
    cin>>n;
    if(n>=500)return !(cout<<"Yes");
    vector<ll> v(n);
    for(auto &i : v)cin>>i;
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < i ; j++)b.insert(v[i]^v[j]);
    }
    for(int i = 0 ; i < n ; i++){
        for(int j = i+1 ; j < n ; j++)b.erase(b.find(v[i]^v[j]));
        for(int j = 0 ; j < i ; j++){
            if(b.find(v[i]^v[j]) != b.end())return !(cout<<"Yes");
        }
    }
    cout<<"No";
}

 

태그를 알고 나면 난이도가 급하락하는 것 같다. 풀이를 찾으니까 어이없긴 한데 그대로 자력솔에 의의를 두자.

 

20240816 추가) xor convolution? 머시기를 이용하면 그냥 정공법으로 풀 수 있는 것 같다. 수학을 못해서 잘 모르겠지만 나중에 알아봐야겠다.