2026. 01. 25. 에 진행된 IOI 1차 선발고사 후기 + 2026. 02. 08. 에 진행된 IOI 2차 선발고사 후기이다.
이 글은 2차 선발고사를 잘 봐서 국대가 되지 못하면 삭제될 예정이다. 였으나 글 많이 써놓은게 아까워서 그냥 올리기로 했다.
결과
1차 6등 + 2차 4등으로 최종 5등, 국가대표 후보가 되었다.
1차대회
대회 전
우현이와 테트리스를 하고, 다다스가 디맥하는데 코치가 뺏어서 하는걸 구경하고, 이런저런 뻘짓을 하면서 시간을 보냈다.
0:00~0:10(0/0/0/0=0)
문제들을 읽고 문제 조건을 이해했다. 보자마자 풀이의 방향이 떠오르는 문제가 없었고, 상당한 불셋임을 직감했다.
0:10~0:34(52/0/0/0=52)
1번 문제의 자명한 서브태스크를 긁었다. 균형잡힌 수열의 길이는 2^k-1 꼴이므로, 후보의 개수가 NlogN개가 되어 모든 후보들을 각각 확인해 NQlog^2N을 구현하여 52점을 받았다. 12점을 더 받을 수 있었지만, 구현이 귀찮기도 했고 나중에 100점 풀이가 떠오를 수도 있으니 잠시 미뤄두었다. 시작한지 30분만에 생각보다 큰 점수를 얻어 시작이 좋다고 생각했다.
0:34~0:50(52/0/18/0=70)
2번을 보려고 했으나 너무 어려워 3번으로 넘어갔다. 트리의 깊이를 먼저 정해 놓으면 아래에서부터 최대한 밑에 쌓아올리는 방식으로 배치하고, 겹치는 부분이 없는지 확인해주면 될 것 같았다. 이를 구현했는데 18점을 받았다.
잠시 생각해보니 반례를 찾을 수 있었다. 모든 노드에서 서브트리가 겹치지 않는지를 따로 확인해주어야 했다. 이는 트리를 체인으로 분할해 서브트리의 체인들의 시작점을 정렬하고 min(v[i], i)를 구함으로써 확인해줄 수 있었다.
0:50~2:10(52/0/18/0=70)
각 노드마다 다이나믹 금광세그를 하나씩 만들어주고 스투라로 합치고 영차영차 해주면 풀리는 문제였다. 아직 시간은 많으니까 AC 받기만 하면 된다 라는 마인드로 열심히 구현했는데, 디버깅하느라 미쳐버릴 뻔 했던 것 같다. 대회 시작 후 2시간 조금 넘게 지나, 결국 어디가 문제인지를 찾지 못하고 이대로는 70점으로 대회를 마무리하게 될 것 같아 코드를 싹 지우고 다른 문제로 넘어갔다.
2:10~2:49(52/0/18/0=70)
2번 문제는 ODC를 구현하면 19점을 받을 수 있었다. 그래서 열심히 구현했는데 Nlog^2N에서 TLE가 났다. 끝나고 제출했던 코드를 gpt에 넣어보니 롤백유파 부분을 잘못 짰다고 한다. ㅄ
2:49~3:08(52/0/60/0=112)
개빡쳐서 다시 3번으로 넘어왔다. 노드의 깊이가 고정이고, 겹치는지만 판단해주면 되는 N^2 서브태스크를 긁어 21점을 받고, 각 노드를 같은 논리로 겹치지 않게 배정하는 코드를 제출해 29점을 더 받았다. 한참 동안 점수가 그대로라 멘탈이 나가있었는데, 그래도 100점을 넘기니 조금 안정이 되었다.
3:08~3:49(52/0/60/26=138)
4번으로 넘어왔다. 무슨 더러운 필충조건을 하나 찾아서 26점을 받았다. Ai=1일 때는 min(B)=1이고 mex(B)>max(B) 일 때 멋진 구간임이 성립해서, 서다수쿼를 풀면 16점을 더 받을 수 있었다. 세그트리 구현이 갑자기 기억이 안 나서 mo's NsqrtN 코드를 제출했는데 TLE를 받았다. pragma GCC를 붙여도 안 돌길래 좀 이따가 세그트리를 짜기로 하고 일단은 넘어갔다.
3:49~4:16(64/0/60/26=150)
이때쯤 4문제가 다 이렇게 어려운 것은 말이 안 되고, 나만 모르는 개쉬운 문제가 하나 있으며 내가 그걸 풀지 못하면 국대는 물론이고 상위 10명에도 못 들 것이라는 슬픈 생각을 했다.
아까 미뤄두었던 1번의 12점 서브태스크를 구현하려다가, 어떤 구간에 대해, 그 구간의 균형 여부가 갱신될 때마다 위로 올려주면 되지 않을까? 하고 구현했는데 구현력이 딸려서 런타임 에러가 계속 났다. 그래서 포기하고 12점만 긁었는데 나중에 보니까 그게 맞았다ㅅㅂ.
4:16~4:38(64/0/100/26=190)
생각해보니 아까 다이나믹 세그트리로 관리하려던 것을 루트질로도 구현할 수 있었다. 최근 SciOI의 문제를 검수하며 구현해 본 적 있는 트릭이라(대 밍 구), 제발 이거라도 돌아야 한다는 생각으로 짜서 제출했다. 20만에 NsqrtNlogN이라서 불안했지만, 다행히도 잘 돌아 주어 100점을 받을 수 있었다.
4:38~4:47(64/0/100/42=206)
시간이 얼마 없어 4번의 서다수쿼섭테와 2번의 ODC를 긁고 끝내면 딱 만족스럽겠다고 생각했다. 서다수쿼를 머지소트트리 비슷하게 구현해 16점을 더 받았다.
4:47~5:00(64/0/100/42=206)
내 ODC 코드가 왜 틀렸는지를 살펴보는데, 이대로 ODC를 못 고치고 끝날 것 같은 생각이 들었다. 그래서 10분 정도 남기고 짜던 걸 다 지우고 O(SNQ)를 구현했다. 대회 시간을 50초 정도 남겨두고 제출했는데, 틀려서 그냥 제출창에 빠큐 한번 날리고 마무리했다.
대회 이후
쉬워보이는 1번을 못 풀었지만, 그래도 꽤 어려운 3번을 풀었기 때문에 나에게도 꽤 승산이 있을 것이라고 생각했다. 옆자리에 있었던 dadas08에게 점수를 물어봤는데, 300이 넘는다고 해서 조금 절망적이었다. dadas08 피셜, 1번과 4번을 풀고 나서 "김유담은 이거 못푼다" 하면서 나는 경쟁 대상에서 제외하고 시작했다고 한다.
3번은 나 혼자 풀었다. 구현은 복잡하지만 풀이가 꽤 자명하다고 생각해 3~4명 정도는 풀었을 수 있겠다고 생각했는데, 대부분 1번과 4번에 시간을 많이 쓴 것 같다.
작년에 국대를 했던 변키정 듀오는 280점대, 4등인 pk661은 232, 5등인 woohyun_jng은 224, 그리고 내가 6등이었다. 7등부터는 170점대로 격차가 조금 벌어져, 나와 pk661, woohyun_jng의 치열한 4등 싸움이 될 것으로 예상한다.
1/26~2/7
1차 선발고사에서 중저점? 정도를 띄웠기 때문에 2차에서 더 잘해야 했다. woohyun_jng은 매일 셋을 하나씩 돈다길래 몇 번 따라서 같이 돌았다.
1/26
17677 32040 30941 15865 로 된 셋을 돌았고, 100/100/46/100=346점을 받았다. 끝나는 시간을 착각해서 4시간셋을 돌게 되었다.
1/27
뭔가 일정이 잘 안 맞아서 셋은 돌지 않고, 대신 친구들이 푼 문제를 따라 풀었다.
1/28
학원일정이 빡센 이슈로 PS를 하지 못했다. ㅠㅠ
1/29
24945 24946 24947로 이루어진 셋을 돌았다. 줫망해서 결과는 잘 기억이 안난다.
2번은 더럽고 끔찍한 투스텝 문제고, 1번과 3번을 업솔빙했다. 각각 다4/플2 인데 못 풀어서 조금 슬펐다.
저녁에는 코드포스 Div.1이 있길래 참가했다. 낮에 셋을 망한 덕분인지 굉장히 잘봤다. 53등으로 2800대의 인생퍼포를 내고 찐렌지를 스킵하면서 레드를 찍었다. 또한 경기과고 레이팅 1짱이 되었다. (byunjaewoo와 공동으로)
푼제를 푸는 속도는 매우 좋았는데, A와 D에서 쓸데없는 실수를 하여 점수가 꽤 많이 깎였다. N제한과 mod를 잘 확인하도록 하자!
1/30 ~ 2/1
친구들이 푼 문제를 열심히 따라 풀었다.
32007 20049 19509 20105 17188 14166 33058 (=27289=touch the sky)
2/2
18848 28058 14875 19927로 이루어진 셋을 돌았다. 너무 어려워서 뒤에 두개만 풀고 ㅌㅌ했다.
17146과 27284를 풀었다.
2/3 ~ 2/7
마음 같아서는 우현이처럼 1일1셋을 하고 싶었지만, 학원 이슈로 5시간을 꽉 채워 돌기가 쉽지 않았다. 그리고 셋을 돌 때는 간절한 마음이 잘 안 생겨서 섭태를 잘 안 긁게 되어, 차라리 다하위 빨리 풀기 연습을 하기로 했다.
문제 셋은 solved.ac에 (@woohyun_jng & @byunjaewoo) *d5..d4 !@$me 검색하고 랜덤돌려서 뽑았다. 1차 직후에는 70문제 정도 있었는데, 선발 직전에는 40문제 정도로 줄일 수 있었다.
2/3 : 21816 20193 27841 14240 12766 21788 21793
2/4 : 32045
2/5 : 27996 16012 11934 16982 33494 10067 17675 14894 24490 19556 25403
2/6 : 13318 27844 17274 5559 15870 14509 21795 23065
2차대회
대회 전
대회 전날에는 잠을 잘 못 잤다. 11시쯤 자려고 누웠는데, 내 2년간의 ps인생이 내일 하루에 달려있다고 생각하니 잠이 잘 오지 않아서 계속 뒤척이다가 한 시 좀 넘어서 잔 것 같다.
그래서인지 조금 피곤한 상태로 대회를 쳤다. 몬스터 두 캔을 마셨는데도 피곤함이 잘 가시지 않았다.
대회장에 와서는 친구들이랑 좀 떠들다가 우현이가 던져준 문제(28497)을 같이 고민했다. 다5인데 못풀었다.
0:00~0:20(0/0/0/0=0)
문제를 읽고 조건과 제한, 예상 난이도 등을 종이에 정리했다. 1차대회가 조금 할만하게 나와서 그런지 문제들의 첫인상이 전체적으로 조금 무서워보였다. 1번과 2번은 애드 혹 인터랙티브, 3번은 그리디, 4번은 자구 문제로 보였다.
0:20~0:36(11/0/0/0=11)
뭘 먼저 잡아볼지 고민하다가 그나마 풀만해보이는 1번을 먼저 잡았다. 나이브 섭태인 11점을 긁었다.
0:36~0:53(100/0/0/0=100)
|X|=2인 서브태스크를 긁어보려고 고민했다. 집합을 4개로 분할하고, 4C1+4C2번의 쿼리를 날려 포함배제를 이용하면 점수를 받을 수 있었다. 25점을 더 받았다. 또한 그 풀이를 확장해 6개의 집합으로 분할하고 6C1+6C2+6C3개의 쿼리를 날려 포함배제를 이용하면 전체 문제를 풀 수 있었다. 생각보다 빨리 100점이 하나 나와 좋았다.
0:53~1:19(100/0/0/0=100)
같은 애드혹 인터랙티브 문제인 2번으로 넘어갔다. N<=100인 섭태를 풀어 15점을 받으려고 했는데, 왜인지 모르게 점수를 주지 않았다. 일단 3번으로 넘어갔다.
1:19~1:37(100/0/29/0=129)
Bi=0인 섭태를 긁었다. 슬로프 트릭 비슷하게 해서 쉽게 풀 수 있었다. 여기에 Aliens 트릭을 적용하면 구해야 하는 값 하나를 빠르게 구할 수 있다는 점을 관찰했는데, 그런 서브태스크는 없었다.(사실 있는데 몰랐다)
1:37~2:19(100/5.2/29/0=134.2)
2번으로 넘어왔다. 오류를 찾아볼려고 했는데 뭔가 잘 안돼서 섭태 3과 4에 먼저 접근했다. 섭태 3은 쿼리 N회까지는 쉽게 풀 수 있었기 때문에 열심히 구현해서 5.2점을 받았다.
2:19~3:04(100/23.9/29/0=152.9)
섭태 4는 앞의 절반은 Ai=0이고, 뒤의 절반만을 정렬하면 되는 문제였다. N/2개의 수에 대해, N/4개의 쌍을 만들어 각각을 비교해 준 후 그 결과를 이용해서 정렬하면 N/2개의 쿼리로 문제를 풀 수 있었다.
풀이는 쉬운데 구현할 내용이 너무 많았다. N/2C2개의 정점 쌍을 만들고, 각 쌍을 간선으로 이어주고, SCC를 찾고, 비교 결과로 SCC를 정렬하고, 정렬된 SCC를 기준으로 정점을 또 정렬해야 했다. (나중에 보니 그럴 필요는 없었다)
다행히도 SCC 구현을 한 번에 맞아서 18점 정도를 더 받았다.
3:04~3:58(100/23.9/29/0=152.9)
이제 진짜로 할 게 없었다. 2번의 N<=100 섭태는 몇 번을 내봐도 계속 틀리고, 3번에서 긁을 수 있는 건 3점짜리 나이브 섭태뿐이며 4번은 그 나이브 섭태마저 없었다.
2번에서 쿼리 줄일 방법을 고민하고, 3번에서 관찰하고 터지고를 반복하고, 4번을 고민하다가 아니야이건루상위야 하고 도망치기를 반복하니 한 시간이 금방 지났다. 게다가 앞에서는 다다스가 타자치다가한숨쉬고타자치다가한숨쉬고를 반복하고 있어 멘탈이 갈려나가고 있었다.
3:58~4:35(100/38.9/29/0=167.9)
3번을 풀지는 못할 것 같아 2번으로 다시 돌아왔다. N<=100은 어떻게든 풀어야 한다고 생각했고, 열심히 디버깅을 해보니 sort 함수를 사용했을 때 뭔가 오류가 발생함을 알게 되었다. 결국 머지소트를 직접 구현해 15점을 받을 수 있었다.
4:35~4:51(100/57.1/29/0=186.9)
조금 더 생각해보니 4번 섭태에서 관찰을 조금 더 하면 5번 섭태에서도 점수를 받을 수 있음을 알게 되었고, 몇 줄을 추가해 점수를 더 받을 수 있었다.
4:51~5:00(100/57.1/29/0=186.9)
남은 시간에 현실적으로 할 수 있는 게 없었다. 4번의 쿼리가 단순연산으로 해결 가능하고 시간제한이 크길래 나이브가 돌지 않을까 하는 생각이 들었지만 gcc pragma를 떡칠해도 돌지 않아 점수를 더 얻지는 못했다.
대회 이후
대회가 끝나기 전부터 국대가 되지 못할 것임은 어느 정도 직감하고 있었다. woohyun_jng은 그렇다 쳐도 수올러인 pk661이 1번은 못 풀 리가 없고, 2번에서도 꽤 높은 점수를 받을 것이라 생각했기 때문이다. 그렇다고 이미 80점 가까이 차이가 벌어진 1차의 123등을 역전할 일도 없었다.
끝나고 다다스가 300 업다운 ㅇㅈㄹ하길래 개패고싶었다! 하지만 다다스는 나의 견제대상이 아니었기 때문에 그러지는 않았다.
최종 5등으로 국가대표 후보가 되었다.
아쉽긴 했지만, 2차 때 아무리 잘했다고 해도 지금 점수에서 30점 넘게 올리지는 못했을 것 같아 후회는 없었던 것 같다.
5등까지는 국대교육을 시켜준다고 하니 국교 즐겜하고 학교빠지기쌀먹이나 좀 해야겠다.
dadas orz.