IOI 2023 후기

8/28 ~ 9/4에 헝가리에서 열린 IOI 2023에 한국 국가대표로 참가했다. 한국 팀 멤버는 박상훈(qwerasdfzxcl), 반딧불(79brue), 이동현(lisifu/kizen), 이성호(puppy/windva)였고, 작년에 비해 꽤 강한 멤버였기 때문에 4금을 노려볼만하다고 생각했다. 나와 동현이는 금메달을 받았고, 딧불이와 성호는 은메달을 받으면서 2금2은의 성적을 기록했고, 국가 순위 5등을 했다.

 

작년에도 IOI에 참가했지만 코로나 이슈로 온라인으로 참가하게 되어서 대회만 치고 끝났는데, 올해는 오프라인으로 직접 헝가리도 가고 여러 행사나 관광을 즐길 수 있어서 매우 좋았다. 솔직히 말하자면 관광은 별 거 없어서 재미없었고 공통 관심사를 가진 외국인 친구들을 많이 만날 수 있었던 것이 너무 즐거웠다. 특히, 개회식이 끝나고 숙소로 돌아가는 길에 일본 국대들과 많은 대화를 했는데, 생각보다 잘 맞아서 금방 친해질 수 있었다.

 

대회 이야기를 다시 해보자면, 올해 대회는 내가 지금까지 친 대회 중 제일 어렵고 힘들었던 대회였던 것 같다. 실제로 각 문제의 솔브 수가 11/10/3/2/28/0으로, 한 문제라도 만점을 받는 것이 매우 어려웠고 부분 점수를 받는 것도 쉽지 않은 문제가 대부분이었다. 특히, day 1의 경우 지금까지 있었던 ioi 대회 중 제일 어렵게 나온 셋이었다. 어려운 난이도로 인해 한국 국대 대부분이 day 1을 망칠 뻔했지만 다행히 모두 막판에 점수를 끌어올리는 데 성공했다. 나는 43 + 60 + 65.5 + 31 + 100 + 54 = 353.5점을 받으면서 개인 22등, 금메달을 받았다.

Day 1

0:00 ~ 1:00

일단 1번부터 읽었다. 트리에서 뭔가 하는 문제라서 선형을 풀고 적당히 발전시키면 풀릴 것이라고 생각하고 좀 고민을 했다. 30분쯤 고민을 했는데도 선형 제곱로그 풀이 정도만 나와서 일단 다른 문제를 보기로 했다. 2번은 특수한 그래프에서 최장경로를 인터렉티브로 구하는... 답이 없어보이는 문제여서 바로 넘겼다. 3번은 격자판에서 특정 조건을 만족하는 부분집합 크기의 최댓값을 구하는 문제였는데, 조건 판별만 빠르게 해도 25%의 부분점수를 줘서 일단 그럴싸한 조건을 찾아서 짜봤지만 틀렸다. 틀린 건 알겠는데 어떻게 해야 맞을지 감이 잘 안 잡혀서 다시 1번을 고민했다.

1:00 ~ 2:00

내 머릿속에 있던 계획은 1번/3번 중 하나를 풀고, 나머지를 적당히 긁고, 2시간이상 2번에 시간을 투자하는 것이었다. 그러나 쉽다고 생각한 1번이 잘 안 풀렸다. 일단 선형을 계속 고민했고 몇몇 관찰을 한 뒤 선형 O(NlogN) 풀이를 찾아서 코딩을 했고, 2:02:55에 43점을 받았다.

2:00 ~ 3:00

나는 증명은 제대로 안 했지만 대충 비슷하게 하면 트리도 풀릴 것이라고 생각하고 100점으로 추정되는 풀이를 짜기 시작했다. 20분쯤 짜니까 완성할 수 있었고 제출을 하면서 계속 디버깅했지만 43점이 한계였다. 3시간 경과했을 때 뭔가 심하게 잘못되었다는 것을 깨달았다. 쉽다고 추정되는 1번에 거의 3시간을 갈아 넣었고 다른 문제들은 고민도 거의 안 했고 내 점수는 44.5점이었다. 그리고 내 1번 풀이는 높은 확률로 틀린 풀이였기 때문에 그냥 완전히 망했다는 생각 밖에 안 들었다. 몇 분 간 멘탈붕괴된 상태로 아무것도 안 하고 메달 없이 집에 가서 엉엉 우는 상상만 했던 것 같다.

3:00 ~ 4:00

겨우 정신을 차리고 2번과 3번을 긁기 시작했다. 일단 매우 간단한 2번 15점을 받은 다음 3번 25점을 다시 고민했다. 생각보다 금방 풀이를 찾았고 짰지만 N=3에서도 계속 틀려서 또 멘탈이 나갈뻔했다. 다행히 고치는 데 성공했고 섭태별 25% 점수를 받았다. 이때가 4:03:41이었고 내 점수는 43 + 15 + 29.5 = 77.5점이었다. 여전히 망한 상태였다.

4:00 ~ 5:00

3번에서 조건을 간단하게 바꿨기 때문에 다항시간 풀이도 금방 나왔다. O(N^5) 풀이를 빠르게 짰고 40점정도를 추가로 받았다. 점수 합이 100점을 넘어서 겨우 멘탈을 회복할 수 있었다. 40분 정도 남은 상태였고 남은 시간을 전부 2번에 박기로 했다. 2번 60점 풀이가 운 좋게 10분 만에 보였고, 10분 정도 코딩을 해서 한 번에 맞는 데 성공했다. 이때가 4:46:06이었고 43 + 60 + 65.5 = 169.5점이었다. 1시간 만에 100점 가까이 끌어올려서 정말 다행이라고 생각했다.

5:00 ~

대회장을 나와보니 코치들이랑 교수님들이 기다리고 있었다. 서버 오류 때문이었는지 스코어보드가 약 4:40시점에서 프리즈 된 상태여서 정확한 등수는 알 수 없었지만, 대략 금컷 근처라는 것을 알고 너무 기뻤다. 3시간 시점까지만 해도 동메달도 못 받을 것이라고 생각했는데 겨우 등수를 끌어올려서 다행이었다. 내 day 1 등수는 33등이었고, 금메달은 30등까지 주기 때문에 day 2를 잘 보면 충분히 금메달을 받을 수 있는 점수였다.

Day 2

~ 0:00

성호가 day 2에는 쉬운 문제가 정확히 하나 있을 것이라는 주장을 했다. 6문제 다 어려운건 말도 안 되고, 2문제가 쉬우면 day 1에 1개를 넣었을 것이기 때문이라는 주장이었다. 실제로 어느 정도 맞는 말이긴 했다. 대회 전날에 구사과가 일본 팀에 invited guest로 요네다 형제가 있는 것을 발견했는데, 이 소식을 접한 우리는 절망에 빠졌다. 요네다 형제는 joisc(일본 선발고사)에 끔찍한 인터렉티브/투스텝 문제를 출제하기로 유명하기 때문이다. 대표적으로 flights, device2, battle 등이 있다. 참고로 작년 ioi에는 prison이라는 문제를 출제했다.

0:00 ~ 1:00

일단 문제를 읽었다. 1번은 적당히 하면 풀릴 것 같은 트리 문제처럼 보였지만 day 1때처럼 엄청 어려울 수도 있어서 적당히 끄적이다가 넘어갔다. 2번은 뭔가 복잡해서 일단 미뤄뒀다. 섭태가 적고 N M도 별로 안 커서 쉬운 것 같다는 느낌이 들었다. 3번은 끔찍한 문제였다. 누가 봐도 요네다 형제의 작품이라는 것을 알 수 있어서 바로 넘겼다. 1번을 그럴싸한 조건 몇 개 찾아서 짜봤지만 틀리기만 했다.

1:00 ~ 2:00

1번을 좀 더 고민해봤지만 잘 안 돼서 2번과 3번을 봤다. 일단 2번은 39점이 매우 쉬웠고 65점도 쉬운 편이었다. 3번은 적당히 탐색하면 35점을 받을 수 있고, 이걸 2번 반복하면 54점을 받을 수 있는 것 같았다. 일단 2번 39점을 짰고 2번과 3번을 계속 고민했다.

2:00 ~ 3:00

2번 풀이의 대략적인 흐름이 나온 것 같아서 3번을 긁고 2번을 짜기로 했다. 3번은 일단 35점 풀이만 짰고 54점은 맞는지도 잘 모르겠고 구현이 많이 늘어날 것 같아서 일단 안 짜고 미뤘다. 2번 100점을 하기 위해 필요한 관찰이 사실인지 39점 코드로 계속 검증하면서 풀이를 정리했고, 2시간 46분 시점부터 100점 코드를 짜기 시작했다. 중간에 디버깅하면서 풀이가 틀린 줄 알았는데, 인덱스 관리를 다른 방식으로 하면 된다는 것을 깨닫고 고쳐서 100점을 받았다. ioi에서 초록색을 봤다는 사실이 너무 기분 좋았다.

3:00 ~ 4:00

2번 100을 받고 1번을 풀기로 했다. 그러나 계속 섭태 1, 3만 맞고 다른 섭태는 틀렸다. 이때 잠깐 섭태 번호를 착각해서 N, M이 200 이하인 섭태에서 tle가 나는 줄 알고 상수커팅을 좀 했는데 결과가 안 변해서 포기하고 다른 섭태를 긁었다.

4:00 ~ 5:00

섭태 3을 맞는 코드가 있었기 때문에 그 코드를 쓰면 섭태 4를 맞을 수 있었고, 섭태 2는 쉽게 짤 수 있어서 섭태를 빠르게 긁을 수 있었다. 40분쯤 남은 상태여서 3번을 더 긁기로 했고, 초반에 생각해 둔 54점 풀이를 짜서 맞았다. 생각보다 구현이 복잡하지 않았고 시뮬레이터도 있어서 편했다. 20분 정도 남았는데 딱히 할 수 있는 게 없기도 했고 피곤해서 좀 쉬었다. 점수는 31 + 100 + 54 = 185점이었다.

5:00 ~

합산 22등, day 2 6등이라는 소식을 들어서 너무 기분이 좋았다. 여담으로 요네다 형제는 day 1에서 1, 3번, day 2에서 3번을 출제했다고 한다. 일본 국대 중 Yuki Tanaka는 4:55에 3번 53점을 받고 4:59:59에 80점을 받았다고 한다. 나중에 물어보니까 의도적으로 그런건 아니고 10초 전에 코딩을 겨우 끝내서 실행도 안 해보고 제출해서 80점을 받았다고 한다. 정말 대단한 것 같다.