Polish Problems (1~5)

폴란드에는 양질의 문제가 많다. 타 국가에서 폴란드의 문제들을 가져와 여러 용도로 활용하기도 할 정도이다. 이 포스팅에는 폴란드의 Poland Olympiad in Informatics, Algorithmic Engagement 등에 수록된 여러 좋은 문제들을 다룬 자료집에 있는 문제들을 연습한 내용을 정리할 것이다. 여러가지 이유로 문제가 저평가되는 경우도 있지만 기본적으로 다들 굉장히 재미있는 것들이라고 생각한다. 많은 수를 자력으로 풀지 못해 풀이를 봐야 했었다. ㅠ

acmicpc.net에 수록되어 있는 문제는 해당 문제의 링크가 걸려 있다.

□ Axes of Symmetry (14회 POI, #)

계절학교에서 처음 들은 이후로 꽤 인상깊었던 문제인데, 이미 기출 문제였을 줄은 몰랐다. 정수 점만 가지고는 테스트케이스를 충분히 만들기 어려울 것 같았기 때문이다. 아무튼 이 문제는 풀이가 꽤 재미있으니 충분히 생각해보고 풀이를 보도록 하자.

1. 어떤 대칭축은 무조건 변을 수직으로 이등분하거나 각을 이등분한다.

2. 당연히도, 대칭축 양쪽의 도형은 완전히 같은 모양의 거울상이다.

한 번 하나의 각과 하나의 변을 하나의 글자로 나타내어 보자. 그러면 $n$각형은 각과 변에 해당하는 글자가 번갈아 나타나는 길이 $2n$의 환형 문자열이 된다. 그리고 어떤 각(또는 변)을 이등분하는 직선이 대칭축이라는 것은 이 각(변)에 해당하는 글자를 중심으로 길이 $2n-1$ 이상의(문자열이 무한히 연장된다면 무한대의 길이가 될 것이다) 팰린드롬을 이룬다, 즉 양쪽의 각과 변이 모두 같은 크기와 길이를 가지고 있다는 것을 뜻한다.

위의 풀이에는 Manacher의 알고리즘을 사용할 수 있다. 변은 길이(의 제곱)로, 각은 양변에 끼인 CCW 값으로 나타낸다. 변과 각에 대한 표시를 구분해도 되지만, 구분하지 않아도 둘의 표시가 겹쳐서 생길 수 있는 문제는 없다. 환형 문자열이므로 문자열을 두 번 나열해놓고 가운데 $length\over2$($n$)에서 $3\times length\over2$($3n$)까지의 인덱스의 팰린드롬만 확인해도 문제없다. 대칭축이 서로 반대 방향에서 두 번 나타날 것임을 생각해 답을 2로 나누는 것을 잊지 말자.

별해: 다각형을 변환시킨 수열 $S$를 두 번 이어붙인다. 그 문자열 안에서 $S$를 거꾸로 한 문자열의 개수를 KMP 알고리즘으로 찾아도 답이 나온다.

□ Party (10회 POI, #)

보이는 것과 달리 쉽고 간단한 문제이다. 그래프에서 최대 클릭을 구하는 것은 굉장히 어려운 NP-hard 문제로 알려져 있다. 그런데 이번에는 크기가 $3n$인 그래프의 클릭의 크기가 $2n$ 이상이라는 것이 주어져 있을 때 크기가 $n$인 클릭을 하나 찾는 문제이다. 제한이 굉장히 널널한데, 어떻게 풀어야 할까?

풀이는 세 줄로 끝난다.

1. 연결되지 않은 두 정점을 고른다. 두 정점 중 하나는 클릭에 포함되지 않을텐데, 두 점 중 무엇일까? 그냥 둘 다 제외시키자.

2. 1번 과정을 $n$번 반복하면 클릭에 포함되지 않은 최대 $n$개의 정점이 모두 지워지고, 클릭에 반드시 포함되는 $n$개의 점이 남는다.

3. 남은 $n$개의 점을 출력한다.

한참을 고민했는데 이런 간단한 풀이가 존재한다는 사실을 알고 정말 놀랐다. 더 공부해야 될 것 같다 ㅠ

□ Byteland (1회 JPOI)

Author solution은 다음과 같다: 최소 스패닝 트리를 하나 구성해 놓고, 포함되지 않은 각 간선에 대해 이 간선이 스패닝 트리의 간선을 대체할 수 있는지를 판단할 것이다. 어떤 간선 $(u, v)$가 스패닝 트리의 어떤 간선을 대체하려면 스패닝 트리에서 $u$와 $v$를 잇는 경로의 간선의 무게 중 최댓값과 무게가 같아야 한다. (작은 것은 불가능하다.) 그러면 경로의 가장 무거운 간선을 $(u, v)$로 대체할 수 있을 것이다. DFS를 통해서 이를 판별할 수 있다고 한다.

나와 다른 학생들은 모두 다른 솔루션을 쓴 것 같다. 크루스칼 알고리즘을 응용해, 간선을 무게의 오름차순으로 정렬한다. 무게 $w$인 간선 $(u, v)$가 사용될 수 있다는 것은, $w$보다 작은 무게의 간선들을 이용해 만든 스패닝 트리 조각에서 $u$와 $v$가 분리되어 있다는 뜻이다. 각 무게에 대해서 무게에 속하는 모든 간선에 대해 판별하고 스패닝 트리에 추가해주면 된다.

□ Barricades (AE 2007)

시간 복잡도 분석이 캐리한 문제이다. 처음 볼 때는 누가 봐도 $O(n^3)$일 것 같아 통과하지 않을 것같이 생긴 풀이가, 실은 $O(n^2)$이다.

$f(k, x)$를 다음과 같이 정의하자: $k$를 루트로 한 서브트리에서 $x$를 포함하는 크기 $x$의 컴포넌트를 골랐을 때 주변 간선 수의 최솟값.

따라서 $f(k, x)$에서는 $x$와, $x$의 자식들에서 $x-1$개를 나누어 고르게 된다. 자식에게서 나누어 고르는 경우의 수를 일일히 세기는 힘들기에, $x$에 자식이 없었다고 가정하고 하나씩 붙이면서 $f$값을 합쳐보자.

$k$의 자식이 $c_1, c_2, \cdots , c_t$라고 하자. 그리고 $f_i(k, x)$를 $k$의 $i$번째 자식까지만 달려 있는 트리에서의 $f$값이라고 생각하자. 그러면 $f_0(k, 1) = 1$이고, $f_i(k, x) = \min_{a+b=x} \left( f_{i-1}(k, a) \times f(c_i, b) \right)$이다. 따라서 차례대로 $f_{i-1}(k, -)$과 $f(c_i, -)$의 값들을 합쳐가며 모든 $i$에 대해 $f_i(k, -)$를 채울 수 있다. $f(k, -) = f_t(k, -)$이다.

이 방법이 모든 정점에 대해 $\sum_{i<j} c_i \times c_j$의 시간을 소요하기 때문에, 각 정점에 대해 $O(n^2)$의 시간이 소요되어 $O(n^3)$로 보일 수도 있다. 그래서 시간이 너무 많이 걸릴 거라 생각했다면, 속은 것이다. $f_{i-1}(k, -)$과 $f(c_i, -)$을 합칠 때 하는 연산들은 $c_{1..i-1} \cup \{k\}$의 정점들과 $c_i$의 정점들의 pair와 일대일 대응될 수 있다. 모든 계산과정을 합치면 모든 서로 다른 정점들의 쌍에 대해 각 연산이 일대일대응되게 되고, 따라서 $O(n^2)$ 안에 알고리즘이 작동할 수 있게 된다.

OI에서는 부분점수 받으려고 짰다가 만점을 받는 경우도 존재하기 때문에 문제가 되지 않지만, 나중에 참가할 부분점수가 없거나 제한적인 대회(ICPC, GCJ 등)에 참여하게 될 때는 이 알고리즘이 더 타이트한 시간복잡도로 작동하지 않을까를 고민해보자.

□ Ice Skates (16회 POI, #)

어떤 스케이트화의 집합이 있을 때, 이들을 모든 부원에게 줄 수 있다는 것은 다음 명제와 동치이다.

모든 $s \le e$에 대해, $a_s + \cdots + a_e \le (e-s+d+1)k$.

이 때 $b_i = a_i - k$로 두게 되면, 이 식은 $b_s + \cdots + b_e \le dk$로 바뀌게 된다. 이는, 모든 가능한 구간에 대해 구간의 원소의 합이 상수 $dk$ 이하라는 것이다. 구간 합의 최댓값을 구하는 문제는 [구간의 부분구간의 합의 최댓값, 전체 구간의 합, 접두사 구간의 합의 최댓값, 접미사 구간의 합의 최댓값]을 각 노드에 저장하는 세그먼트 트리를 만들어 해결할 수 있다.