BOJ 30300 AND MEX

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

30300번: AND MEX

문제

We define the beauty of an array as the value of its minimum excluded value (MEX ). A larger MEX corresponds to a more beautiful array.

You are given an array A of length N. You want to enhance it in terms of its beauty. To achieve this, you can choose a non-negative integer x and replace each element A_i with A_i^x where ∧ denotes the bitwise AND operator.

Find the optimal value of x that maximizes the beauty of the array.

입력

The first line contains a single integer T --- the number of test cases.

The first line of each test case contains a single integer N.

The second line of each test case contains N space-separated integers A_1, ... ,A_N.

출력

For each test case, print a single line containing a single integer x that maximizes the MEX of the array formed by taking the bitwise AND of each element of A with x. If there are multiple solutions, you may print any.

제한

•  1≤T≤100000
•  1≤N≤100000
•  0≤A_i<2^30 
• It is guaranteed that the sum of N over all test cases does not exceed 100000$100\, 000$.
• All values in the input are integers.
•  0≤x<2^30
• It can be shown that there always exists an optimal x in the specified range.

풀이

요약하면, 배열에 x값을 AND 했을 때 MEX값이 최대가 되는 x를 찾는 문제이다.

 

MEX에 대해 잘 생각해보자. MEX값이 k이려면 k보다 작은 모든 자연수 k-1, k-2, ... , 1, 0이 모두 배열에 있어야 한다.

 

사실 생각해보면 0부터 차례대로 숫자를 채워 나가야 하는데, 배열 위의 각 수는 자신이 갖고 있던 비트만을 사용해야 하지 없던 비트를 만들어낼 수는 없다. 따라서 MEX가 1보다 크려면 최하위 비트가 0인 수와 1인 수가 모두 있어야 하고, MEX가 3보다 크려면 최하위 2비트가 00, 01, 10, 11인 수가 모두 있어야 하고, ... 과 같은 논리 전개가 가능하다. 대회 도중 이 시점에서 풀이를 작성해 AC를 받았다.

 

예를 들어 [1, 8]이 주어졌다고 하자. 이 자체로는 MEX가 0이지만 x=1을 AND해주면 8이 0의 자리를 채우면서 MEX값이 2가 된다. 즉, 상위 비트를 0으로 날리면서 0부터 순서대로 채우는 것으로 MEX를 크게 만드는 문제이다. 사실 0으로 날리지 않은 비트가 있다면 그 하위 모든 비트들은 0으로 만들어주면 안된다. AND로 0으로 만든 비트가 있다면 그 비트가 최상위비트가 되는 수가 배열에 존재하지 않게 되고, 그런 수 중 최소값이 MEX값의 상한이 된다. 따라서 AND를 통해 0으로 만든 비트가 있다면, 그 상위 비트에 관계 없이 MEX의 상한이 정해진다. 이때 최대한 많은 정수를 하위 비트들에 채워야 하므로 상위 비트를 0으로 만들어 AND를 통해 결정된 상한보다 작게 만들어 주는 것이 최적이다.

 

이를 통해 얻을 수 있는 로직은 아래와 같다.

1. 0부터 2^30보다 작은 모든 bit = (1<<i)-1 (0 ≤ i ≤ 30)를 순회한다.

2. bit를 각 배열 요소에 AND해주고 MEX를 구한다.

3. 이전까지 구한 MEX의 최대값보다 크다면 최대 MEX값을 갱신하고 bit값을 저장한다.

4. 순회가 끝난 뒤 최종 갱신된 bit값이 문제의 정답이다.