2024 CCPC Online Contest: 최댓값의 최소화 문제

2024 CCPC 인터넷 예선 J번 문제는 두 시퀀스의 XOR 합을 조정하여 그 중 최댓값을 최소화하는 문제입니다. 길이 $n$인 두 수열 $a, b$가 주어지며, 동일한 인덱스 $i$에 대해 $a_i$와 $b_i$를 교환하는 연산을 원하는 만큼 수행할 수 있습니다. 이때 $f(a) = \bigoplus_{i=1}^n a_i$와 $f(b) = \bigoplus_{i=1}^n b_i$를 정의할 때, $\max(f(a), f(b))$의 최소값을 구하는 것이 목표입니다.

문제 접근법

가장 중요한 관찰은 특정 인덱스 $i$의 요소를 교환할 때 발생하는 변화입니다. 초기 XOR 합을 $S_A, S_B$라고 합시다. $a_i$와 $b_i$를 교환하면 새로운 XOR 합은 다음과 같습니다.

• 새로운 $f(a) = S_A \oplus a_i \oplus b_i$
• 새로운 $f(b) = S_B \oplus a_i \oplus b_i$

여기서 $c_i = a_i \oplus b_i$라고 정의하면, 우리가 할 수 있는 일은 $c$ 수열의 부분 집합을 선택하여 그 XOR 합 $X$를 구한 뒤, $S_A \oplus X$와 $S_B \oplus X$ 중 큰 값을 최소화하는 것입니다. 이는 선형 기저(Linear Basis)를 사용하여 해결할 수 있는 전형적인 XOR 공간 문제입니다.

그리디 전략

가장 높은 비트부터 탐색하며 그리디하게 결정합니다. $S_A$와 $S_B$의 현재 비트가 같다면, 선형 기저를 통해 해당 비트를 반전시켜도 $S_A, S_B$의 대소 관계에는 영향을 주지 않으므로 양쪽 모두 작아지는 방향을 선택합니다. 만약 어느 시점에서 $S_A$와 $S_B$의 비트가 달라지면(예: $S_A=1, S_B=0$), 그 이후부터는 현재까지 더 작았던 쪽을 키우고 더 컸던 쪽을 줄이는 방향으로 보상적인 선택을 이어갑니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

struct XORBasis {
    ll basis[32];
    XORBasis() { fill(basis, basis + 32, 0); }

    void insert(ll x) {
        for (int i = 31; i >= 0; i--) {
            if (!(x & (1LL << i))) continue;
            if (!basis[i]) {
                basis[i] = x;
                return;
            }
            x ^= basis[i];
        }
    }

    void build() {
        for (int i = 31; i >= 0; i--) {
            for (int j = i - 1; j >= 0; j--) {
                if (basis[i] & (1LL << j)) basis[i] ^= basis[j];
            }
        }
    }
};

void run_test_case() {
    int n;
    cin > n;
    vector<ll> v1(n), v2(n);
    ll sumA = 0, sumB = 0;
    for (int i = 0; i < n; i++) { cin >> v1[i]; sumA ^= v1[i]; }
    for (int i = 0; i < n; i++) { cin >> v2[i]; sumB ^= v2[i]; }

    XORBasis lb;
    for (int i = 0; i < n; i++) lb.insert(v1[i] ^ v2[i]);
    lb.build();

    if (sumA < sumB) swap(sumA, sumB);

    ll targetX = 0;
    bool gapFound = false;

    for (int i = 31; i >= 0; i--) {
        bool bitA = (sumA >> i) & 1;
        bool bitB = (sumB >> i) & 1;

        if (!gapFound) {
            if (bitA != bitB) {
                gapFound = true;
                // A가 크므로 A를 줄일 수 있다면 줄임
                if (lb.basis[i]) targetX ^= lb.basis[i];
            } else if (bitA && bitB) {
                // 둘 다 1이면 둘 다 0으로 만들 수 있는지 확인
                if (lb.basis[i]) targetX ^= lb.basis[i];
            }
        } else {
            // 이미 차이가 발생한 후에는 현재 큰 쪽을 줄이는 방향으로
            ll currentA = sumA ^ targetX;
            ll currentB = sumB ^ targetX;
            if (currentA > currentB) {
                if ((currentA ^ lb.basis[i]) < currentA) targetX ^= lb.basis[i];
            } else {
                if ((currentB ^ lb.basis[i]) < currentB) targetX ^= lb.basis[i];
            }
        }
    }

    cout << max(sumA ^ targetX, sumB ^ targetX) << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) run_test_case();
    return 0;
}

2024 교내 팀 대회: 게임 이론과 XOR 합

이 문제는 두 명의 플레이어 Taibo와 xxcdsg가 시퀀스에서 비어있지 않은 부분 수열을 번갈아 선택하여 제거하는 게임입니다. 최종 점수는 각 단계에서 선택된 부분 수열들의 XOR 합의 총합입니다. Taibo는 이 점수를 최대화하려 하고, xxcdsg는 최소화하려 합니다.

핵심 원리

XOR 연산은 비올림 덧셈이므로, 임의의 두 수 $a, b$에 대해 $a \oplus b \leq a + b$가 성립합니다. Taibo가 첫 번째로 어떤 부분 수열을 선택하여 XOR 합 $X$를 만들더라도, xxcdsg는 남은 모든 수를 한꺼번에 선택하여 XOR 합을 최소화(XOR 성질에 의해 남은 것들의 XOR 합은 전체 XOR 합 $S \oplus X$가 됨)하려 할 것입니다. 하지만 여기서 xxcdsg의 최적 전략은 결국 전체 게임의 형태를 $X + (S \oplus X)$의 구조로 만듭니다. Taibo는 이 값을 최대화하는 $X$를 선택해야 합니다.

선형 기저와 탐색

값의 범위가 $2^{20}$ 미만이므로 선형 기저의 크기는 최대 20입니다. 20개의 기저 원소로 만들 수 있는 모든 XOR 합의 가짓수는 $2^{20} \approx 10^6$으로, 완전 탐색(DFS)이 가능한 수준입니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

ll total_xor = 0;
ll max_score = 0;
vector<ll> active_basis;

void find_max(int idx, ll current_xor) {
    if (idx == active_basis.size()) {
        max_score = max(max_score, current_xor + (total_xor ^ current_xor));
        return;
    }
    // 현재 기저 포함하지 않음
    find_max(idx + 1, current_xor);
    // 현재 기저 포함함
    find_max(idx + 1, current_xor ^ active_basis[idx]);
}

int main() {
    int n;
    if (!(cin >> n)) return 0;

    ll basis[21] = {0};
    for (int i = 0; i < n; i++) {
        ll val;
        cin >> val;
        total_xor ^= val;
        for (int j = 20; j >= 0; j--) {
            if (!(val & (1LL << j))) continue;
            if (!basis[j]) {
                basis[j] = val;
                break;
            }
            val ^= basis[j];
        }
    }

    for (int i = 0; i <= 20; i++) {
        if (basis[i]) active_basis.push_back(basis[i]);
    }

    find_max(0, 0);
    cout << max_score << endl;

    return 0;
}