2025 IOI 국가대표 선발고사 후기

1/18, 2/22에 2025 국제정보올림피아드 국가대표 선발고사에 응시했다.

1차 400점(1위) + 2차 214.62점(2위)로 종합 2등으로 국가대표에 선발되었다.

작년에는 국가대표 후보로 선발되어 국가대표 교육에만 참여하고 IOI에는 참여하지 못했는데, 올해는 IOI에 참가할 수 있게 되어 기쁘다.

IOI에 나가서 좋은 성적을 거두고 싶다.

1/18 1차 선발고사 후기

올해에는 꼭 국가대표가 되어야 하겠다는 신념으로 시험에 응시했다.

0:00 ~ 0:10 (0 / 0 / 0 / 0 = 0)

문제를 모두 읽고 섭테 배점과 조건을 종이에 정리했다.

0:10 ~ 0:34 (0 / 0 / 100 / 0 = 100)

아무리 봐도 3번이 쉬워 보여서 3번을 먼저 시도했다.

오래 걸리지 않아 간단한 O(N) DP 식을 세웠고, 구현해서 맞았다.

0:34 ~ 1:10 (47 / 0 / 100 / 0 = 147)

그다음으로는 투스텝 문제인 1번 문제를 생각해보기로 했다.

몇 가지 경우를 시도해보다 보니 47점 풀이를 떠올리는 것에 성공했고, 구현해서 맞았다.

1:10 ~ 1:28 (47 / 45 / 100 / 0 = 192)

2번 문제가 내가 제대로 이해한 것인지 확인하고, 섭테 점수를 얻고자 섭테 구현을 시작했다.

N이 작은 경우와 트리가 일자인 경우에 대해 각각 구현해서 맞았다.

1:28 ~ 1:53(47 / 100 / 100 / 0 = 247)

2번 문제의 섭테 풀이를 확장해 전체 풀이를 알아냈다.

쿼리 부분을 HLD를 이용해 빠르게 처리하면 되는 것이었다.

이 풀이를 구현해서 맞았다.

1:53 ~ 2:03 (47 / 100 / 100 / 14 = 261)

4번 문제에서 기본적인 섭테를 풀었다.

N이 작은 경우와 직사각형을 1차원으로 나타낼 수 있는 경우를 각각 구현해서 맞았다.

2:03 ~ 2:29 (100 / 100 / 100 / 14 = 314)

1번 문제로 돌아와 전체 문제를 고민했다.

생각해보니 주어진 조건에 의해 모든 경우에서 행렬을 적절히 바꾸면 히스토그램의 꼴이 된다는 것을 알아냈다.

따라서 섭테와 같은 방법으로 풀 수 있었고, 구현해서 맞았다.

2:29 ~ 3:13 (100 / 100 / 100 / 40 = 340)

4번 문제에서 O(Nlog^3N) 풀이를 떠올렸는데, 전체 문제는 당연히 시간 초과가 날 것이라 생각해 N 제한을 줄여서 구현했다.

구현해서 맞았는데, 생각보다 시간이 얼마 안 걸려서 N 제한을 늘려서 제출했다.

3:13 ~ 3:14 (100 / 100 / 100 / 100 = 400)

N 제한을 늘려서 제출하니 100점이 나왔다.

생각보다 너무 빨리 모든 문제가 다 풀려서 당황했다.

3:14 ~ 5:00 (100 / 100 / 100 / 100 = 400)

할게 없어서 뻘짓을 하면서 시간을 때웠다.

2/22 2차 선발고사 후기

1차 선발고사를 잘 봐서 2차 선발고사는 상대적으로 가벼운 마음으로 응시했다.

1차 선발고사의 난이도가 쉬웠던 만큼 문제도 더 어려워질 것이라 생각했고, 그만큼 점수가 역전되기는 더 어려울 것이라고 생각했기 때문이다.

그래도 한 달 동안 열심히 문제를 풀면서 노력했기 때문에, 2차 선발고사를 깔끔하게 마무리하기 위해 문제를 최선을 다해 풀었다.

0:00 ~ 0:20 (0 / 0 / 0 / 0 = 0)

문제를 모두 읽고 이해한 뒤 섭테 배점과 조건을 종이에 정리했다.

이번 문제들은 1차 선발고사에 비해 문제에서 주어지는 상황 자체가 복잡해서 이해하는 데에도 시간이 꽤 오래 걸렸다.

0:20 ~ 1:16 (67.7 / 0 / 0 / 0 = 67.7)

1번 문제가 그나마 가장 할만해보여서 1번 문제를 풀기 시작했다.

결국 두 서브트리를 빠르게 합치는 것이 관건이었는데, 이는 서브트리 사이즈를 A, B(A<B)라고 하면, A+B-1번의 쿼리 또는 AlogB번의 쿼리를 사용해 합칠 수 있었다.

처음에는 두 가지 방법을 독립적으로 사용했는데, 둘 중 더 유리한 방법을 택하니 67.7점이 나왔다.

1:16 ~ 1:34 (67.7 / 0 / 0 / 18 = 85.7)

그나마 섭테 풀기가 가장 쉬워 보이는 4번으로 넘어와서 기초 섭테를 풀었다.

O(NQlogN)을 구현해서 맞았다.

1:34 ~ 2:11 (67.7 / 0 / 0 / 18 = 85.7)

그다음 2번으로 넘어와 섭테를 풀기 시작했다.

A, B의 조건을 잘 따져주면 되는데, 디테일을 섬세하게 하지 못해서 계속 틀렸다.

2:11 ~ 2:29 (67.7 / 0 / 18 / 18 = 103.7)

2번이 계속 틀리길래 3번으로 넘어가서 섭테를 풀었다.

주어진 그래프가 트리인 경우에는 트리 DP로 잘 계산할 수 있었다.

트리 O(N^2)을 구현해서 맞았다.

2:29 ~ 3:04 (67.7 / 28 / 18 / 18 = 131.7)

다시 2번으로 넘어와 섭테를 풀었다.

조건을 진중하게 따져주니 그럴듯한 방법으로 풀 수 있었다.

3:04 ~ 3:57 (67.7 / 73 / 18 / 18 = 176.7)

2번의 45점 섭테를 더 풀었다.

적당히 조건을 쳐내고 나면 2D 세그트리로 구현할 수 있었다.

3:57 ~ 4:07 (67.7 / 73 / 46 / 18 = 204.7)

갑자기 3번 섭테의 트리 O(N)(?) 풀이가 떠올라서 구현해서 맞았다.

합이 N인 수들의 종류의 개수는 최대 O(sqrtN)개라는 사실을 활용해 시간복잡도를 유의미하게 줄일 수 있었다.

4:07 ~ 4:25 (71.62 / 73 / 46 / 18 = 208.62)

1번 문제에서 상수를 바꿔보니 점수가 조금 올랐다.

4:25 ~ 4:46 (71.62 / 73 / 46 / 24 = 214.62)

4번 문제에서 O(50QlogM)을 구현해서 맞았다.

금광세그를 짜니 시간초과가 나서 구간을 미리 합쳐준 뒤 최댓갑 세그와 lower_bound를 쓰니 10초 시간 제한에서 9초 정도에 가까스로 통과됐다.

4:46 ~ 5:00 (71.62 / 73 / 46 / 24 = 214.62)

14분 동안 현실적으로 할 수 있는 것이 없어서 3번 전체 문제 고민하면서 남은 시간을 기다렸다.

종료 이후

2차 선발고사 점수가 생각보다 낮게 나와서 불안했는데, 나만 문제가 어렵다고 느낀 것이 아니었다.

스코어보드가 나왔는데, 전체 2등이었다.

국대가 되어 기분이 좋았다. 예아.

mickeyjung orz.