0. 서론
KOI 2021을 봤다. 작년에는 전형료가 엄청나게 비싸진 것도 있고 IOI 일정과도 겹쳐서 응시를 안했다. 근데 끝나고 문제들을 들어보니 다 너무 쉽게 풀렸다. 쳤으면 400점이 나왔을 거 같아서 올해는 억울해서 응시를 했다. 딱히 준비를 하지는 않았지만 일단 목표는 올솔이었다. IOI를 기점으로 폼도 엄청나게 떨어지고 (IOI 후기도 빨리 써야겠다.) 공부도 안해서 가능할 리가 없었지만 아무튼 목표는 올솔이었다...ㅋㅋ
1. 시작 전
대회 시작 1시간 전에 줌 고사실로 입실해서 이것저것 검사를 받았다. 온라인으로 대회를 여러번 진행하더니 이제는 부정행위 감시도 굉장히 철저해지고 체계적이게 된 것 같았다. 이 부분은 참 좋았다. 다만 감독기기 (== 핸드폰)을 후면카메라로 바꿔서 들고 주변을 찍으라는 부분은 쉽지 않았다. 핸드폰 충전이 마땅치 않아서 책 여러 개를 깔고 노트북을 올려서 썼는데 노트북을 앞으로 들고 화면을 안보면서 찍으려니 쉽진 않았다. 사실 별로 중요한 얘기는 아니고 그냥 생각이 났다. 선발고사 때는 안그랬는데ㅋㅋ
중요한 얘기는 화장실 이야기이다. 오프라인이야 진행요원이 따라가서 화장실을 자유롭게 갔다오지만 온라인은 화장실에 폰을 두고 검색할 수도 있으니 확실히 중요한 문제였다. 선발때는 그런 제한이 없었는데 이번에는 이용횟수 1회, 시작하고 1시간 뒤부터 갈 수 있다는 제한이 있었다. 사실 나는 대회 때 화장실을 정말 자주 간다. 이런 류의 대회를 칠 때는 물을 끊임없이 마시고 그만큼 화장실도 많이 가는데 1회라는 이야기를 듣고 불안감이 엄습했다. 전략적으로(?) 화장실을 가지 않으면 큰일이 나겠구나. 근데 그 얘기를 듣기전에 이미 물을 두 컵은 마셨던 것 같다. 아ㅋㅋ 결국 이게 대회에 영향을 크게 줬다.
2. 그래프
시작하고 바로 1번 문제를 찬찬히 읽었다. 경우의 수 문제고 색깔이 있고 1+2+3+... 이라 아무튼 시복은 루트겠다. 근데 거기까지 바로 생각은 나는데 쿼리도 있고 시간이 빡세보인다. 근데 Q=1이 90점? 엄.... 뭔가 DP 하나로 전처리 해놓고 a, b에 따라 부분적으로 테이블의 합을 구하겠구나... 까지 생각하고 말릴것 같아서 일단 다 문제를 읽기로 했다.
2번 문제를 읽었다. 그래프 문제가 나왔는데... 그런데 어디선 많이 본 문제가 나왔다. 그냥 BOI 2020 graph가 확장된 형태로 나왔다. 물론 풀이의 틀은 전혀 달라지지 않는다. 1번 정점을 x라고 하면 간선을 지나면서 모든 정점의 값을 a+x 또는 a-x 꼴로 표현해줄 수 있다. 어떤 정점들에서는 저 두 조건이 동시에 나타나서 (홀수 사이클이 있다면 아마 그렇게 만날 것이다.) x가 결정된다. 불가능한 경우도 쉽게 처리되고 x를 우리가 결정해야하는 경우는 결국 |x - a|의 합 꼴이 되니까 중간값을 뽑으면 된다. 머리를 비우고 편안하게 구현해서 한 번에 맞았다.
3. 페인트 통
다시 1번으로 돌아가려고 하는데... 이미 본능이 화장실을 외치고 있었다. 진짜 사고가 나고 말았다. 1시간까지는 한참 남았는데... 걍 답이 없었다. 참아야 했고 고통스러웠지만 결국은 버텼다. 그런 상황이 되니까 사람이 집중이 안 되는 것도 있는데 의외의 효과(?)로 사람이 그냥 급해졌다. 그래서 1번을 조급한 마음과 함께 다시 잡았다.
차근차근 생각해보니 일단 루트는 확실했고 DP도 안 어려웠다. D[i][j] = i 동심원을 j 빨간색으로 칠하는 경우의 수로 생각하면 그냥 쉬웠다. 저렇게 하면 두 개의 인자에 파란색의 양에 대한 정보가 포함되어 있다. a b로 주어지는 쿼리도 그냥 쿼리당 루트로 각 줄마다 구간 합 계산이니 누적합으로 어렵지 않게 할 수 있었다. 한 번에 AC.
개인적으로 정말 좋은 문제라고 생각했다. 문제를 보고 어려운 문제들에서 감탄하는 경우는 많았는데 최근들어 송년 문제 준비를 시작해 고민이 많아 그런지 너무 식상하지 않으면서도 깔끔한 문제라는 생각이 들었다. 고등부 1번으로는 조금 어려웠던 것 같다는 감이 있는 것도 같다. 내 기준에서는 확실히 2 < 1인듯. 루트 아이디어나 DP나 이런 부분들이 엄청나게 참신하지는 않아도 깔끔하게 잘 섞인 것 같다.
4. 괄호 문자열
여기까지 하니까 대충 30~40분정도 지나갔다. 화장실까지 20분이 남았다는 말이다. 정말 정신이 혼미했다. 그 시간동안 3번 4번 문제를 모두 읽고 생각을 해보려 했다. 근데 구체적인 생각을 하려고 하니까 그냥 머리가 아예 안 돌아갔다. 거기다 문제들도 3번은 누가봐도 Suffix Array가 정해이게 생긴 문자열 문제고 4번은 트리 위에 원이 올라가 있었다. 뭐 적당히 센트로이드거나 무지성 세그 큰-작 트리 DP 둘 중 하나겠거니 했다... 대충 (힘겹게) 생각을 정리하고 시간을 보니 5분이 남았다. 그때부터는 그냥 정신을 놓고 30초 남았을 때 감독관님한테 다녀와도 되냐고 묻고 빛의 속도로 다녀왔다.
정신이 갑자기 맑아졌다. 문제들 견적을 다시보니 3번은 LCP 쓰는게 맞는 것 같았고 4번은 세그 큰작이 맞는 것 같았다. 근데 SA를 한 번도 짜본 적이 없어서 그냥 큰일 났다는 생각 밖에 안 났다. 원리야 알고 있지만 문자열은 좀... 애초에 OI 준비에서 문자열을 볼거라고는 생각도 안했다. 사실 작년 선발고사에서 KMP로 이미 한 번 통수를 맞았으니 두 번 당한건 그냥 안일했던 것 같다. 근데 생각해보니 이번 KOI도 그렇고 선발고사도 그렇고 결국은 잘 풀었으니 뭐 그걸로 된 것 같다.
조금 생각을 해보니 해싱을 박아도 될 것 같았다. 괄호가 아닌 버전의 최장 공통 부분 문자열을 푸는 방법을 1. LCP Array 사용하기와 2. 라빈-카프 해싱 + 파라메트릭의 두 가지로 알고 있었다. 여기서도 후자의 풀이가 될 지 고민해봤다. 일단 괄호 문자열 문제니까 산부터 그렸다. 이 글을 읽는 사람들 중 모르는 사람들이 있다면 알아두자. 괄호 문자열에서 (를 1, )를 -1로 생각하면 올바른 괄호 문자열이라는 것은 전체 합이 0이고 앞에서부터의 누적 합이 항상 음이 아니라는 것과 동치이다. 따라서 이 누적합을 앞에서부터 오르락 내리락하는 산으로 그리면 생각하기 편하다.
괄호열에서 올바른 부분 문자열이란 산의 한 부분을 잘라서 왼쪽 끝과 오른쪽 끝의 높이가 같고, 중간의 점들이 그 높이 밑으로 내려가지 않게 만든 것이다. 다시 정리하면 1. 같은 높이의 여는 괄호와 닫는 괄호를 뽑아서 2. 그 사이에 끝점보다 아래로 내려가는 부분이 없게 만들면 되는 것이다. 이제 이 관찰을 이용해서 구간의 왼쪽 끝을 정하면 그에 올바르게 대응 되는 오른쪽 끝들을 쉽게 찾을 수 있다. 앞에서부터 훑으면서 같은 높이의 괄호들에 같은 그룹 번호를 붙여 표시한다. 동시에 닫는 괄호들은 그룹별로 벡터에 넣어 순서대로 위치를 저장한다. 그러다가 산이 하강하면 원래 높이에 있던 그룹을 닫고 같은 높이에서 새로운 그룹을 시작한다. 그 오른쪽에 있는 괄호는 2번 조건이 만족하지 않아 왼쪽과 매칭될수 없다. 따라서 다른 그룹으로 쪼개는 것이다. 이제 왼쪽 괄호를 정하면 그 괄호가 속한 그룹의 벡터의 닫는 괄호들이 곧 대응 가능한 오른쪽 끝이다.
이제 파라메트릭을 해보자. 길이 K 이상인 올바른 공통 괄호열이 있을까? 라는 질문에 답하려면 각 위치를 왼쪽 끝점으로 할 때 만들 수 있는 올바른 괄호열 중 길이가 K이상인 가장 작은 오른쪽 끝점을 가져오면 된다. 다른 문자열에도 그 길이 이상의 같은 괄호열이 있다면 정확히 같은 문자열을 가져올테니. 따라서 위치마다 많아야 1개씩 문자열을 가져오니 한 번의 시행에서 O(N)개를 가져오고 두 집합에서 공통원소가 있는지를 판별하는 것은 해싱을 하고 해시값을 정렬하면 O(N log N)에 끝이다. 부분 문자열의 해시값은 그냥 누적합과 진수의 거듭제곱값을 전처리해두면 O(1)에 계산된다. 따라서 최종 시간복잡도 O(N log^2 N)에 풀린다.
짜서 제출을 했더니 마지막 서브태스크에서 WA가 나왔다. 해시를 썼으니 뭐 그럴 수 있겠다고 생각했다. 앞의 섭태를 다 맞은걸 보면 코드는 맞았다. 해시를 안 뚫리려면 그냥 이중 해싱을 하면 된다. 그래서 진수랑 MOD값을 바꿔서 한 5번 제출해놓고 이중해싱으로 고치기 시작했다. 1분 제출제한이 없어서 좋았다. 근데 짜고 있었더니 그냥 17진수 + MOD 10억 9였나에서 AC를 받았다. 100점 받은걸 보고 짜던걸 그대로 던지고 4번으로 갔다. 뭔가 뚫은 느낌이라 기분이 좋았다.
5. 맛집 추천
결국 트리류의 특수한 그래프에서의 가중치 있는 최대 독립 집합이었다. 사실 그건 중요한 건 아니고. 트리 위의 원이라서 센트로이드인가? 했지만 결국 DP였다. 그냥 방역이었다. 방역을 짜면 맞았다. 2시간이 남은 상황이었고 나는 방역을 풀었다. 뭔가 데자뷰가 느껴졌다. 2019년에도 4번은 그냥 불도저를 짜면 맞았고 1시간 남기고 짜서 0점 받고 은상따리가 되었다. 그래서 일단 섭태를 긁을까 했지만 생각해보니 올해는 2시간이 남았고 반딧불이 있다. 딧불이도 방역 풀었을테니까 어차피 400 받을거 같아서 시간을 절약해서 400을 받아야 대상이 되겠다는 생각을 했다. 그래서 그냥 노빠꾸로 풀테를 짰다.
APIO에서 큰작 트리 디피 짜다가 말린 안 좋은 경험이 있었지만 (Niyaz and small degree) 정리해놓고 보니 이 문제는 엄청나게 정교한 무언가를 짤 필요는 없는 것 같았다. 그냥 레이지가 되는 맥스 세그를 들고 작은 쪽 원소들을 큰 쪽으로 잘 넘기면 된다. D[u][x]를 u 아래 서브트리의 원들을 골랐을 때 최소 깊이가 x인 최대 합으로 정의하고 전처리로 각 세그에 들어갈 깊이의 종류를 저장해 좌표압축하고 세그를 만들어서 그대로 올리면 구현도 나름 아름답게 되는 것 같았다. 그래서 그대로 짰고 다 짜고도 50분인가가 남았다. 아 400 되겠구나 싶어서 디버깅을 그냥 들어갔다.
그런데 엥? 컴파일 에러 5개 정도를 고치고 돌렸더니 런타임 에러가 났다. 뭐 런타임 에러야 그냥 고치면 된다. 근데 테스트 환경이 이상하다. 런타임에러가 났는데 그 이전의 출력 결과를 안 보여준다. 뭐지 싶어서 main함수 선언 바로 밑에 puts("???"); 를 박았는데 아무것도 안 나왔다. 사태의 심각성을 느끼고 최대한 빠르게 런타임이 날거 같은 부분들을 주석쳐서 돌리면서 찾았다. 시스템으로 원래 이런거냐고 질문도 날렸는데 끝까지 답변 못 받았다...ㅋㅋ 그리고 시간을 좀 많이 태워서 찾았더니 그냥 레이지 벡터를 리사이즈 안 한거였다. 로컬에서 돌렸으면 3분이면 찾았을 거 같은데 ㅁㄴㅇㄻㄴㅇㄹ 아무튼 좀 많이 화가 났다. 내 전형료는 어디로...
찾아서 이제 이것저것 고쳐서 냈더니 9점이 나왔다. 직선만 맞는다는걸 보고 풀이가 틀렸는지 한참 고민했는데 풀이는 맞는 것 같았다. 근데 도저히 반례도 안 보이고 틀린것 같은 부분도 안 보이더라... 그러다가 시간은 한 자리 수대로 남고 그냥 답이 없는 상황이 돼서 반딧불 우승~~ 을 외치고 멘탈이 나갔다. 섭태 긁을걸~ 솔직히 국교 3번 들으면서 섭태 긁으라는 말은 200번쯤 들은것 같지만 버릇은 쉽게 안 고쳐지는 것 같다. 사실 처음부터 올솔이 목표였으니까 아무래도 상관은 없는 것 같다. 400점이 충분히 해볼만 했던것 같아서 너무 아쉽다.
6. 대회 종료
여기저기 알아보니까 대충 금상이라는 것 같다. 400점은 없었고 딧불이도 400 받으려고 풀테 짰다가 맞왜틀 박고 터졌다고 한다. ㅋㅋ.... 결국 섭태만 긁어도 대상이었는데 2019년에 이어 또 그걸 못했다. 그래도 만점풀이 다 찾고 짰으니 처음 목표를 반은 달성한 것 같다. 2016 초등 대상 이후로 은상만 받고 코이랑은 인연은 없나 했는데 마지막 코이에서 금상이라도 받으니 만족해야 겠다. 정말 재미있었다.