KOI 2021 고등부 후기

오늘 고등부 KOI 2차 대회가 있었습니다. 시험을 보기 전엔 은 중상위권 정도만 했으면 좋겠다고 생각했는데, 점수가 생각보다 잘 나와서 기분이 좋네요.

 

0:00 ~ 0:20

일단 1번을 열었는데, 1번이 생각보다 어려웠습니다. 가능한 동심원 크기의 최댓값은 루트(N)에 비례한다는 사실과, dp 전처리를 잘 섞으면 O(N루트N) 정도에 풀 수 있습니다. (N = A+B)

 

0:20 ~ 0:57

어려웠던 1번과 달리, 2번은 풀이가 바로 보였습니다. 1번 정점의 가중치를 x라고 두면 dfs를 돌면서 나머지 정점들의 가중치를 x에 대한 식으로 나타낼 수 있고, 이분그래프가 아닌 케이스들만 처리를 해주면 쉽게 해결이 가능합니다.

이분그래프인 경우, x의 값을 마음대로 설정할 수 있는데, 최솟값을 찾기 위해 저는 삼분탐색을 사용했습니다. 슬로프의 기울기를 관리하는 방식으로도 쉽게 풀 수 있다고 합니다.

 

0:57 ~ 1:35

3번을 열어봤는데, 제곱 풀이도 잘 보이지가 않았습니다. 대충 감은 잡히는데 풀이가 구체화되지 않아서 일단 4번으로 넘어갔습니다. 4번에서 섭태 1은 간단한 dp를 짜면 쉽게 풀 수 있고, 빠르게 섭태 1을 긁어 9점을 받았습니다.

 

1:35 ~ 1:55

다시 3번으로 돌아와서 간단한 세제곱 풀이를 짰고, 18점을 받았습니다. 세제곱 풀이를 약간의 전처리를 통해 제곱으로 바꿀 수 있어서 제곱으로 바꾼 후, 41점을 받았습니다.

 

1:55 ~ 2:10

3번에서 A=B인 섭태는 유효한 괄호 문자열의 최장길이를 찾기만 하면 되는 섭태였고, 이는 segment tree와 dp로 쉽게 풀 수 있었습니다. dp[i] = (i번째 괄호로 끝나는 가장 긴 괄호 문자열의 길이)로 놓으면 O(NlogN)에 문제를 풀 수 있습니다.

 

2:10 ~ 3:31

3번 100점 풀이를 고민해봤지만 잘 떠오르지 않았고, 아직 4번 문제의 섭태들을 다 긁지 않아서 일단 4번 문제를 긁기로 정했습니다. 4번 섭태 1을 풀면서 생각해뒀던 O(N(N+M)) tree dp를 짰는데 TLE가 났고, 알고보니 N이 하나 더 붙었습니다. 약간 변형해서 N을 떼고 제출을 했더니 47점이 되었습니다. (M<=100000, N<=2000이라 N(N+M))으로 짜도 TLE가 나지 않았던 것 같습니다.)

 

참고로 제가 짰던 tree dp는 다음과 같습니다.

dp[s][h] = ((s의 깊이 - (배달 가능한 점의 최소깊이)) <= h를 만족하도록 서브트리 s에서만 점들을 골랐을 때, 점들의 가중치 합의 최댓값)

h<0인 경우는 그냥 dfs로 서브트리에 h+1을 계산하도록 넘겨주면 되고, h>=0인 경우는 dfs 함수가 한번 호출 되었을 때, 0<=h<=n일때의 dp값을 O(N*d(s))에 계산하도록 잘 처리해주면 O(N(N+M))에 풀 수 있습니다.

 

다시 3번으로 넘어가려고 했는데 4번의 섭태 5를 보니 완전이진트리라는 조건이 있었고, 트리의 높이가 O(logN)이기 때문에 위에서 짰던 tree dp에서 h의 범위만 로그로 바꿔주면 된다는 것을 확인했습니다. 그래서 8점을 추가로 긁었습니다.

 

3:31 ~ 4:24

3번 100점을 노리려고 했지만 1시간 정도 밖에 남지 않아 풀 수 있다는 확신이 없었고, 4번의 섭태 6 풀이가 바로 보여서 일단 섭태 6을 긁기로 했습니다.

 

차수가 3 이상인 점을 고정해놓으면 스타그래프처럼 생겼다는 것을 확인할 수 있습니다. 그래서 중심점을 제거했을 때 생기는 일직선 그래프들 각각에 대해 섭태 1처럼 dp를 돌려주고, dp값을 가지고 잘 계산하면 답을 구할 수 있습니다.

 

구현하면서 dp 배열의 정의를 자꾸 착각하고 범위를 잘못 확인해서 계속 RTE와 WA가 났고, 30분 넘게 디버깅을 하다가 겨우 버그를 다 고치고 4:24에 12점을 더 긁었습니다. 디버깅 중간에 멘탈이 나갈뻔 했지만 포기하지 않고 계속 디버깅을 한 결과 다행히 부분점수를 더 받을 수 있었습니다.

 

대회가 끝나고

3번과 4번 섭태들을 긁기 쉬워서 당연히 대부분 300점 이상을 받았을거라고 예상을 했지만, 지인들과 점수를 비교해본 결과 제 점수가 거의 최상위권이라는 사실을 알게 되었습니다. 운이 되게 좋았던 것 같았고, 앞으로도 더 열심히 공부해서 다른 대회에서도 좋은 성과를 낼 수 있도록 노력하겠습니다.

 

추가) 대상 받았네요 ㅎㅎ