Polish Problems (11-15)

□ Reconstruction of Byteland (AE 2008)

긴 제목을 보고 언젠간 꼭 풀고 싶었던 문제였으나 그리 어렵진 않았다. 이런 문제들은 보통 소수가 아닌 다른 간단한 아이디어를 이용하기 마련이다. 예제에 있는 크기 5의 풀이를 일반적으로 확장할 수 있을까? 그냥 $n$개를 풀이할 때에 $\lfloor {n\over5} \rfloor$개씩 나누어 5개의 주소를 나누어 쓰면 되지 않을까? 하지만 이 방법은 각 번호가 달라야 함에 위반된다. 그러니, 각 주소에 대해서 쓰지 않는 적당히 큰 소수를 하나씩 곱해 주자. 100개 뿐이므로 서로 다른 소수를 곱한다 해도 10^9보다 클 리는 없다.

□ Rooks (3회 POI)

머리 속에 체스판을 생각하면 풀 수 없다. 체스판을 위나 왼쪽(중 아무거나 하나)에서 그림자를 내려보자. 그러면 문제는 서로 다른 독립적인 두 1차원 문제로 바뀐다. "일렬로 있는 $n$개의 칸들에 룩을 하나씩 채워야 한다. 이 때 각 룩은 있을 수 있는 범위가 $[s_i, e_i]$로 제한되어 있다. 이 때에 룩을 놓을 수 있는 아무 방법이나 하나 구하라." 이제 이 문제는 유명한 그리디 풀이를 가진다. # 이 문제와 같으니, 한 번 생각해 보도록 하자.

□ Termites (AE 2010, #)

문제는 흔한 DP로 풀릴 게임 문제같이 보이지만, 크기 제한이 무지하게 크다. 이게 풀 수 있는 것인지 의문이 들 정도. 당연히 이렇게 큰 제한을 걸었다는 것은 그리디가 정해라는 것일 거다. 그리고 실제로도 그리디가 정해이다. 풀이는 몇 개의 Lemma로 구성된다. Lemma들이 참임을 아는 순간 문제는 꽤 간단하게 풀리지만, 이들을 찾지 못한다면 절대 풀 수 없다. 증명은 건너뛴다. (솔직히 잘 모르겠다)

Lemma 1, 2는 중간이 비어있지 않아 중간에서 plank를 가져갈 수 없고, 양 끝 가장자리에서 plank를 가져갈 수 있는 상황을 다루고 있다. 즉, 양의 정수열 $a_1$, $\cdots$, $a_n$의 양 끝에서 하나씩 가져가는 게임을 다루고 있다.

Lemma 1. 수열에서 가장 큰 원소 $M$이 가장자리에 있으면, 플레이어는 무조건 $M$을 가져가는 게 최적이다.

Lemma 2. 수열 가운데에 $x$, $M$, $y$가 차례대로 있고, $x \le M$, $M \ge y$를 만족한다면(꼭 M이 수열에서 가장 큰 원소일 필요는 없다) 세 수를 하나의 수 $x+y-M$으로 갈음해도 같은 결과가 만들어진다.

Lemma 2를 적절히 활용하면, 문제 수열을 바이토닉, 즉 점점 감소하다가 다시 증가하는 수열로 바꿀 수 있으며, 이는 Lemma 1을 항상 이용할 수 있는 꼴이 된다. 그리고, 사실은 위 두 Lemma는 양 끝에서 가져가는 게임 뿐만 아니라, 가져가는 위치가 여러 개인 본 문제에서도 그대로 적용된다. 다만, 수열의 양 끝이 비어있지 않다면 수열의 양끝에서는 가져갈 수 없다. 이는 새로운 Lemma를 통해 해결할 수 있다.

Lemma 3. "가져갈 수 없는 끝"에 $x$, $M$($x \le M$)이 차례대로 있고, $M$이 수열의 끝에 있다면, $M$과 $x$를 제거하고, $x$를 무조건 먹어야 하는 사람(전체 원소가 짝수 개 -> A, 홀수 개 -> B)에게 $M-x$만큼의 패널티를 주는 것과 동등한 문제이다.

어떻게 생각해 냈는지와, 정말 참인지, 또 어떻게 증명하는 건지는 모르겠지만 이 세 보조정리를 적절히 활용하면 문제를 $O(n\log n)$으로 풀 수 있다고 한다~!

□ Game of Tokens (ONTAK 2010)

재미있는 인터랙티브 문제. 영어 실력이 딸리면 무슨 이야기를 하는지 이해하기 힘들 수 있다. 나도 그랬다. 문제의 뜻은, $1$에서 $n$까지 적혀있는 토큰들이 있고, $n \times n$의 격자판 $a$가 있을 때에, 토큰을 각 플레이어가 하나씩 골라 ($S$가 플레이어의 토큰들의 집합일 때) $\sum_{i, j \in S} a_{ij}$, 즉 열과 행이 모두 자기 소유인 칸의 수들의 합을 최대화하는 것이다.

어떤 토큰 $i$를 가질 때와 가지지 않을 때를 비교해보자. 그러면 다른 토큰의 소유권이 누구에게 있든 전체 점수 차이는 $score_i = \sum_k \left( a_{ik} + a_{ki} \right)$만큼 나타나게 된다. 따라서 매번 남아있는 토큰들 중에서 가장 큰 $score_i$ 값을 가지고 있는 토큰을 고르면 된다.

□ Termites 2 (AE 2010, #)

더 짧은 시간에 작동하는 풀이가 있다곤 하지만, 난 잘 모르겠고, $O(n \log^2 n)$ 풀이를 적는다. 선형 시간에 작동하는 풀이도 존재한다고 한다. 원래 그래프가 비어있는 포레스트이고, 간선을 이을 때마다 하나씩 간선을 추가한다고 생각하면, 간선을 이을 때마다 두 개의 서로 다른 컴포넌트가 연결된다는 것을 알 수 있다. 그리고, 각 컴포넌트에서는 무조건 하나의 정점만이 남아있고, 나머지는 모두 먹었을 거라는 것도 알 수 있다. 이 때, 두 집합을 정의하자.

$A(T)$ $:=$ 포레스트의 어떤 컴포넌트 $T$에서, A가 마음먹으면 남길 수 있는 정점의 집합

$B(T)$ $:=$ $T$에서, B가 마음먹으면 남길 수 있는 정점의 집합

초기에, $A(T)$와 $B(T)$에는 모두 $T$에 있는 유일한 정점을 담고 있다. 이 때, $T_1$ 컴포넌트의 정점 $u$와 $T_2$ 컴포넌트의 정점 $v$를 $A$가 연결한다고 하자. 이 때 크게 네 가지 경우로 나눌 수 있다. 

$u \in A(T_1)$이고, $v \in A(T_2)$일 때: $A(T) = A(T_1) \cup A(T_2)$, $B(T) = \emptyset$

$u \in A(T_1)$이고, $v \notin A(T_2)$일 때: $A(T) = A(T_2)$, $B(T) = B(T_2) - \left\{ v \right\}$

$u \notin A(T_1)$이고, $v \in A(T_2)$일 때: $A(T) = A(T_1)$, $B(T) = B(T_1) - \left\{ u \right\}$

$u \notin A(T_1)$이고, $v \notin A(T_2)$일 때: 게임이 끝난다. $B$는 $A$가 이 정점을 무조건 먹지 못하게 만들 수 있다.

이는 Union-find를 이용하여, 각 집합에 대하여 하나의 집합을 유지하며 해결할 수 있다. 무조건 작은 집합을 큰 집합에 집어넣는 방식으로 구현하면, $O(n \log^2 n)$의 시간복잡도가 나온다.

여기까지가 <Looking for a challenge?>의 50개 조금 넘는 문제들 중 1/3에 해당하는 풀이이다. 목록 안에 있는 문제들만 골라서 푸는 것도 나름 굉장히 기분 나쁜 일인 것 같다. 남은 문제들은 그냥 한 번씩 이해해보는 정도로 끝내야 할 것 같다.