MEX with XOR

1. 원소 하나를 지웠을 때의 mex

배열 $A$ 전체의 mex를 $m$이라고 하자. $0,1,\cdots,m-1$은 모두 등장하고, $m$은 등장하지 않는다.

$A_i$ 하나를 지우면 다음 두 경우로 나뉜다.

• $A_i<m$이고 $A_i$가 정확히 한 번 등장했다면 $M_i=A_i$이다.

따라서 $B_i=0$인 위치는 정확히 $m$보다 작은 값이 한 번만 등장하는 위치이다. $B_i\ne0$인 위치에서는 반드시

$$A_i=B_i\oplus m$$

이어야 한다. 여기서 $\oplus$는 비트 XOR이다.

$B$에서 $0$의 개수를 $Z$라고 하자. 같은 양의 정수 $v$가 $B$에 등장하는 횟수를 $f(v)$라고 하자. 을 정하면 인 위치의 값은 모두 결정된다.

이 값들 중 $m$보다 작은 값이 정확히 한 번 등장하면 모순이다. 그런 값은 $B_i=0$을 만들어야 하기 때문이다. 반면 두 번 이상 등장하는 값에는 문제가 없다. 아직 등장하지 않은 $0$ 이상 $m$ 미만의 값들은 $B_{}$인 위치에 하나씩 배치하면 된다.

따라서 $m$이 가능할 필요충분조건은 다음과 같다.

• $v\oplus m<m$인 모든 양의 정수 $v$에 대해 $f(v)\ne1$이다.

$m$은 배열의 mex이므로 $0\le m\le N$이다.

2. 작은 입력: mex 후보를 모두 확인하기

$m=0,1,\cdots,N$을 모두 시도한다. 각 후보에 대해 $B_i\ne0$인 위치를 으로 채우고, 미만에서 빠진 값들을 인 위치에 하나씩 넣는다. 빠진 값의 수가 와 다르면 해당 후보는 불가능하다.

이후 각 위치를 직접 제외하여 mex를 다시 계산하면 후보 하나를 $O(N^2)$에 확인할 수 있다. 전체 시간 복잡도는 $O(N^3)$이며 서브태스크 3을 해결한다.

앞 절의 필요충분조건을 이용하면 더 빠르게 확인할 수 있다. 후보 하나마다 $m$ 미만의 값들의 등장 횟수를 세고, 한 번 등장하는 값이 없는지와 빠진 값의 수가 $Z$인지 확인한다. 후보당 $O(N)$, 전체 $O(N^2)$이므로 서브태스크 4를 해결한다.

3. XOR 비교를 최상위 비트로 바꾸기

양의 정수 $v$의 가장 높은 $1$ 비트 위치를 $h$라고 하자. $v\oplus m$과 $m$은 $h$보다 높은 모든 비트가 같고, 번째 비트가 다르다. 따라서

$$v\oplus m<m \quad\Longleftrightarrow\quad m\text{의 }h\text{번째 비트가 }1$$

이다.

양의 $B_i$들을 최상위 비트 위치별로 묶는다. 각 비트 $h$에 대해 다음 정보를 계산한다.

• $C_h$: 최상위 비트가 $h$인 서로 다른 양의 $B_i$의 개수.
• 해당 묶음에 정확히 한 번 등장하는 값이 있는지 여부.

정확히 한 번 등장하는 값이 있는 비트는 $m$에서 선택할 수 없다. 그 비트를 선택하면 그 값이 $m$ 미만의 유일한 원소가 되기 때문이다.

이러한 금지 비트를 제외하고, $m$의 $h$번째 비트가 $1$인지 나타내는 값을 $s_h$라고 하자. $m$ 미만에서 이미 등장한 서로 다른 값의 수는 $$이다. 그러므로

$$Z=m-\sum_h C_hs_h=\sum_h(2^h-C_h)s_h.$$

즉, 허용된 비트마다 가중치

$$W_h=2^h-C_h$$

를 하나씩 두고, 일부 비트를 선택하여 가중치 합을 $Z$로 만들면 된다.

최상위 비트가 $h$인 양의 정수는 정확히 $2^h$개이므로 $C_h\le2^h$이며, 모든 가중치는 음이 아니다.

4. 부분합 DP와 배열 복원

$dp[s]$를 지금까지 처리한 비트 중 일부를 선택하여 합 $s$를 만들 수 있는지로 정의한다. 처음에는 $dp[0]$만 참이다.

각 허용 비트의 양의 가중치 $W_h$에 대해, $s=Z,Z-1,\cdots,W_h$ 순서로

$$dp[s]\leftarrow dp[s]\lor dp[s-W_h]$$

를 적용한다. 내림차순으로 갱신하므로 같은 비트를 두 번 선택하지 않는다. 처음 도달한 상태마다 이전 합과 사용한 비트를 저장하면 실제 선택도 복원할 수 있다.

가중치가 $0$인 비트는 선택하지 않아도 합에 영향이 없으므로 건너뛴다. $Z$보다 큰 가중치도 사용할 수 없다.

$dp[Z]$가 거짓이면 -1을 출력한다. 참이면 선택한 비트들로 $m$을 복원하고 다음과 같이 $A$를 만든다.

• $B_i\ne0$이면 $A_i=B_i\oplus m$으로 정한다.

5. 정확성 증명

어떤 정답 배열의 mex가 $m$이라면, 첫 절의 관찰에 의해 금지 비트를 선택할 수 없고 가중치 합이 반드시 $Z$이다. 따라서 정답이 존재하면 DP도 합 $Z$에 도달한다. 가중치가 $0$인 비트를 버려도 합은 바뀌지 않으므로 이를 건너뛰는 것은 안전하다.

반대로 DP가 선택한 비트들로 만든 $m$을 생각하자. 선택된 묶음의 서로 다른 값들은 각각 두 번 이상 등장한다. 그 개수를 $D$라고 하면

$$m=Z+D\le Z+\frac{N-Z}{2}\le N.$$

따라서 복원한 $m$도 유효한 mex 후보 범위에 있다.

$B_i\ne0$인 위치에서는 $A_i=m$이 될 수 없다. 이면 이 되어야 하기 때문이다. 이 위치들이 채우는 미만의 서로 다른 값은 정확히 개이며, 모두 두 번 이상 등장한다. 남은 개의 값은 인 위치에 하나씩 배치한다.

따라서 완성된 배열은 $0$부터 $m-1$까지를 모두 포함하고 $m$을 포함하지 않아 mex가 $m$이다. $B_i=0$인 위치의 값은 미만에서 유일하므로 제거 후 mex가 자기 자신이다. 인 위치를 제거하면 mex는 으로 유지된다. 두 경우 모두 요구한 XOR 관계를 만족한다.

또한 $m\le N<2^{30}$이고 $B_i<2^{30}$이므로 이다. 빠진 값들도 보다 작으므로 모든 출력값이 허용 범위를 만족한다.

6. 특수 조건 서브태스크

서브태스크 1에서는 모든 $B_i>0$이다. $A=B$로 두면 $0$이 없으므로 어떤 원소를 지워도 mex는 $0$이다. 따라서 그대로 출력하면 된다. 시간 복잡도는 이다.

서브태스크 2에서는 $B_i\in\{0,1\}$이다. 모두 $0$이면 $A$를 $0,1,\cdots ,N-1$의 순열로 만들면 된다. 이 하나 이상 있다면 정답이 존재할 필요충분조건은 가 짝수인 것이다.

이를 보이기 위해 $B_i=1$인 위치의 값 $m\oplus1$을 생각하자. $m$이 짝수이면 이 값은 $m+1$이므로 미만의 모든 값은 인 위치가 채워야 하고 이다. 이 홀수이면 이 값은 이다. 이 경우 이 정확히 한 번 등장하면 모순이고, 두 번 이상 등장하면 이다. 두 경우 모두 가 짝수이다.

$Z$가 짝수이면 $m=Z$로 두고, $B_i=0$인 위치에 $0,1,\cdots ,Z$을 하나씩, 인 위치에 을 넣으면 된다. 시간 복잡도는 이다.

7. 복잡도

양의 $B_i$를 정렬하여 값별 등장 횟수와 비트별 정보를 구하면 $O(N\log N)$ 시간이 필요하다. 비트는 $0$부터 $29$까지 있으므로 DP에는 , 배열 복원에는 시간이 필요하다.

전체 시간 복잡도는 $O(N\log N+30Z)$, 공간 복잡도는 $O(N)$이다. 모든 테스트케이스의 $N$ 합이 $200\,000$ 이하이므로 전체 제한을 만족한다.

Solution written by GPT