BOI 2016 Swap

BOI 2016 Swap

순열 $x_1, \cdots, x_n$ 이 주어질 때, $i = 2, \cdots, n$ 에 대해 (순서대로) $x _ {[i/2]}$와 $x _ i$ 를 스왑할 수 있는 기회가 한 번씩 주어진다. 이를 적절히 사용하여 만들 수 있는 사전 순 최소 순열을 구하여라.

풀이

$x_i$의 후보는 $x_i, x_{2i}, x_{2i+1}$ 셋 뿐이고, 사전 순 최소를 생각하면 이 중 최소인 값이 $i$번 자리에 들어가는 것이 당연하다.

• (자명한 경우) $i$번 자리에 $x_i$ 또는 $x_{2i}$가 들어가는 경우, $(2i, 2i+1)$번 자리가 각각 $(x_{2i}, x_{2i+1}), (x_{i}, x_{2i+1})$로 강제된다.
• (비자명한 경우) 하지만 $x_{2i+1}$이 들어가는 경우 $(x_{i}, x_{2i})$, $(x_{2i}, x_{i})$가 모두 가능하다. $2i$번 자리가 더 앞쪽이니 이 곳에 작은 수를 배정하는 그리디한 전략이 이득이 아닐까?

아쉽게도 예제 1에서 사실이 아님을 알 수 있다. $x_{2i}, x_{i}$ 둘 중 무엇도 $2i$ 번 자리에 고정될 수 없는 경우 (즉, $\min(x_{4i}, x_{4i+1}) < \min(x_{2i}, x_{i})$인 경우) 어차피 둘 모두 $2i$번 자리에 기여할 수 없으니, $2i+1$번 자리에 둘 중 작은 수를 보내는 것이 이득이 될 수 있다.

어떻게 보면 직관적인 결론인데, 나는 직관적인 방법으로 증명하기는 힘들어서 다음과 같은 방법을 썼다.

$i$의 서브트리에 속한 모든 정점 $j$에 대해, $\sum_{j} x_{j} W^{-j}$ 같은 값을 생각할 수 있다. $W$를 매우 큰 수로 잡으면 이 값이 작은 것과 사전순으로 작은 것이 동치가 된다.

$F(i, a)$를 $i$번 자리에 $a$가 들어왔을 때 위 합의 가능한 최솟값이라고 하자. "비자명한 경우"란 여기서 $x_{2i+1} < x_{2i}, a$ 여서 $i$번 자리에 $x_{2i+1}$이 들어가는 경우일 것이다.

우리는 여기서 $F(2i, a) + F(2i+1, x_{2i}), F(2i, x_{2i}) + F(2i+1, a)$ 중 더 작은 경우를 찾아야 하는데, 이 둘의 대소관계는 $F(2i, a) - F(2i+1, a)$, $F(2i, x_{2i}) - F(2i+1, x_{2i})$ 의 대소관계와 같다. 즉, $F(2i, v) - F(2i+1, v)$가 더 작은 $v$를 $2i$번 자리에 넣으면 된다.

이제 $D(i, a)$를 $i$번 자리에 $a$를 넣었을 때, $a$가 이르게 되는 최종 인덱스라고 하자. $u = \min(a, x_{2i}), v = \max(a, x_{2i})$ 라고 하면, $j$번 인덱스에 $u$를 못 넣는다면 $v$또한 넣을 수 없다. 만약 둘 다 넣을 수 있거나 $u$만 넣을 수 있다면 두 경우 모두 반드시 $F(2i, u) - F(2i+1, u)$가 $F(2i, v) - F(2i+1, v)$보다 더 작게 된다. 이로부터, $D(2i, u)$와 $D(2i+1, u)$ 중 더 작은 인덱스로 $u$를 보내는 결정을 할 수 있다.

리프 노드에 대해서 $D(i, x) = i$이기 때문에 $D(i, x)$ 값들을 DP로 관리할 수 있고, $i$의 조상 노드들과 그 형제 노드만 $x$의 후보가 될 수 있으므로 가능한 상태 공간의 수가 $O(N \log N)$개뿐이다. 따라서 전체 시간 복잡도 $O(N \log N)$에 문제를 해결할 수 있다.