https://dojoi.xyz/ko 라는 사이트에서 KOI 2차 모의고사를 출제하였다고 하여 고등부를 참가해보게 되었다. 시험 시간은 4시간 반이고, 대략적으로 14:00 - 18:30 정도의 시간을 잡고 참가하였다. (해당 모의고사는 실제 KOI와는 전혀 무관합니다.)
고등부의 문제는 이렇게 4문제였다.
[0:00 - 0:44] A. 히스토그램 (AC, 100)
이번 출제자 중 한 명인 lunarlity가 저번에 만든 히스토그램 관련 PS 문제가 NM개라고 해서 문제를 보자마자 lunarlity가 냈겠다는 생각이 들었다. 일단 X번 이하 시행으로 가능한 경우를 탐색하는 것은 굉장히 어렵기 때문에 Parametric Search를 통해 문제를 풀어야겠다는 아이디어를 낼 수 있었다.
그러면 답이 p보다 클 수 있는가?라는 판정 문제를 풀 수 있어야 한다. 하지만 이 역시 p가 가로 * 높이 꼴이라서 어렵기 때문에 가로나 높이 중 하나의 값을 고정하는 아이디어를 떠올렸다. N 범위가 7000이므로 N^2 이상의 시간복잡도가 나와도 괜찮기 때문이다. 가로를 고정할 경우 가로 길이는 고정할 수 있지만 위치를 고정하는 과정이 추가로 필요하기 때문에 높이를 고정하여 N번 탐색하는 것을 생각했다.
이렇게 되면 높이를 고정했을 때 문제를 $O(N)$ 정도에 풀 수 있어야 하는데, 내가 정한 높이보다 높은 것을 1, 낮은 것을 0으로 잡을 수 있고, p와 높이가 정해지므로 연속하게 만들어야 하는 1의 개수가 정해진다. 그러므로 1이 그 정해진 개수만큼 붙을 수 있는지 생각해보면 되고, 당연히 인접한 1들끼리 붙어야 하고, 붙는 위치는 항상 붙을 1들 중에 가장 중앙 위치에 가까운 1에 붙는 것이 이득이 됨을 쉽게 알 수 있으므로 $O(N)$에 높이를 고정했을 때의 판정 문제를 풀 수 있게 된다. 따라서 전체 시간복잡도는 $O(N^2 log N)$이다.
Python으로 $O(N^2 log N)$을 $N \le 7000$에서 돌릴 수 있느냐가 관건이었는데, 2초 제한에 1630ms로 다행히 시간 안에 돌았다. 난이도는 P3 정도인 것 같다.
[0:44 - 1:17] B. 경기장 (AC, 200)
이 문제는 트리와 관련된 문제였다. 주어진 예제에서 3을 경기장의 한 점으로 잡고, 여기서 불편도를 가장 많이 줄일 수 있는 방향으로 간선을 뻗어 경기장을 늘리는 그리디를 반복하면 정답을 얻을 수 있음을 확인하였다. 그래서 해당 그리디가 맞을 것이라고 생각하고 처음의 한 점을 어떻게 정해야 할지에 대해 고민했다.
처음의 한 점이 $X = 1$일 때의 정답일 것이라는 추론은 위 그리디가 성립한다면 꽤 자명하게 해볼 수 있다. 따라서 이 추론이 맞는지 확인하기 위해 $X = 1$ 서브태스크에 해당하는 풀이를 짜서 먼저 제출했다. 다행히 해당 섭태에서 올바른 결과가 나왔고 따라서 이 풀이에 우선순위 큐를 이용해 간선을 추가로 연결하는 부분을 구현하여 15점을 받고 3분 후 곧바로 만점을 받을 수 있었다. 최종 시간복잡도는 간단한 tree dp를 이용해 $X = 1$의 답을 찾는 과정이 $O(N)$이고 그 이후 우선순위 큐를 이용해 답을 구하는 과정이 $O(X log N)$이므로 $O(N + Xlog N)$이다.
문제 난이도는 증명에 비해 발상이 Korean Well known이라 다소 낮게 책정될 수도 있을 것 같은데, P2 정도인 것 같다.
[1:17 - 2:21] C. 중앙값 (PAC, 273)
문제를 보고 이걸 어떻게 풀지 생각이 들어 차분히 서브태스크를 보기로 했다. 2점짜리 서브태스크 3개는 정말 쉽고 바로 구현해서 낼 수 있는 부분이라 4, 5, 6번 서브태스크에 해당하는 $N = 2K+1$을 집중적으로 고민했다. 최종적으로 남게 되는 답은 정확히 하나이므로 이 값이 얼마일지 알아야 하는데, 이것조차 잘 모르겠어서 먼저 $N =2K+1$이고 $A_{i} \le 2$인 섭태 4부터 생각하기로 했다. $A_{i}$의 값은 1이나 2만 가능하고, 예제 몇 개를 손으로 해보다 보니 인접한 두 수가 같으면 이 값이 계속해서 끝까지 유지되는 것을 관찰할 수 있었다. 그리고 그렇지 않다면 1과 2가 번갈아 가며 등장해야 하는데 이 경우는 1, 2, 1, 2, ...이 2, 1, 2, 1, ... 으로 뒤집힌다.
그래서 결국 인접한 두 수의 쌍 중 중앙과 가장 가까운 것을 찾으면 되는 문제가 되고 이걸 조금 응용하면 A와 마찬가지로 p보다 작으면 0, p보다 크면 1로 바꾸어서 parametric search를 할 수 있게 된다. 따라서 $N = 2K+1$을 온전히 풀 수 있게 된다. 그래서 46점을 받았다.
문제를 더 못 풀 수도 있겠다는 생각이 들어 일단 쉬운 서브태스크인 1, 2, 3점을 긁고 52점을 확보하였다. 그리고 뒤이은 섭태를 조금 더 고민하다가 $A_i \le 2$ 서브태스크를 위에서의 아이디어를 비슷하게 이용해서 풀 수 있다는 생각이 들었다. 그리고 이걸 활용해서 0과 1을 구분하는 기준을 2, 3, 4, 5... 10으로 바꾸어 가며 10번 연산하면 $A_i \le 10$까지 풀 수 있겠다는 생각이 들어 이걸 구현했고 총 73점을 받을 수 있었다. 그리고 풀태를 풀지 못할 것 같아 D로 넘어갔다.
[2:21 - 4:07] D. 지우기 (PAC, 297)
문제를 읽자마자 굉장히 어렵겠다는 생각이 들었다. $l_1, r_1, l_2, r_2$가 동작하는 방식이 굉장히 까다로웠다. 일단 왼쪽 끝과 오른쪽 끝이 정해지면 값이 정해지므로 dp[l][r]을 l ~ r 구간의 f 함숫값으로 정의하면 $O(N^2)$ 사이즈의 테이블을 만들 수 있다. 그리고 여기에 Segtree를 이용해서 구간 max를 관리하면 $O(N^2 + QN log N)$에 문제가 해결된다. 몇 번의 구현 실수가 있었지만 이를 통해서 섭태 1과 2를 맞힐 수 있었다.
섭태 3의 경우 모든 값이 다르면 f 함수를 취할 때 지울 수 있는 값이 없으므로 구간의 길이를 각각 최소화, 최대화하는 방법만 생각하여 구현하면 되는 간단한 서브태스크였다.
그리고 다양한 섭태를 보다가 그나마 섭태 5가 $l_1 = r_1, l_2 = r_2$가 성립하므로 비교적 간단헤 보였다. 오프라인 쿼리 중 mo's를 이용해서 쿼리 순서를 바꾸면 문제가 $O(N \sqrt{N} + Q)$에 풀리기 때문에 12점을 획득할 수 있어서 최종적으로 24점을 얻었다. 이 문제를 풀던 도중 채점 서버에 오류가 발생했는데, 이미 문제를 풀 수 있는 만큼 대부분 푼 대회 후반부라서 그나마 다행이었던 듯하다.
이렇게 4시간 반에 걸친 KOI MOCK을 마쳤고, unrated 참가자 포함 6위를 기록하며 레이팅 238점을 벌게 되었다. 문제 퀄리티가 전반적으로 높았던 것 같다. 그러나 1번과 3번이 공통적으로 파라매트릭 서치를 공통적인 아이디어로 쓰는 등 상당히 유사한 문제 같다는 생각이 들기도 해서 이 부분은 조금 아쉬웠다.
그래도 4시간 반 동안 재밌게 풀어볼 수 있는 문제를 마련해준 운영 및 출제진 분들께 감사의 말씀을 드린다.
'PS' 카테고리의 다른 글
| 2026 SCSC 프로그래밍 경시대회 Div. 1 후기 (1) | 2026.05.18 |
|---|---|
| 2026 Kaist Run Spring Contest 후기 (1) | 2026.05.05 |
| PS 문자열 알고리즘 - 8. 1D Trie 구현 (4) | 2025.08.13 |
| PS 문자열 알고리즘 - 7. 접미사 배열과 lcp 배열 응용 (0) | 2025.08.12 |
| PS 문자열 알고리즘 - 6. 접미사 배열과 lcp 배열 (0) | 2025.08.12 |