문제의 지문을 공개하면 안 되기 때문에 풀이가 다소 빈약할 수 있습니다.
예선
공지도 없이 대회 시작이 10분 지연된 것 빼고는 문제 난이도 분포도 괜찮고 재미있었습니다.
1번 문제는 잘 생각해보면 제가 작년 동아리 주최 대회에 출제했던 문제(링크)와 똑같은 문제로 바뀌게 됩니다.
1번은 누적합/변홧값 배열을 아는 사람들은 5분 안에 풀 수 있는 문제입니다. 2분만에 풀고 다음 문제로 넘어갔습니다.
2번도 어려운 문제는 아닌데 처음에 이 문제가 생각나서 시간이 조금 지체되었습니다. Ladder Game처럼 어려운 문제는 아니고, 간단한 관찰을 통해 풀 수 있는 문제입니다.
inversion의 관점에서 바라본 풀이와 DFS/BFS+이분탐색을 이용한 풀이가 있는 것으로 아는데, 저는 BFS+이분탐색으로 풀었습니다. 구현에 시간이 조금 걸려서 대회 시작 후 25분쯤에 풀었습니다.
적절히 쉬운 문제 2개라서 본선 컷이 125점 정도(1번 100점 + 2번 Naive 풀이 25점) 될 줄 알았는데, 실제로는 80점대인 것 같네요.
본선
1번은 쉬운 문제, 2번도 본선 치고는 쉬운 문제였습니다.
대회 참가자 중 코포 퍼플, 오렌지인 사람만 3~4명정도 될텐데, 그런 사람들이 풀기에는 쉬운 문제인 것 같습니다.
1번은 예전 KOI 지역 대회 문제(링크)와 매우 비슷한데 입출력 형식과 입력 범위 제한이 조금 다른 문제입니다. 2번 문제는 제가 작년 동아리 주최 대회에 출제했던 또 다른 문제(링크)와 비슷한 문제입니다.
1번은 정점 개수가 최대 10,000이라서 $O(N^2)$보다 빠른 풀이를 작성했으나 구현 실수때문에 WA를 받았습니다. 이후 $O(N^2)$ 풀이를 작성해서 제출했는데 100점이 나왔습니다. 대회 시작 후 18분 정도였습니다.
2번은 문제 해석이 가장 어려웠습니다. 3번정도 잘못 읽었는데, 잘못 읽은 문제대로 풀 때마다 예제는 잘 나와서 멘탈이 약간 흔들렸습니다.
저는 Union-Find + small to large + 누적합으로 풀었는데, small to large랑 누적합은 굳이 안 써도 되는 것 같습니다. 저는 잘못 읽은 문제의 코드를 재활용하기 위해서 조금 돌아간 것 같습니다. 38분 쯤에 200점을 받았습니다.
문제 난이도 예상 (solved.ac 기준)
- 예선 1번 : 골드 4~5
- 예선 2번 : 골드 1 ~ 플레 5
- 본선 1번 : 골드 3
- 본선 2번 : 골드 1 ~ 플레 4
마무리/아무말
끝나고 나와서 일찍 나오는 사람들을 세어봤는데, 제 앞에 30분, 33분 만점자가 있어서 3~4등정도 할 것 같습니다.
1등 노리고 갔는데 조금 아쉽네요.
작년에 개최한 동아리 대회(UniCon)는 좋은 대회였다는 것이 이렇게 증명되네요.
올해도 동아리 대회를 열 수 있을지는 잘 모르겠네요. 좋은 문제가 있으면 동아리 대회보다는 연말에 BOJ에서 개최할 예정인 Good Bye, BOJ 2020에 출제할 가능성이 높습니다…
수정) 결과 나왔습니다. 3등입니다.
- 1등 200점/30분
- 2등 200점/33분
- 3등 200점/38분
- 4등 200점/68분
- 5등 ?
- 6등 ?
- 7등 200점/75분
인 것 같네요.