POI 2009/2010 (~Platinum + eps) 풀이 및 후기

Mon Oct 16 2023

solved.ac 기준 플래티넘 아래쪽 문제와 monotonicity를 돌았다. 이왕 도는 거 차례대로 돌기로 했다.

Guilds

chessboard coloring을 시도해서, 검은색 지점과 흰색 지점에 길드를 열면 된다. 크기가 $1$인 컴포넌트에 주의. 굳이 이론적으로 표현을 하자면, domatic number가 1인지 2인지 구분하는 문제라고 말할 수 있겠다.

Beads

길이를 고정하고 check를 한다고 할 때, 어떤 두 substring의 비교를 아주 빠르게 할 수 있다면 harmonic lemma가 시간복잡도를 bound해준다. 그러므로 hash 쓰면 된다. 내가 문자열 문제에서 해시 써본 건 이번이 처음인 것 같다.

에디토리얼을 보면서 알게 된 건데, 이런 표현이 맞는지는 모르겠으나 suffix array에서 rank 붙이는 방식을 이용해서 $O(1)$ rmq를 sparse table로 계산하는 것처럼 두 substring을 비교하는 방법을 Karp-Miller-Rosenberg (KMR) algorithm이라고 부르는 것 같다.

한마디로 문자열들을 찾되 순서만 맞으면 된다는 뜻이다. Greedy하게 앞에서부터 매칭될 수 있는 게 있는지 봐주면 된다. 이러면 대략 모든 입력의 길이에 대한 선형로그 정도의 복잡도로 쉽게 구현할 수 있다. 이 문제는 linear time에도 풀 수 있다. 찾고자 하는 패턴을 전부 저장하고, 전체 문자열을 하나씩 읽으면서 현재 보고 있는 문자에 대응시킬 수 있는 모든 패턴의 match_cnt 같은 값을 $1$ 증가시키면 된다.

Antisymmetry

Manacher의 기본 원리는, 내가 어딘가에서 palindrome substring을 찾았을 때 그 substring의 절반 왼쪽과 절반 오른쪽에서 대칭적이므로 왼쪽에서 계산한 정보를 오른쪽에도 그대로 적용할 수 있다는 점이다. 즉 문자의 matching이 아니라 문자의 anti-matching이 궁금하다고 해도, anti-anti-matching은 matching이기 때문에 manacher를 여전히 적용할 수 있는 구조이다. Manacher에서 문자열이 매칭되는 부분만 건드리면 ok. 이 말을 생각해보면 reflexivity도 필요가 없다는 뜻이 되는데, 이건 맞는지 모르겠다. POI 에디토리얼은 정말 최고의 퀄리티를 자랑한다고 느껴지는 부분이, 지금까지 봐온 어떤 manacher를 설명하는 글보다도 여기 에디토리얼에 부록처럼 딸려 있는 manacher 설명이 훨씬 더 자세하고 삽화까지 들어가 있다.

Sheep

처음 본 유형의 기하 문제. 결국 catalan number랑 똑같은 상황 아니냐고 물으면 맞긴 한데, 이 문제는 좀 더 기하적이기도 하고 나는 직접 구현해본 적이 없기 때문에 그렇다. 아까 쓴 Beads 문제도 그렇고, 점점 옛날 셋으로 가는데도 은근 처음 짜보게 되는 문제가 많다. 내가 아직 근본력이 부족하다는 게 느껴진다.

먼저 임의의 볼록 다각형의 세 점 $P_x, P_y, P_z$에 대해 $(P_x, P_y, P_z)$ 삼각형 안에 속하는 점들의 개수를 전부 계산할 방법을 생각해보자. 우선 직선 위에 놓이는 점들을 세지 않도록 하자. 그렇다면 직선 위에 점이 있는지 판별은 ccw가 $0$인지로 쉽게 판별이 되므로, 일반적인 경우를 생각한다. 만약 여집합에 있는 점의 개수를 이미 알고 있다면 문제가 쉬워지는데, 그러한 여집합들은 $x, x+1, \ldots, y$번 정점들로만 이루어진 작은 볼록 다각형 형태이다. 다각형은 순환적이므로 $x > y$라면 $n$으로 나눈 나머지로 숫자를 세다가 한 바퀴 돌아서 $y$에 도달한 작은 다각형을 생각할 수 있다. $2$차원 배열에 아무런 추가 처리 없이 이를 처리할 수 있다는 장점이 있다. 이러한 작은 다각형을 $S_{x,y}$, 그 다각형 내에 있는 점의 개수를 $C_{x,y}$라 하자. $x$를 고정하고 $P_x$를 중심으로 하여 모든 pasture를 각도 정렬하면, 임의의 $y$에 대해 $C_{x,y}$를 전부 알아낼 수 있다. 우선 여기까지의 시간복잡도가 $O(nklogk)$.

이제 위의 정보를 바탕으로 triangulation의 가능한 가짓수를 알아낼 차례이다. 이걸 dp라고 부를 수 있나 싶긴 한데, 마땅한 이름이 생각이 안 나서 그냥 이렇게 쓴다. $dp[x][y]$를 $S_{x,y}$의 조건을 만족하는 triangulation의 가짓수라고 정의하자. 여기서 $P_x, P_y$를 잇는 선분을 생각했을 때, 어떤 triangulation이 주어지면 이 선분을 포함하는 삼각형이 정확히 하나 존재하게 된다. 그 삼각형의 세 번째 점을 $z$라고 한다면, 이러한 경우의 수는 $dp[x][z] \times dp[z][y]$이다. 따라서 $x, y$ 사이에 있는 모든 $z$에 대해서 위 값을 전부 더한 것이 $dp[x][y]$가 된다. 물론 $P_x, P_y, P_z$를 잇는 어떤 선분 위에도 pasture가 존재하지 않으며, 삼각형 내부에 짝수 개의 점이 있는 경우만 valid함에 유의하자. 이렇게 되면 결국 $\lvert x-y \rvert$의 값이 커지는 순서대로 dp 값들을 계산할 수 있으므로, $O(n^3)$ 시간이 소요된다.

나는 여기까지 구현해서 AC를 받긴 했는데, $2.8$초가 걸린 것으로 보아 이게 정해가 맞을까에 대한 의구심이 있다. 물론 내가 느리게 짠 거일 수도 있긴 한데... 첫 번째 파트를 $O(nk)$에 계산하는 방법이 있기 때문이다. $P_x, P_{y-1}, P_y$로 이루어진 삼각형을 $T_{x,y}$라고 하자. 관점을 바꿔서 pasture마다 그 pasture가 포함되는 모든 삼각형에 $+1$을 해준다고 보면, 두 가지 성질이 있다. $x$를 고정했을 때 그 pasture를 포함하는 $T_{x,y}$는 정확히 $1$개만 존재하며, 이를 $T_{x,y(x)}$라고 두면 $y(x) \leq y(x+1)$이라는 것이다. mod 때문에 $y(x)$를 어떤 값으로 해석하면 애매해지는데, 말하고 싶은 건 처음에 주어지는 볼록 다각형 위에서 시계 방향 (아니면 반시계)으로 점을 읽어서 얻은 순서 상으로 그렇다는 것이다. 굳이 기하적인 내용을 엄밀하게 formulate하고 싶지는 않으므로 이 정도에서 마무리.

Teleportation

꽤 재밌었던 문제다. 몇 가지 관찰을 해 보자.

관찰 1. 최종적으로 내가 만든 그래프에서 $1$과 $2$ 사이의 거리는 정확히 $5$이다.

관찰 2. 다른 모든 정점들은 $1$과 $2$ 사이에 위치하는데, 즉 $1$과 $x$만큼, $2$와 $5-x$ 거리만큼 떨어져 있어야 한다. $(1 \leq x \leq 4)$

두 관찰을 만족시키지 않는 정점이 있으면 그 정점에 적당히 간선을 하나 더 추가하면서도 여전히 $1$과 $2$ 사이 거리를 $5$ 이상으로 유지할 수 있기 때문이다. 즉 우리는 이제 'layer' $4$개를 만들 수 있다. $A_x$를 어떤 최적해에서 $1$번 정점으로부터 $x$만큼 떨어진 정점들의 집합이라고 두자. 굳이 정의하자면 $A_0 = \{ 1 \}, A_5 = \{ 2 \}$로 두는 것도 가능하긴 하겠다.

관찰 3. 같은 layer, 혹은 인접한 layer에 존재하는 정점들은 항상 연결되어 있다. 또한 두 layer 이상을 건너뛰어 연결된 정점들은 최단 경로의 정의 상 존재할 수 없다.

그러므로 관찰 3은 우리가 관심 있는 값이 오직 $\lvert A_x \rvert$뿐이라는 것을 알려준다. 이 사실로부터 최종 그래프의 간선의 개수가 다음과 같이 표현되기 때문이다. $$ \sum_{x=1}^4 \lvert A_x \rvert \cdot (\lvert A_{x-1} \rvert + \lvert A_{x} \rvert + \lvert A_{x+1} \rvert) $$

그렇다고 임의의 정점 $v$가 임의의 layer에 속할 수 있진 않을 것이다. 초기 그래프에서 $v$가 $1$과 $d_1$만큼, $2$와는 $d_2$만큼 떨어져 있었다고 하면, 최단 경로의 정의 상 이게 더 늘어나는 건 불가능하므로, $5-d_2 \leq x \leq d_1$을 만족하는 $x$에 대해서만 들어갈 수 있다. 그리고 반대로 그러한 $x$에 반드시 포함될 수 있게 간선을 추가할 수 있다. 즉 모든 정점은 어떻게 보면 $_4C_2 = 6$종류밖에 없었던 것이다. 그러므로 가능한 layer의 cardinality를 무식하게 다 시도해보는 $O(n^3)$ brute force solution까지는 찾은 것이다.

최적해의 성질을 조금 더 관찰하자. 사실 $A_1, A_4$는 $1$, $2$라는 정점 $1$개짜리 layer에 인접해 있기 때문에, 만약 이들이 $A_2$나 $A_3$에 들어갈 수 있었다면 위치를 옮기는 게 더 최적이다. 그러므로 $A_1$와 $A_4$가 유일한 선택지인 정점을 제외하고는, $\lvert A_2 \rvert$의 가능한 값을 전부 시도해보면 된다. 그러므로 최종 풀이는 $O(n+m)$.

Monotonicity 2

원래 POI에서는 Monotonicity로 제한이 더 약한 문제가 출제되었던 것 같은데, 왠지 모르게 더 강한 버전이 있다. 약한 버전은 단순 2차원 dp이다. 강한 버전은 꽤 흥미로운 관찰을 필요로 한다. $dp[i]$를 $[1, i]$ 구간까지만 봤을 때 $i$가 마지막으로 매칭된 위치인 subsequence들 중 최대 길이로 정의하자. 이 때 그러한 최대 길이 subsequence 중 어떤 것은 반드시 어떤 $j < i$에 대해 $j$에서 끝나는 $dp[j]$ 길이를 갖는 최적 subsequence에 $a_i$만 하나 더 붙인 extended subsequence가 된다는 것이다.

증명은 귀류법으로 진행할 수 있다. 위의 명제가 성립하지 않는 최소의 sequence $(a_i)_{i=1}^n$을 생각하자. 즉 $dp[n]$에 대한 어떤 최적해는 임의의 optimal subsequence의 extension이 아니라는 뜻이고, $n$에서 끝나기 직전에 매칭된 문자 위치가 $a_m$이라고 하자. 그러면 case work를 통해서 $dp[m]$ 길이를 갖는 $m$에서 끝나는 subsequence의 suffix를 적절히 제거하고 마지막에 $a_n$을 넣어서 $dp[n]$ 이상의 길이를 가지는 올바른 subsequence를 찾을 수 있고, 귀류 가정의 최소성에 의해 $dp[n]$ 길이를 만드는 extension을 찾은 것이므로 ok.

문제는 이걸 직관적으로 이해하는 방법을 잘 모르겠다는 점이다. Longest Increasing Sequence 문제를 푸는 방법과 비슷해보이는데, 이건 매칭되는 위치에 따라서 그 다음으로 요구되는 대소 관계가 달라지기 때문에 lis 문제의 분석을 그대로 적용할 수 없다. 그렇지만 위의 정리는 그와 비슷한 느낌으로 풀 수 있다는 걸 드러내는데, 뭔가 생각이 더 나면 나중에 추가하도록 하겠다.

결론적으로 풀이는 다음과 같다. Interval query, point update maximum segment tree를 $3$개 만들자. $dp[i]$를 $i$를 증가시키면서 계산해나가되, $s_{dp[i] \% k + 1}$가 무엇인지에 따라 $dp[i]$의 값을 $3$개 중 $1$개의 segment tree에 update하자. 즉 $i$에서 끝나는 최적해를 찾으면, 그 최적해의 길이에 따라 그 다음에 와야 할 scheme의 부등호/등호를 예상하여 다음에 올 수가 자신의 dp 값을 쉽게 계산할 수 있는 위치의 segment tree를 update하겠다는 것이다. 그리고 $dp[i]$를 계산하는 과정은 $3$가지의 세그먼트 트리에 범위에 맞게 쿼리를 날려서 최댓값을 얻어내면 된다.

The Minima Game

먼저 카드를 오름차순으로 정렬하면 누구라도 항상 가장 큰 몇 개의 카드를 가져가는 것만이 최적의 전략이 된다. 아니라면 같은 개수만큼 suffix를 가져가는 것이 항상 더 이득이기 때문이다. 그러므로 $dp[i]$를 가장 작은 $i$개의 카드가 남았을 때, 그 시점에서의 선공이 최대로 얻는 점수 차이라고 정의하자. 그러면 $k_i$만 가져갈 때와 $k_j (j<i)$를 가져갈 때를 생각하면 다음과 같은 점화식이 성립한다. $$ dp[i] = max(dp[i-1], k_i-dp[i-1])$$

Frog

만약 $p_i$ 위치에서 다음으로 leap할 위치를 모든 $1 \leq i \leq n$에 대해서 구할 수 있다면, 남은 문제는 sparse table을 구축해서 풀 수 있다. $p_i$를 중심으로 반지름 $r_i$인 구간 $[p_i-r_i, p_i+r_i]$에 총 $k+1$개 혹은 $k+2$개의 바위가 들어가게 하는 최소의 $r_i$가 존재할 것이다. 그러면 $i$가 증가할 때 최소한 $r_{i+1} \leq p_{i+1}-r_i$이기는 할 것이므로, $p_i-r_i \leq p_{i+1}-r_{i+1}$과 $p_i+r_i \leq p_{i+1}+r_{i+1}$이 성립한다. 이러한 구조는 two pointer로 관리할 수 있으므로 ok. 동일 거리만큼 떨어져 있어 왼쪽의 바위를 선택해야 하는 tie breaking 상황에 주의하면서 구현하면 된다.

Pilots

말 그대로 굉장히 웰노운인 문제. 옛날에 풀려 있었던 문제여서 대충만 쓴다. 바로 위에 설명한 frog 문제와 비슷하다. 모든 $i$에 대해 $[i, j]$ 구간이 문제의 조건을 만족하는 구간이 되는 최대의 $j$가 항상 유일하게 존재한다. 그러므로 two pointer로 이를 관리하면서, 구간 내의 maximum element와 minimum element가 deque으로 관리할 수 있는 형태이므로 ok.