KOI 2020 고등부 후기

KOI 2020 본선 문제는 다소 쉬웠지만 문제의 질은 보통 이상이었던 것 같습니다. 예선 난이도가 상당히 극단적이었기 때문에 본선이 어떻게 나올 지 도저히 감을 못 잡았는데, 나름대로 만족스러운 성적을 얻어 좋습니다.

 

대회 시작 전

대회 시작 전, 여유롭게 codeblocks abbreviation 몇 개를 추가하고 간단한 프로그램을 만들어 실행시켜 봤는데, 실행이 되지 않았습니다. 당황한 나머지 python을 써야 하는 건가 잠시 고민했는데, 옆 컴퓨터로 옮겨서 실행해도 마찬가지였습니다. 그때 누군가 <bits/stdc++.h>는 비표준 헤더라 사용할 수 없다는 사실을 알려 주었고, 그 뒤로 이 대회에서는 STL 자료구조 등을 쓸 때마다 그때그때 필요한 헤더를 include 하게 되었습니다. 여러모로 불편했지만 bits/stdc++.h가 표준 헤더가 아닌 것은 맞으니 어쩔 수 없었습니다.

 

간단한 연습 문제를 풀어야 했는데, 이 연습 문제는 정올 고등부 예선 1번 문제였습니다. 하지만 앞서 설명한 문제로 시간이 많이 흘렀기 때문에, 연습 세션 종료 1분 전인 1시 24분에 겨우 제출해 맞을 수 있었습니다.

 

연습 세션이 종료되고, 초조한 마음으로 대회 시작을 기다렸습니다.

 

대회 시작 ~ 0:05

대회가 시작되자, 일단 빠르게 네 문제의 지문을 다운받았습니다. 그리고 첫 문제를 읽었는데, 코포에서 한 번쯤 본 듯한 문제가 나왔습니다. 또 제가 PMCC B번에 비슷한 문제를 낸 전적도 있기에, 곧바로 풀이를 구현하고 100점을 받았습니다.

 

$S$와 $T$의 길이를 각각 $n$, $m$이라고 둡시다. 또, 문자열 $T$를 무한 반복한 문자열을 $T_\infty$라고 합시다. 또 $S$의 $[1, i]$번 문자가 $T_\infty$의 $[1, j]$번 문자의 부분 문자열이 되는 최소 $j$를 $a_i$라고 합시다. 우리의 목표는 $a_n$을 구하는 것입니다.

 

수열 $a$는 간단한 DP로 구할 수 있습니다. $a_{i+1}$은 $T_\infty$에서 문자 $S[i+1]$의 위치 중 $a_{i}$보다 큰 가장 작은 값이 될 것입니다. 이것은 사전에 각 문자의 출현 위치를 배열에 담아 놓고 정렬한 후, std::upper_bound 등을 이용하는 것으로 쉽게 구할 수 있습니다. 시간 복잡도는 $O(M + N \log M)$입니다.

 

0:05 ~ 0:35

이후 2번 문제를 풀기 위해 노력했으나, 2번 문제는 생각만큼 쉽게 풀리지 않았습니다. 3번부터 볼까 생각했지만, 3번이 2번보다 어려울 것이라는 근거 없는 믿음을 가지고 있었기 때문에 2번만큼은 풀고 다음 문제를 읽기로 했습니다. 그렇게 20분쯤 고민한 끝에 결정적인 관찰을 했고, 문제를 풀었습니다.

 

수열 $A$에서 인접한 두 원소를 왼쪽부터 차례로 비교하고, 왼쪽이 더 크면 -1, 오른쪽이 더 크면 1을 적어 나간 수열을 $f(A)$라고 합시다. 예를 들어 $f([1, 3, 3, 5, 1]) = [1, 1, -1]$입니다. 인접한 수가 같으면 무시하고 넘어가기로 합시다.

 

또 수열 $B_n$을 $\sum_{i=0}^{n-1} [(-1)^{i}]^\infty$라고 정의합시다. 이때 수열의 합은 두 수열을 이어붙인 것으로, 수열의 거듭제곱은 수열을 일정 횟수 반복한 것으로 정의합니다. 이때 $g(x)$를 수열 $x$가 $B_n$의 부분 수열이 되는 최소 $n$으로 정의합시다.

 

우리가 할 수 있는 관찰은 다음과 같습니다.

 

한 번의 순서 섞기 연산에서 $g(f(A))$는 반절 이상 줄어들 수 없다.

 

이를 증명하기 위해서는 $g(f(A))$를 이해하는 것이 필요합니다. 사실 수학적으로 엄밀하게 설명하다 보니 정의가 길어졌는데, 이 정의는 그냥 수열이 몇 번 오르락 내리락 하느냐와 같은 정의입니다. 그러면 우리가 이 수치를 줄일 수 있는 최선은 양쪽 끝에서 적절히 선택해 주는 방법밖에 없는데, 이때 $g(f(A))$가 반이 된다는 사실을 찾을 수 있습니다. 따라서 문제를 $O(N)$에 해결할 수 있습니다.

 

0:35 ~ 01:19

이후 3번 풀이가 잘 보이지 않아 4번으로 넘어갔습니다. 4번 문제는 KOI 2019 초등부 로봇 과 비슷해 보였습니다. 하지만 원형이 아닌 선형이었기 때문에, 꽤 쉽게 풀릴 거라는 생각을 했고, 5분만에 풀이 비슷한 것을 얻어내 바로 구현에 들어갔습니다. 하지만 반례가 있었는지 잘 통과되지 않았습니다. 일단 저는 3번부터 풀고 오자고 생각했고, 3번 문제를 생각하기 시작했습니다.

 

01:19 ~ 03:00

그런데 그때 마침 3번 문제에서 parametric search를 해보자는 생각이 들었고, 문제를 결정 문제로 바꾸고 나니 어느 정도 길이 보이기 시작했습니다. 약 10분 정도 고민한 끝에 풀이가 나왔고, 이를 구현하는 데 1시간 정도가 걸렸지만 여러 가지 오류를 해결하고 5초라는 (생각보다 빡빡한) 시간 제한 안에 넣기 위해 여러 최적화를 한 끝에 대회 시작 3시간 후에 100점을 받을 수 있었습니다.

 

 

문제를 결정 문제로 바꿔, '길이가 $L$인 정사각형으로 모든 색의 점을 덮을 수 있는가?'라는 문제를 풀어 봅시다.

 

$N=K$일 때

(실제로는 없는 서브태스크이지만, 편의상 넣었습니다.)

 

$N=K$이므로 모든 점의 색이 다릅니다. 즉, 우리의 목표는 모든 점을 사각형으로 덮을 수 있는지 보는 것입니다. 물론 이 문제는 브론즈 수준으로 매우 쉽게 풀리지만 그냥 무시해 주세요.

 

여기서 우리는, 정사각형의 왼쪽 끝 꼭짓점의 범위를 생각할 것입니다. 이 범위는 모든 점 $i$에 대해 점 $i$를 오른쪽 위 꼭짓점으로 가지는 한 변의 길이가 $L$인 정사각형 위에 있어야 하고, 이 정사각형들의 교집합이 될 것입니다. 마찬가지로 이 교집합을 찾는 데에도 개구리 2 문제와 같은 여러 가지 테크닉이 있지만, 우리는 굳이 이 문제를 세그먼트 트리를 이용해 풀 것입니다.

 

plane sweeping을 할 것인데, sweeping을 하면서 정사각형의 시작을 만나면 그 구간에 1을 더하고, 정사각형의 끝을 만나면 그 구간에 -1을 더할 것입니다. 이때 구간 최댓값 쿼리를 전체 구간에 계속 날려 주면서, 한 번이라도 최댓값이 $K$가 되는 곳이 있는지 판별해 주면 될 것입니다. 이때의 전체 문제 시간 복잡도는 $O(N \log^2 X)$입니다. 여기서 $X$는 좌표의 범위입니다.

 

$N \neq K$일 때

(100점 풀이입니다.)

 

$N=K$일 때와 다른 점은 같은 색의 점이 있을 수 있다는 것입니다. 따라서 위 풀이와 같이 세그먼트 트리를 이용하게 되면, 같은 색의 정사각형이 두 번 더해지며 문제가 생길 수 있습니다. 이것을 해결하기 위해서, 같은 색의 정사각형을 한 번만 더할 수는 없을 지 생각해 봅시다.

 

먼저 lazy propagation plane sweeping을 하기 전에, 각 색별로 plane sweeping을 한 번씩 수행해 줄 것입니다. 여기서 정사각형의 시작 부분을 만났을 때는, 구간에 1을 더해주긴 하는데, 그 전에 원래 0이었던 부분이 어디었는지를 찾아 줍니다. 원래 0이었던 부분을 '실제로 수행할 쿼리 목록'에 넣어 줄 것입니다. 마찬가지로, 정사각형의 끝 부분을 만났을 때는, 구간에 -1을 더해주고 나서, 그 후에 0이 되는 부분을 '실제로 수행할 쿼리 목록'에 넣어줄 것입니다.

 

그렇다면 0인 부분을 어떻게 빠르게 찾을까요? 여기서 중요한 관찰은, 이런 0인 부분은 구간 하나로 나타난다는 것입니다. 만약 구간 두 개 이상이라면, 그 사이 부분의 크기가 $L$ 이하인데, 이 영역은 정사각형들의 합집합이므로 두께가 $L$ 이상이어야 해서 모순입니다. 따라서 세그먼트 트리에 아래 연산을 지원하게 하면 문제를 풀 수 있습니다.

 

• 구간의 최댓값 / 최솟값 구하기
• 구간에 1 또는 -1 더하기
• $A_x = 0$이고 $x \ge lim$인 최소 $x$ 구하기
• $A_x = 0$이고 $x \le lim$인 최대 $x$ 구하기

위 연산은 모두 로그 시간에 처리할 수 있고, 따라서 문제는 $O(N \log ^2 X)$ 시간에 풀립니다.

 

03:00 ~ 03:35

3번을 풀고 4번의 오류를 고치기 시작했습니다. 다행히도, 전에는 보이지 않았던 몇 가지 논리적 허점이 보였습니다. 이를 수정하자, 100점을 받았습니다.

 

 

일단 가장 쉬운 관찰은 다음과 같습니다. 로봇은 오른쪽으로 센서를 옮길 때에는 그냥 오른쪽으로만 가면 되지만, 왼쪽으로 센서를 옮길 때에는 되돌아가야 합니다. 따라서 되돌아가는 거리를 최소화하는 방법을 찾아야 합니다.

 

변수 세 개를 관리합니다. 세 개는 각각 lim, max-lim, at-least입니다. 왼쪽에서부터 차례대로 센서를 보면서 아래와 같이 처리합시다. $i$번 센서로 넘어갈 때 세 변수의 의미는 각각 다음과 같습니다. $a_i$는 $i$번째 센서의 초기 위치이고, $b_i$는 이후에 설명하겠습니다.

• lim은 센서가 0부터 cover할 수 있는 최대 범위를 말합니다. 즉, $i-1$번 센서까지로 $[0, lim]$의 범위를 덮을 수 있습니다.
• max-lim은 $i-1$번까지의 센서를 최대한 오른쪽으로 옮겼을 때 cover할 수 있는 최대 범위로, $2r(i-1)$과 같습니다. max-lim은 항상 $2r$씩 늘어나므로, 이 값의 변화에 대해서는 밑에 굳이 다루지 않겠습니다.
• at-least는 로봇이 모종의 사유로 오른쪽으로 이동해야 하는 최대 위치를 말합니다. 어떤 센서를 오른쪽으로 옮겨야 하는 경우 등이 포함됩니다.

1. $a_i \le lim+r$
   이 경우에는 당장은 $i$번 센서를 움직이지 않아도 되므로, $lim=a_i+r$로 바꿔 줍니다.
2. $lim+r < a_i \le maxlim+r$
   이 경우에는 $i-1$번 이하의 센서들을 적절히 오른쪽으로 움직여서 덮어줄 수 있으므로, $lim=a_i+r$, $atleast=a_i-2r$로 바꿔 줍니다.
3. $a_i > maxlim + r$
   이 경우에는 $i-1$번 이하의 센서들을 오른쪽으로 움직여줄 뿐만 아니라 $i$번 센서도 왼쪽으로 옮겨 줘야 하므로, $b_i=maxlim+r$, $atleast=a_i$, $lim=b_i+r$로 바꿔 줍니다.

 

눈치채셨을지도 모르겠지만, $b_i$는 (정의된 $i$에 대해서) $i$번 센서를 나중에 옮겨줘야 하는 위치입니다. 따라서, 기본적으로는 0에서 출발해 $atleast$까지 가되, $a_i$에 있는 센서 몇 개를 $b_i$로 옮겨 주는 상황이 됩니다. 이때 $b_i < a_i$입니다. 여기서 $(a_i, b_i)$ 쌍을 구간 $[b_i, a_i]$로 생각하기로 합시다.

 

겹치는 구간들은 하나로 합쳐 주는 것이 항상 최적이라는 사실을 쉽게 보일 수 있습니다. 또 편의를 위해 $atleast$에 구간 $[atleast, atleast]$를 하나 더 만들어 주게 된다면, 아래와 같은 그림이 만들어집니다.

 

화살표는 구간을 나타냅니다.

 

여기서 최적해는 아래 초록 선과 같은 형태라는 것을 쉽게 보일 수 있습니다.

 

따라서, 마지막에 끝나는 점은 각 구간의 왼쪽 끝점 중 하나일 것이고, 이 점으로 가능한 곳을 모두 단순하게 시도하면 $O(N^2)$ 풀이가, 조금 머리를 써서 처리하면 $O(N)$ 풀이가 완성되며 문제를 풀 수 있습니다.

 

3:35 ~ 4:00

제가 이 시간에 무엇을 했는지는 코치님들과의 비밀로 간직하겠습니다.

 

대회 총평

문제 난이도는 다른 해보다 많이 쉬웠습니다. 특히 4번 난이도가 매우 쉬웠기 때문에 400점이 꽤 나올 것이라고 예상했습니다. 이와 별개로 3번 구현이 상당히 복잡해 시간이 많이 걸렸던 것 같습니다. 문제들이 대체적으로 코드포스에 나올 법한 느낌이었던 것 같아 OI라는 느낌은 조금 적었고, 좀 더 재밌었던 것 같습니다.