백준 10736 - XOR삼형제 2

https://www.acmicpc.net/problem/10736

수열의 최대 길이 찾기

XOR의 성질에 따라 $V \oplus V = 0$ 이므로 XOR 과정 중 중복되는 수를 만나서는 안된다.

 

다시 말해 어떤 세 원소를 선택하든 최소 한 개의 비트를 살릴 수만 있으면 된다는 것이다.

 

그렇다면 100 이하의 수로 구성할 수 있는 수열의 최대 길이는 어떻게 찾을 수 있을까?

 

32와 64를 이진수로 나타낸 표를 보면서 생각해보자.

 

X	1	0	0	0	0	0
1	0	0	0	0	0	0

 

이 표에 존재하는 0을 0 혹은 1로 채우는 경우의 수를 만든다고 했을 때 1이 절대로 들어가서는 안 되는 경우가 무엇일까?

 

X	1	0	0	0	0	0
1	NO	0	0	0	0	0

 

바로 64에서 $2^{5}$에 해당하는 비트이다. 만약 이를 허용하면 다음 세 자연수 $a \; (32 \leq a \lt 64), b \; (64 \leq b \lt 96), c \; (96 \leq c)$에서 비트를 적절히 선택해 XOR의 값을 0으로 만들 수 있게 된다.

 

저 자리에만 1을 넣지 않으면 나머지 자리는 괜찮다. 앞서 논한 제약조건을 지키며 reading one이 같은 수를 뽑는 경우는 $\binom{3}{2}$로 결정이 되는데 결국 선택한 수에서 반드시 하나는 reading one을 XOR 연산으로 잃지 않게 되어 언제든 0을 초과한 값을 얻을 수 있다.

 

따라서 이를 표로 정리하면

 

X	1	YES	YES	YES	YES	YES
1	NO	YES	YES	YES	YES	YES

 

경우의 수를 계산하면 $2^{5} + 2^{5} = 64$ 의 길이를 최대로 가질 수 있다는 결과를 얻을 수 있다.

굳이 64와 32로 결정해야 하나요?

다른 reading one으로 조합을 생각하면 이는 최적해를 가질 수 없음을 이해할 수 있다. reading one이 작을 수록 그만큼 가질 수 있는 비트 조합의 개수가 적어지기 때문이다.

모든 N의 범위에서 수열 길이 찾기

수열의 최대 길이를 찾았으니 이를 N 범위 전체에 적용해보자. 우리는 앞서 가장 큰 reading one과 두번째로 큰 reading one으로 수열을 구성하는 게 최적해임을 알았으니 주어진 N에 대해 N 이하인 가장 큰(그리고 두 번째로 큰) reading one을 가진 수를 찾으면 된다.

 

이때 reading one이 가장 큰 수에서 reading one의 위치를 x라고 했을 때 구간 $[2^{x - 1}, 2^{x} + (2^{x - 1} - 1)]$에 포함된 수들이 답이 된다. 이를 적절히 구현하면 정답을 받을 수 있게 된다.

 

전체 코드 - reading one을 찾는 부분은 파라메트릭 서치로 구현했다.

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int reading_bit[7] {1, 2, 4, 8, 16, 32, 64};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--)
    {
        int n;
        cin >> n;

        if (n == 1)
        {
            cout << "1\n1\n";
            continue;
        }

        if (n == 2)
        {
            cout << "2\n1 2\n";
            continue;
        }

        int l = 0, r = 6;
        int bit_reader;

        while (l <= r)
        {
            int m = (l + r) / 2;
            if (reading_bit[m] <= n)
            {
                bit_reader = m;
                l = m + 1;
            }
            else
            {
                r = m - 1;
            }
        }

        int dont_access = reading_bit[bit_reader] | reading_bit[bit_reader - 1];

        vector<int> res;
        for (int i = reading_bit[bit_reader - 1]; i < min(n + 1, dont_access); ++i)
            res.push_back(i);
        cout << res.size() << '\n';
        for (int &i: res)
            cout << i << ' ';
        cout << '\n';
    }
}