BOJ 21768 - AND PLUS OR (Python3)

굉장히 오랜만에 블로그에 글을 쓰는 느낌이다. 대학원생이 된 이후로 바빠서 문제를 풀더라도 블로그에 글을 쓸 시간이 안 났다. 짬이 생긴 터라 오늘 푼 문제의 풀이를 작성한다.

이 문제를 품으로서 수학 태그레이팅이 2600에 도달했다. 2700까지 올리고는 싶으나 아직 내가 그럴 만한 체급이 안 되는 것 같기도 하다. 천천히 올리자. 급하게 하지 말고.

---

문제

두 음이 아닌 정수 \(a,b\)에 대하여 \(a\wedge b, a\vee b\)는 각각 이들의 bitwise AND, bitwise OR를 나타낸다.

음이 아닌 정수로 구성된 길이 \(2^N\)의 정수열 \(A_0,A_1,\cdots,A_{2^N-1}\)에 대해 \(A_i+A_j<A_{i\wedge j}+A_{i\vee j}\)를 만족하는 \(0\le i,j< 2^N\)이 존재하는지 판별하고, 만약 존재한다면 \(i,j\)를 아무거나 하나 출력하라.

 

입력

첫째 줄에 음이 아닌 정수 \(N\)이 주어진다. \((0\le N\le 20)\)

둘째 줄에 정수열의 원소를 나타내는 \(2^N\)개의 음이 아닌 정수가 공백으로 구분되어 주어진다. 순서대로 \(A_0, A_1,\cdots,A_{2^N-1}\)을 의미한다. \((0\le A_i\le 10^7)\)

 

예제 입력)

# 예제 1
2
0 1 1 2

# 예제 2
2
0 1 1 3

 

출력

만약 문제의 조건을 만족하는 \(i,j\)가 있으면 이를 공백으로 구분하여 출력한다. 그렇지 않다면 대신 \(-1\)을 출력한다.

 

예제 출력)

# 예제 1
-1

# 예제 2
1 2

 

---

내 코드

N,*a = map(int,open(0).read().split())
for mask in range(1<<N):
    for i in range(N-1):
        for j in range(i+1,N):
            if 0 == mask & (1<<i):
                if 0 == mask & (1<<j):
                    I,J = mask+(1<<i),mask+(1<<j)
                    iorj = I+J-mask
                    if a[I]+a[J] < a[mask]+a[iorj]:
                        print(I,J); exit(0)
print(-1)

 

매우 풀이가 아름다운데, 그에 비해 구현량은 무시할 수 있을 정도로 짧다. 누군가는 마음에 안 들어하는 유형의 문제겠지만 나는 매우 좋다. 이런 문제가 더 많아졌으면 좋겠다.

\(i,j\)를 \(i=x\vee y, j=x\vee z\)로 둔다. 여기서 \(x,y,z\)는 그 어느 두 개를 뽑아도 bitwise AND값이 0인 세 정수이다. 그러면 \(A_i-A_{i\wedge j}<A_{i\vee j}-A_j\)는 \(A_{x\vee y}-A_{x}<A_{x\vee y \vee z}-A_{x\vee z}\)와 같은 말이다.

\(y\)를 고정하자. 함수 \(f_y(x)=A_{x\vee y}-A_{x}\)를 생각하면 위 등식은 \(f_y(x)<f_y(x\vee z)\)임과 같은 소리이다. \(z=\sum_1^k 2^{a_i}\)이면, \(f_y(x\vee z)-f_y(x)=\sum_{i=1}^k(f_y(x\vee\sum_{j=1}^{i}2^{a_j})-f_y(x\vee\sum_{j=1}^{i-1}2^{a_j}))>0\)이므로 적어도 하나의 \(f_y(x\vee\sum_{j=1}^i2^{a_j})-f_y(x\vee\sum_{j=1}^{i-1}2^{a_j})\)는 0보다 크다. 따라서 문제의 조건을 만족시키는 \((x,y,z)\)가 주어진다면, \(z=2^i\) 꼴의 해도 하나 존재한다.

이 \(z=2^i\)꼴의 해를 고정해놓고 똑같이 위 풀이를 반복하면, \(y=2^i,z=2^j\) 꼴의 해가 존재함 역시 보일 수 있다. 이러면 \(2^N\)개의 모든 \(x\)에 대하여, 각각 최대 \(N\)개의 \(y,z\)가 존재하므로 완전탐색을 할 수 있다. 시간복잡도는 \(\mathcal O(N^22^N)\)이고, \(N=20\)이므로 여유롭게 통과한다.

 

이로서 21768번의 풀이를 마친다.