Polish Problems (6-10)

□ Chocolate (3회 POI, #)

이런 류의 문제에서 흔히 쓰이는 아이디어로(#의 D에도 등장했다), 자르는 순서열을 나열한 후 인접한 원소를 바꾸는 게 이득인 경우를 생각한다. 인접한 원소를 바꾸어서 이득을 보는 경우가 없다면 무조건 전체 순서열 중 최적이다. 이 문제의 경우에는 단순히 비용의 내림차순으로 정렬하고(같은 비용의 자르기는 어떤 순서로 배열해도 무관함) 그 순서대로 자르면 된다.

□ Guilds (10회 POI, #)

일단, 어떤 정점에 오피스를 만들지 않을 이유는 없다. 만들어서 손해볼 일은 없기 때문. 그래프가 연결되었다고 가정하고(아니면 각 컴포넌트에 대해 계산하면 되니) 생각하자. 그래프의 크기가 1이라면 절대 조건을 만족시킬 수 없다. 하지만, 그래프의 크기가 2 이상인 경우 다음과 같은 간단한 방법이 조건을 만족시킬 수 있다.

1. 임의의 정점에 오피스 A를 짓는다.

2. 이 정점에서 갈 수 있는 모든 정점에 오피스 B를 짓는다.

3. 다시 이 정점에서 갈 수 있는 모든 빈 정점에 오피스 A를 짓는다.

4. ...

□ Building blocks (8회 POI, #)

어떤 $k$개의 블록을 같은 높이로 만들려고 한다. 이 때 높이를 블록들의 높이의 중간값으로 하는 것이 최적이다. (짝수 개라면, 두 중간값의 사이에 있는 어떤 높이든 최적이다.) 따라서, 길이가 일정한 움직이는 구간 $h_i, \cdots, h_{i+k-1}$에서 중간값과의 편차의 합을 구하고, 이의 최솟값을 구하는 문제와 같게 된다. #와 같이 전형적인 Running-Median 문제는 최대/최소로 2개의 우선순위 큐를 활용한다. 이 문제도 같은 방법으로 해결할 수 있다. 다만, 원소를 빼는 연산도 필요하다. 그래서 같은 기능을 사용할 수 있는 2개의 set을 써서, 똑같이 구현하면 된다.

BOJ에 수록된 이 문제에는 아직 special judge가 구현되어 있지 않다. 관심 있다면 구현해 보자..

□ Two Parties (12회 POI)

공식 솔루션은 아니지만, 약간의 선형대수를 알면 보다 깔끔하게 풀린다. 공식 솔루션에는 매칭을 하나씩 수정해나가는 방식으로 하는 것 같다. 읽고 나서 추가해보겠다.

먼저, 결론은 항상 모든 정점이 짝수 개의 이웃을 가지게 나눌 수 있다는 것이다. 이는 나중에 증명할 것이다. (솔직히 모두 짝수 개로 매칭이 될 거란 생각을 어떻게 먼저 하는지 잘 모르겠다. 감이 좋아야 하는 건가?) 그래프의 인접 행렬을 크기 $n \times n$인 행렬 $A$라 하자. 그리고 크기 $n$인 벡터 $x$를 정의해서, 각 정점에 대해서 각 사람이 속할 파티를 나타내게 하자. $x_i=0$이라면 첫 번째 파티에, $x_i=1$이라면 두 번째 파티에 $i$번째 사람이 들어있는 것이다. 그러면, 어떤 정점이 문제의 조건을 만족하게 하려면, 다음 식을 만족해야 한다.

$x_i = 1$이라면, $\sum_j a_{ij} x_j \equiv 0 (mod 2)$,

$x_i = 0$이라면, $\sum_j a_{ij} (1-x_j) \equiv 0 (mod 2)$.

식을 정리하고 일반화하면 다음과 같이 바뀐다.

$k = \sum_j a_{ij}$일 때, $\sum_j a_{ij} x_j + kx_i \equiv k (mod 2)$

따라서 크기 $n$의 벡터 $b$를 정의해 $b_i = \sum_j a_{ij}$라고 하고, $A$의 대각성분 $a_{ii} = b_i$로 설정하면, $Ax \equiv b$인 $x$를 찾는 문제가 된다. 일반적인 연립방정식 문제와 모듈러 연산이 있다는 것 빼고 동일한 문제이다. 이 방정식은 항상 해가 존재하고(*), Gauss-Jordan 소거법을 사용하면 해결된다.

*

Lemma. 위 방정식은 항상 consistent하다.
Proof. 이 방정식이 consistent하다는 것은, augmented matrix $A$에서 몇 개의 열을 더해 $[0 \cdots 0 | 1]$인 경우가 없다는 것이다. 만약 그런 행 몇 개 $x_1, \cdots, x_k$가 존재한다고 하자. 이 행들만 모으면(i.e. 다른 행들을 모두 0으로 만들자), 마지막 열을 제외한 모든 열의 원소의 합이 짝수일 것이다.

이 행들을 모았을 때에 $x_1, \cdots, x_k$열은, $A_{x_i x_j} = A_{x_j x_i}$를 만족한다. 따라서, $\sum_{i, j} A_{x_i x_j} = \sum_i A_{x_i x_i} + 2 \sum_{i<j} A_{x_i x_i} \equiv \sum_i A_{x_i x_i}$일 것이다. 하지만, 첨가 열의 원소의 합이 홀수이므로, 대각선의 원소의 합도 홀수여야 한다. (각 원소가 같으니까) 이는 각 열의 원소의 합이 짝수임에 모순이다.

□ Cave (11회 POI)

이 문제는 어떠한 그리디와 규칙으로도 쉬운 답이 찾아지지 않는다.(Quoted by koosaga) 말 그대로 갓 문제라는 것이다. POI 사상 가장 어려웠던 이 문제를 해결하기 위해서는 보다 더 근본적으로 문제에 접근해야 한다.

문제에 대한 어떤 해답이 존재한다면, 이 해답은 이런 형태를 띨 것이다:

1. 어떤 정점에서 첫 질문을 하자.

2. 이 질문에서 이 방향이 나오면 이 정점, 저 방향이 나오면 저 정점, $\cdots$를 다시 질문하자.

3. 다시 그 결과에 따라..

이런 방법에 따라서 질문을 하게 되면, 하나의 정점에 대해서는 최대 한 번의 질문을 할 수 있게 되고, 각 정점에 대해 "이 정점을 질문했다면, 확실히 답을 맞출 수 있게 되기까지 남은 질문의 수"를 정의할 수 있게 된다. 중요한 사실은, 각 정점에 대해서 정의된 이러한 형태의 함수가, 역으로 문제의 해답에 대응된다는 것이다.

모든 정점에 대해 자연수 또는 0을 대응시키는 어떤 함수 $f(v)$를 정의하자. 이 함수는 다음을 만족한다.

어떤 서로 다른 $u$, $v$에 대해 $f(u) = f(v)$이면, $u$와 $v$를 잇는 경로 위의 정점 $k$가 존재해 $f(k) > f(v)$를 만족한다.

함수 $f$가 위 성질을 만족한다면, 이 함수를 따라 질문하는 것은 쉽다. 단순히 현재 트리의 가장 높은 함숫값에 대응되는 정점(유일하다)에 대해 질문하고, 대답에 해당하는 부트리를 따라가면(이 말은, 이 부트리를 제외한 나머지를 트리에서 지운다는 것이다) 된다. 결국 답은 $\max_v f(v)$, 즉 모든 $v$에 대해 $f(v)$의 최댓값이 된다. 그럼 이제 하나의 문제만 해결하면 된다(사실 가장 어렵다). $\max_v f(v)$를 최소화하려면 또 어떻게 해야 하는가?

이 방법에 대해 설명하기 이전에, 정답의 최댓값의 상한에 대해 생각해 보자.

Lemma 1. $\max_v f(v) \le \log_2 n$.

Pf. 트리의 지름은 정점의 개수 $n$보다 작다. 트리의 지름이 1이라면 $f(v) = 0$이 되고, 한 번의 질문으로 트리의 지름을 무조건 절반은 줄일 수 있다: 트리의 centroid에 질문하면 된다.

이로부터, 정답은 $log_2 n$ 이하임을 알았다. $n \le 50000$이므로 정답은 많아야 16이다.

트리의 아무 정점에 루트를 잡자(이 정점에서 질문을 시작한다는 뜻은 절대 아니다). 그러면 트리 DP와 같은 방식으로 다음을 생각할 수 있다.

0. 정점 $v$에 무슨 함숫값을 부여해야 할 지를 생각해보자.

1. 모든 자식들에 대해 "고려해야 하는 자손들의 함숫값들"에 대한 정보를 받자. 고려해야 한다는 것은, 어떤 후손 노드에서 등장하였지만 그 노드에서 부모를 타고 올라가면서 아직 그보다 큰 값을 만나지 못한 경우를 뜻한다. 비트마스크를 이용하면 편할 것이지만 안 그래도 별 상관 없다.

2-1. 이 때, 자식들의 고려할 함숫값 목록에 들어간 함숫값은 사용하면 안 된다. 둘을 잇는 경로 사이에 더 큰 값이 존재하지 않기 때문이다.

2-2. 서로 다른 두 개의 자식들의 고려할 함숫값 목록에 들어있는 함숫값은, 지금 $v$에서 해결해야 한다: $f(v)$는 그 함숫값보다는 커야 한다.

3. 2번의 조건을 모두 만족하는 함숫값 $f(v)$가 결정되었다면, 만족하는 값들 중 아무거나 택하자(나중에 가장 작은 값을 택하면 최적임을 증명할 것이다). 후손들의 함숫값들 중 $f(v)$보다 작은 값들은 고려 대상에서 지우자.

물론, 정답은 루트의 고려할 함숫값 목록에 들어있을 것이다. 가장 큰 함숫값은 단 한 번만 등장할 것이기 때문.

Lemma 2. $f(v)$로 가능한 값들 중 최솟값인 $m$을 고르지 않고 $f(v) = m' > m$를 골랐을 때, $m$을 고른 경우보다 최적해가 더 좋을 수는 없다.

Pf. 그것이 실제로 일어났다고 하자. 물론 $v$의 서브트리에는 $m$과 $m'$ 모두 존재하지 않을 것이다. 만약 트리의 다른 값들 중에 $m$이 없었다고 하면 그대로 $f(v)=m$으로 바꾸어도 똑같이 최적일 것이다. 만약 $f(u)=m$이 있었다고 하자(물론 여러 개였을 수도 있다). $f(v)=m'$가 첫번째 선택으로 남은 상황에서의 부트리를 생각해보자. 하지만 다른 $f(u)=m$이 없는 범위(쪼-금만 더 작은 부트리) 안에서 $v$를 선택하면 $m$번 안에도 답을 구할 수 있다. $v$와 가능한 모든 $u$와의 경로 위에 있는 어떤 노드 $x$에게 $f(x) = m'$를 주고, $f(v) = m$으로 바꾸어 계산해도 적어도 손해는 보지 않는다. (문자를 사용한 엄밀한 증명은 #를 참조하자)

위로부터, 무조건 가장 작은 값만을 택하며 올라가는 것이 최적임을 알 수 있다.

이 문제는 IOI에 출제되었어도 가장 어려운 문제로 랭크되었으리라 생각된다.(왜인지 출제자의 머리에서는 꽤 쉽게 풀이가 나온 것으로 보인다) 나 또한 이 문제의 풀이로 지면의 절반 초과를 할애했다. 출제자는 이 문제를 낸 후 이 문제를 가지고 "이분탐색의 트리에의 일반화"라는 주제로 논문을 썼다고 한다.