KOI 2023 중등부 2차 후기

대회 준비

영재고 2차 시험과 정보올림피아드 2차 시험이 6일차이나는 바람에 정보올림피아드 준비를 할 시간이 부족했다.

그래서 영재고 2차 시험이 끝난 다음날부터 미친듯이 정보를 공부했고, 준비했던 기간이 매우 짧았던 만큼 더 집중도 있게 공부할 수 있었다.

준비했던 방법은 그냥 우사코 골드 문제를 계속 풀었다.

우사코 골드 정도의 문제가 골드 상위 ~ 플래티넘 중하위 정도의 문제가 섞여있어 연습하기 적절했다.

대회 직전

벌써 3년째 치루는 온라인 시험이기 때문에, 화장실 시간 분배가 매우 중요하다는 사실을 깨달았다..

대회 시작 전에는 최대한 물을 마시지 않았고, 방에 물을 2병만 들고 갔다. (그마저도 결국 후회하긴 했지만...)

KOI는 매번 온라인 시험 때 줌을 사용했는데, 다른 참가자들 때문에 불편했던 적이 있었다.

이를 방지하기 위해 포커스 모드를 사용하기 시작한 것 같은데, 어차피 소리는 다 들려서 큰 의미는 없었다.

나는 최대한 집중하기 위해 감독관님의 소리만 들릴 정도로 핸드폰 볼륨을 낮춰 놓았다.

1. 스케이트 연습

시작하자마자 스케이트 연습 문제를 열었다.

문제를 너무 대충 읽은 탓에 예제를 이해 못할 뻔 했다.

이상한 뻘짓을 조금 하다가 뒤에서부터 훑으면 되겠다는 생각이 들었고, 문제를 해결했다.

문제를 해결하는 과정에서 실행과 제출이 너무 오래 걸려 살짝 짜증났다.

제출은 그렇다 쳐도, 실행이 오래 걸리는 것은 선을 넘었다.(나중에는 고쳐진 듯 하다.)

2. 호숫가의 개미굴

1번 문제를 약 10분만에 해결하고 2번 문제를 열었다.

1번과 N번이 중복되면 안된다는 사실을 제외하면 DP로 간단하게 해결할 수 있을 것 같았다.

1번과 N번이 중복된다는 조건을 적용하기 위해 1번의 값을 적용한다는 아이디어는 전에 한 번 본 적이 있었기에, 바로 구현을 시작했다.

테스트를 실행시켰는데 컴파일 에러가 났는데, 아무런 설명 메시지가 없어 당황했지만, 다시 실행해보니 잘 됐다.(버그였던 것 같다.)

구현을 끝마치고 제출하니 7번 테스트 케이스( $C_i \le 1$ )만 정답이고 나머지는 모두 틀렸다.

코드를 다시 살펴보니 0을 1로 쓴 실수가 있었고, 이를 고치자 정답이 나왔다.

3. 고기 파티

2번 문제를 약 10분만에 해결하고 3번 문제를 열었다.

문제를 읽으니 뭔가 범위가 나오는 것이 자료구조 느낌이 났다.

사람 관점에서 고기를 먹으려면 힘들었지만, 고기 관점에서 사람에게 먹히는 것은 그렇게 어렵지 않다는 관찰을 했고, 세그먼트 트리를 통해 꼬치의 위치에 사람의 번호를 업데이트하고 고기의 범위에서 최솟값을 방법을 생각해냈다.

내가 가장 자신 있는 세그먼트 트리였기 때문에 나는 매우 빠르게 구현했고, 뜻밖에도 바로 만점이 나왔다.

4. 지그 재그

3번 문제를 생각보다 빠르게 풀어 아직 시간은 4시간 정도 남았었다.

나는 천천히 4번 문제를 섭태 하나씩 풀 생각으로 문제를 읽었다.

지그 재그라는 아이디어는 전에도 한 번 생각해본 적이 있는 주제였는데, 이걸 문제로 접하니 반가웠다.

문제는 풀이를 전혀 모르겠다는 것...

대충 DP와 세그트리를 사용한 $O(N^3logN)$ 풀이를 떠올렸고, 바로 구현하니 23점이 나왔다.

세그트리 구현에 살짝 실수가 있어서 30분 정도 걸렸다.

다른 부분문제를 보니 logN이 붙는 정도의 숫자가 아닌 것을 파악했고, log를 뗄 방법에 대해 고민했다.

DP와 세그트리를 합친 방법에서는 아무리 생각해봐도 개선하는 방법이 생각나지 않았고, 다른 방법을 고민했다.

이 때 나에게 떠오른 것은 LIS였다.

LIS를 $O(NlogN)$에 구할 때도 세그트리를 사용한 방법이 있지만, 벡터를 사용하는 방법도 있었다.

나는 이 점에서 착안해 $O(N^3)$의 복잡도로 벡터에 하나씩 넣으면서 관리하는 방법을 알아냈고, 바로 구현해 40점을 받았다.

다음 부분문제는 $N \le 5000$였고, $O(N^3)$에서 N을 하나 떼면 되겠다는 생각이 들었다.

N 3개는 각각 x, y, z 때문에 생기는 것인데, z는 아무리 봐도 뗄 수 없을 것 같았다.

x와 y를 떼려는 다양한 노력 끝에, 만만해 보였던 x는 생각보다 제거가 어려웠고, y를 제거하는 방법을 생각해냈다.

각 x에 대해 y=1일 때를 먼저 구하고, 왼쪽부터 하나씩 제거해나가면서 값을 더해가는 방식을 고안했는데, x 때문에 고려하지 않아야 하는 값들이 있어서 구현이 조금 까다로웠다.

그래도 생각보다 금방 구현에 성공했고, 62점을 받아낼 수 있었다.

이 때까지의 시간이 2시간 11분이었고, 나에게는 마지막 부분문제를 해결할 시간이 2시간 19분이 있었다.

ㅎㅎ;

나머지 시간 동안 4번 문제를 결국 해결하지 못했다.

세그트리랑 와리가리 열심히 하면 될 것 같긴 했는데, 내 머리가 따라가질 못했다. (사실 풀기 싫었던 것도 있었다.)

결국 남은 시간동안 화장실을 참으며 그냥 있었다. 중도퇴실할까 심각하게 고민했지만, 그냥 멍때리고 있었다.

대회 종료 후

지그 재그 풀이는 끝나고 생각해봐도 잘 모르겠다. 아직 실력이 부족한 것 같다...

NYPC 전까지 또 정보를 열심히 파야겠다.

아무리 봐도 고기 파티는 플래티넘 4 정도 되는 것 같은데, 많은 사람들이 플래 2~3에 기여하는 바람에 플래 3에 기여했다.

고기 파티와 지그 재그가 같은 티어인 것은 좀 아닌 것 같다.

결과

362점, 최종 점수를 받은 시간 2시간 11분으로 대회가 마무리되었다.

최종 등수는 1등(대상)이다. ㅎ