Editorial

---

D

summary:

수가 n개 존재하는 a와 b 배열이 있는데, b에 있는 수들의 순서를 임의로 변경해서

$c_i = a_i \oplus b_i$ 라고 할 때,

$ c_1 \& c_2 \& ⋯ \& c_n$ 의 값을 가장 크게 만드는 문제이다.

solution:

현재까지 구한 답을 $ans$라고 하고, greedy하게 상위 비트부터 채워나간다.

현재 비트가 가능한 지 결정할 때, 상위 비트에서 결정된 부분들이 영향을 미치므로 $a$의 원소와, $b$의 반전시킨 원소 모두에 $ans$를 \& 한 뒤 개수를 체크한다.

만약 그 값들이 모두 같다면,

어떤 비트의 값이 0이었을 경우에는 고려할 필요가 없고(어차피 0과 &하게 되므로),

1이었을 경우에는 현재 구하려는 값 $ans$에서 모든 1인 비트에 대해, 그 비트에서 $a_i$가 1이었으면 $b_i$의 0인 것들과, $a_i$가 0이었으면 $b_i$의 1인 것들이랑 짝지어졌다는 뜻이다.

즉 $ \oplus $를 하면 확인하고자 하는 모든 비트들(ans에서 1인 비트들)이 1이 된다는 뜻이고, $ans$는 valid하다는 뜻이다. 따라서 현재 비트를 ans에 추가하고(더하거나 $|$),

아니라면 현재 비트는 invalid하므로 ans에 추가하지 않는다.

opinion:

문제 풀때 거의 근접했으나, b의 모든 원소들의 반전시킨 버전과 현재 구한 답을 $\&$을 해서 현재 구한 값에서의 모든 비트들을 한번에 valid한지 체크하는 방법(자동으로 분류하는 방법)을 생각해내지 못했다. 따라서 수많은 vector로 일일이 분류하여 현재 비트가 되는지를 확인할 수밖에 없었고, 틀리게 되었다.