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

2월 5일, 2월 19일 이틀에 걸쳐 2023 국제정보올림피아드 국가대표 선발고사를 쳤다.

1차 176점(4위) + 2차 236점(6위)로 종합 3등을 하여 국가대표로 선발되었다.

이번 방학을 PS에 올인했고, 특히 1차 선발고사와 2차 선발고사 사이 2주 동안에는 학원에 간 시간을 제외하면 PS만 했다. 이 노력이 결과로 나온 것이 정말 뿌듯하고 기쁘다. 운이 꽤 좋게 작용했지만, 힘들게 얻은 기회인 만큼 국제정보올림피아드에서도 좋은 결과를 거두고 싶다.

2월 5일(일요일) 1차 선발고사 후기

사실 첫 선발고사는 가벼운 마음으로 쳤다. 솔직히 장태환, 반딧불, 박상훈 세 명은 어떻게 해도 이길 자신이 없었으며 이 셋을 제외해도 나보다 잘하는 사람이 많았기 때문이다.

00:00:00~01:22:28

우선 지금까지 선발이 항상 그래왔듯이, 쉬운 문제가 하나 이상 있을 것이라 확신했고 그 문제에서 풀태스크를 긁는 것이 가장 먼저 해야 할 일이라 생각했다. 처음 5분간 세팅을 마친 후, 모든 문제 지문을 읽어보았다. 각 문제의 첫인상은 다음과 같았다.

던전(dungeon): 세제곱 풀이가 지문을 읽고 바로 생각났는데, 세제곱 배점이 상당히 컸다. 풀태가 어렵지 않을 것이라고 확신했다.
외곽 순환 도로 2(ringroad2): 일단 문제 이름을 보고 1차 좌절, 차수 3 이하 섭태 보고 2차 좌절을 했다. 문제에서 '홀수 사이클'이라는 단어를 보고 이분 그래프를 떠올리긴 했지만 아주 막막해 보였다. 더군다나 원본 문제는 루비였기에 어려울 것이라고 생각했다.
택시 여행(taxi): O(N^2logN) 풀이를 보고 바로 떠올렸는데, 그 이상으로 확장할 여지가 없는 풀이인 것 같았기에 꽤 어려운 문제일 것이라 생각했다.
야유회(workshop2): 내가 살면서 풀어본 투스텝이 당시 철도밖에 없었는데 심지어 그 철도도 풀이만 떠올리고 구현한 적이 없었다. 그래서인지 너무 막막했고, 문제도 정말 어려워 보였다. 다른 걸 최대한 긁고 이것만 고민하기로 마음먹었다.

그래서 위 4문제 중 유일하게 할만해 보였던 던전을 잡았다. 25분쯤 제곱 풀이를 떠올리는 데 성공했고, 구현에 들어갔다. 45분쯤 첫 제출을 했는데 WA를 받았다. 풀이의 틀이 맞는 것은 분명하였기에 고치면 된다고 생각했다.
풀이의 큰 틀은 맞는데 중복 처리를 조금 잘못했음을 깨달았고, dp를 조금 개선하여 다시 짜서 1시간 10분쯤 제출했는데 또 WA를 받아서 조금 당황했다. 테두리 코너 케이스를 처리해 주지 않았다는 것을 깨달았고, 약간의 예외 처리를 한 후 제출하니 AC가 떴다. 이때 시간이 1시간 22분 28초였고, 100점을 받아 놓으니 심리적 여유가 생겼다.

 

01:22:28~04:08:17

1번을 AC 받고 여유 있게 2번을 잡았는데, 멘붕이 왔다. 첫 서브태스크가 K <= 5였는데 이 풀이조차 떠오르지 않았다. 약 25분 동안 그 어떤 서브태스크에도 접근조차 하지 못했고, 멘탈이 조금 흐트러졌다. 솔직히 K <= 5면 나이브라고 만들어준 것처럼 보이는데 그것도 생각이 안 났다. 그래서 3번으로 넘어갔다.
우선 제곱 다익 풀이 구현이 복잡하지도 않을 것 같았고, 이후 내가 긁을 서브태스크와도 교집합이 없어 보여서 그냥 바로 구현하고 20점을 받았다. 서브태스크 2는 식을 조금 정리하니까 단조성 없는 cht가 나왔다. 리차오 구현이 조금 걸릴 것 같기도 했고, 한 번에 제대로 할 자신도 없었으며, 그 짓을 해도 8점밖에 못 받을 것이었기 때문에 나중으로 미뤘다.
이후 B[i] <= 30 서브태스크를 고민해보았다. 제한이 너무 O(B[i]NlogN)이라고 말해주는 것 같아서 30 * 200000 다익을 생각하고 짰는데 시간초과가 났다. 이상해서 bfs로 바꿔봤는데 AC가 날 리가 없었다. 멘탈이 조금 무너졌다. 그러다 B[i]의 감소를 관찰하였고 다익을 30번 돌리는 코드를 내서 17점을 받았다.
사실 이걸 고민하면서 중간중간에 4번도 많이 봤는데, 아무리 봐도 그 어떤 생각도 나지 않았다. 이럴 줄 알았으면 투스텝 좀 풀어볼걸 하는 후회가 밀려왔다. 이때가 3시간 40분경이었는데, 이럴 바에 그냥 리차오를 짜자고 생각했다. 다행히도 리차오는 한 번만에 잘 돌아갔고, 8점을 더 긁어서 45점이 되었다.

04:08:17~05:00:00

아무리 봐도 4번이 부분점수가 많이 풀릴 것처럼 생겨먹었는데 5점 초과 풀이는 생각조차 안 나니 멘탈이 조금 흐트러졌다.
그러던 중, 진짜 갑자기 머릿속에 m=18 풀이가 떠올랐다. 양쪽보다 크면 1, 양쪽보다 작으면 0, 아니면 오른쪽과 내가 다른 최상위 비트 + 2.
이렇게 긁은 사람을 한 번도 못 봤고, 나도 저게 왜 생각났는지 모르겠다. 이걸 빠르게 구현해서 m=18을 맞고 32점을 받았다.
그리고 20분 동안 계속 고민해보았는데, 생각나는 게 없었다.
그러다 4시간 40분 시점즈음 이 짓을 똑같이 한 번 더 하면 더 줄일 수 있을 것이라는 생각이 들었고, 이 풀이를 구체화하니 4시간 50분이었다. 최대한 빠르게 구현을 해서 4시간 58분에 구현을 성공했고, 4시간 59분 초반에 첫 제출을 했으나 틀렸다. 눈에 보이는 오류가 하나 있길래 고치고 4시간 59분 50초에 마지막 제출을 했다. 대회 종료 전까지 계속 '채점 중'이 뜨길래 나는 도는 줄 알고 대회가 끝난 후에도 스코어보드를 계속 새로고침했다. 그러나 1분이 지나도록 내 점수는 올라가지 않았고, 난 아직도 그때 내 코드가 왜 틀렸었는지 모른다.. 최종 점수는 177점이다.

대회 종료 후

4번에서 점수를 끝내 못 올려서 너무 아쉬웠는데, 끝나고 디스코드 서버에 들어가서 본 첫 점수는 이유찬 학생의 191점이었다. 그냥 망했구나 하고 있었고, 다니엘에게 내 등수를 알려달라고 졸랐다. 다니엘이 내 예상 등수랑 실제 등수가 2 이하로 차이나면 알려준다고 했고, 난 7등으로 예상했다. 그런데 내 등수가 [5, 9]에 없다는 것이었다. 4등 이내일 리는 없고 10등 혹은 그 아래일 것이라 확신했고 좀 절망했다.
그리고 10분 후 스코어보드를 봤는데, 이유찬 학생이 3등이고 내가 4등이었다.. 처음에 보고 놀라서 육성으로 소리를 질렀다. 1, 2등은 예상한 대로 반딧불, 박상훈 학생이 차지했으며 장태환 학생은 미응시였다.
사실 국대가 되고 싶은 욕망은 있었으나 가능성이 높지 않다고 생각했었는데, 1차 선발고사에서 좋은 성적을 받고 열심히 해 보기로 마음먹었다.

2차 선발고사 전까지

1차 선발고사 이후 작심하고 정말 열심히 했다. 마지막 1주 동안은 학원도 동영상강의가 없는 곳만 갔고, 그 외의 시간에 PS만 했다. 그걸 증명할 수 있는 것은 나의 스트릭과 BOJ 제출내역일 것이다.

solved.ac 스트릭

2~3일 전 BOJ 제출내역

우선 초반에는 내 부족한 솔브 수로 인한 단점을 보완하기 위해 솔브가 꽤 많은 문제들을 골라 최대한 풀었다. 웰노운 아이디어를 학습하기 위해서였다. 웰노운이 나왔는데 다 풀고 나만 못 풀면 안 되니까..^^
그리고 어느 정도 학습이 된 후에는 발상형 문제를 조금씩 풀어보았다.
사이 기간 동안 다이아 문제만 40개 이상 푼 것 같은데, 이때 내가 체감할 수 있을 만큼 실력이 많이 상승한 것 같다.

2월 19일(일요일) 2차 선발고사 후기

이번 선발고사는 정말 열심히 준비한 만큼 잘 치고 싶었다. 그만큼 부담을 느껴서인지 전전날 많이 안 잤음에도 불구하고 전날 새벽 5시까지 잠에 들지 못했으며, 결국 4시간 30분 취침했다. 밤에 잠이 안 온 건 1학년 기말고사 이후로 처음인 것 같다.

00:00:00~01:05:46

우선 항상 하던 대로, 약 5분간 지문을 다운받은 후 코드블럭 세팅을 마쳤다. 계속반 선발을 위한 어렵지 않은 문제가 최소 한 문제 있어야 한다는 사실을 인지한 채로 시험을 쳤기에, 어떻게든 풀태를 하나 이상 긁어야겠다고 생각했다. 그리고 지문을 하나씩 읽어보았는데, 첫인상은 다음과 같았다.

기지 간소화(base): 1차에도 트리가 두 개나 있어서 트리가 안 나올 것이라 생각했는데 또 나와서 좀 당황했다. 일단 막막하긴 하지만 문제 생긴 걸 봤을 때 막상 해보면 그리 어렵지 않을 수도 있을 것이라고 느꼈다.
회의실 2(meeting2): 진짜 막막했다. 일단 쉬운 문제는 절대 아닌 것 같았다.
학생들(students): 이것도 엄청 막막하긴 했는데, 조건을 조금만 잘 분석해 보면 그리 어렵지 않을 수도 있을 것 같았다.
팀 만들기(teambuilding): 문제가 너무 단순해서 당황했다. 그래서 더 난이도 있을 것 같다고 느꼈다.

일단 항상 하던 대로 1번 문제부터 간단하게 접근해보았다. 우선 더블카운팅을 해야겠다고 제일 먼저 생각했다. 각 간선이 선택되지 않게끔 하는 (s, e) 개수를 구하여 전체에서 빼주면 될 것이라 생각했으며, 이 접근까지 하고 나서 '어려운 문제가 아니기 때문에, 이건 무조건 풀어야 국대겠구나' 하는 생각을 했다.
각 숫자가 속해 있는 구간을 관리해야겠다고 생각했다. 구간을 set으로 관리하는 문제를 두 선발고사 사이 2주 동안 한 번 풀어본 덕분에 set을 바로 떠올릴 수 있었다. 게다가 당일날 시험 보기 직전에 고민한 문제에서 트리에서의 small to large를 이용한 사풀을 떠올렸는데, 이것 때문인진 모르겠지만 small to large를 어렵지 않게 생각했고 set을 dfs큰작으로 관리하면 로그제곱에 문제가 풀림을 알아냈다.
시간제한이 4초였는데, 제한은 25만이었고 set에서 붙는 로그가 여간 큰 게 아니라서 좀 고민했다. 그런데 25만에서 로그가 intended solution인데 시간제한이 4초인 것은 더 이상할 뿐더러, 로그제곱을 유도하는 서브태스크도 없었기에 그냥 짜기로 했다. 코드를 짜는 와중에도 계속 찝찝한 기분이 들었다.
사실 구현 삑사리가 최근에 좀 잦았던 데다가 하필 set이라 begin, end 등도 케웤하며 구현이 길어져서.. 당연히 틀리거나 시간 초과가 뜰 것이라 생각한 채 첫 제출을 했다. 돌아가는 중에도 계속 불안했고 로그를 뗄 방법을 계속 생각하고 있었는데, 상상도 못한 100점이 떴다. 갑자기 기분이 너무 좋아졌고 마음이 안정되었다. 이때가 1시간 5분이다.

01:05:46~02:18:01

1번을 풀긴 풀었는데, 이게 dfs큰작도 쓰고 아이디어가 마냥 쉬운 게 아니라 생각해서 '계속반 선발을 위한 쉬운 문제'가 아닌 것 같았다. 그래서 다른 문제 풀태에도 한 번 도전해봐야겠다고 생각했다.
1번 다음으로는 문제 번호 순서대로 2번을 잡아보았다. 몇 개의 관찰을 했지만, 다항시간 풀이는커녕 N <= 20 풀이조차 나올 기미가 보이지 않았고 그렇다고 다른 특수 서브태스크도 풀이가 보이는 게 없어서 좀 고민하다가 넘어갔다. 그리고는 4번 문제를 잡았다. 하나를 고정하고 나머지 중 최대를 빠르게 구하는 방법이 없을지 계속해서 고민했지만, 아무것도 떠오르지 않았고 그렇게 시간은 흘렀다. 멘탈에 조금 금이 갔다.
그래서 3번을 잡았다. 3번 같은 문제들이 오히려 관찰을 빠르게 하면 쉽게 풀릴 때가 있기 때문에, 메모장에 메모를 해가면서 관찰을 했다.
그리고 p번째 날 민원이 들어오지 않을 필요충분조건이 임의의 p명의 학생이 공통으로 소속된 강의가 있는 것임을 깨달았다. 이 관찰을 하고 나니 뒤는 쉬웠다. 적당히 DP와 세그먼트 트리로 각 학생이 최초로 민원을 넣을 날을 계산해주면 O(NlogN)에 문제가 해결됨을 알 수 있었다. 구현도 어렵지 않아서 빠르게 구현하고 AC를 받아냈다. 이때가 2시간 18분이었는데, 국대의 가능성이 낮지 않겠구나 생각했다.

02:18:01~03:53:52

2번, 4번 하나 만만해 보이는 것이 없었는데 그나마 4번이 더 할만할 것 같다고 판단되어서 4번을 잡기로 했다. 우선 [0, N-1], [0, M-1]에서 문제를 푸는 방법을 찾기로 했는데, 20분 동안 아무런 유의미한 접근도 못 했다. 하나를 고정하고 다른 걸 구해야 한다는 생각만 하고 있었는데 그것마저 잘 되지 않았다. 조금 멘붕이 와서 2번으로 잠시 넘어가서, '컴포넌트 개수를 단조 감소시킬 수 있다'는 중요한 관찰을 하는 데 성공하였고 2^20*20^2비트dp 풀이를 내는 데 성공하였다. 나중에 구현하기로 하고 다시 4번으로 돌아와서 고민하기 시작했다.
그러던 중 '이거 최대가 되는 위치에 단조성이 없으면 문제를 풀 방법이 진짜 없을 것 같다'는 생각이 들어서, 바로 검증에 들어갔다. 식을 잘 정리하고 재배열 부등식을 2회 사용하니 최대가 되는 위치에 단조성이 있음을 발견할 수 있었다. 당시에는 이걸 착각해서 투 포인터로 짰는데 (당연하게도) 틀렸다. 이때 10분 동안 디버깅을 해 봤으나, 알고리즘 자체가 틀렸는데 고쳐서 맞을 리가 없었다. 시간이 충분했기에 그냥 stress를 돌리기로 했다. 10분 동안 나이브 + 제너레이터를 구현한 후 반례를 찾았는데, 투 포인터로 풀리지 않음을 깨달았다.
단조성이 있다는 것을 다시 엄밀하게 식으로 확인한 뒤, 이를 처리할 방법을 고민하던 중 dnc opt를 떠올렸다. 빠르게 짜서 15점을 받아내는 데 성공하였고, 3번 서브태스크도 RMQ로 어렵지 않게 해결할 수 있음을 깨달아 10점을 더 긁어서 25점이 되었다. 10점 서브태스크의 관찰도 나에겐 충분히 어려웠는데, 다음 서브태스크가 35점인 걸 보고서 그냥 2번을 풀기로 마음먹었다.

03:53:52~04:37:26

2^20*20^2 비트dp를 짜기로 했다. 4시간 10분에 빠르게 짜서 제출했는데 시간 초과가 떠서 좀 당황했다. 하필 시간 초과 직전 테케의 실행 시간은 0.010초 근방이었기에, 무한루프가 도는지 잘 봤는데 아닌 것 같았다. 그러던 중 내 시간복잡도가 O(2^N*N^2)가 아니라 O(2^N*N^2logN)임을 깨달았고, 바로 로그를 떼서 확신에 찬 제출을 했다. 결과는 TLE가 아닌 WA였다.
섭태 1은 맞았는데 섭태 2는 WA인 게 이상했다. 처음엔 단순히 섭태 1이 데이터 개수가 적어서 내가 뚫은 것일 거라고 생각했는데, 다시 생각해보니까 섭태 1은 컴포넌트의 개수가 1이라는 특징이 있음을 알게 되었다. 이걸 이용해서 컴포넌트 개수가 2 이상이 될 때 문제가 발생하는 부분을 찾기 위해 노력하였고, 결국 틀린 부분을 찾아서 제출하고 총 11점을 긁을 수 있었다.

04:37:26~05:00:00

4시간 37분에 11점을 긁고 나서, '내가 긁을 수 있는 모든 섭태는 다 긁은 것 같다'고 생각했다. 이후 회의실 2의 특수 섭태들과 미팅의 섭태 4를 열심히 고민해보았으나 딱히 떠오르는 것은 없었다. 4시간 50분이 된 후에는, 어차피 지금 풀이를 떠올려도 구현을 못 할 것 같아서 그만하기로 했다. 마지막 10분 동안은 내가 국대가 되지 않았을 때 멘탈 관리를 어떻게 할지 등등 잡생각에 빠져 있었는데, 다니엘 말로 줌 화면에서는 내가 기도하는 것처럼 보였다고 한다.

대회 종료 후

사실 초반에 3번을 맞고 나서는 국대가 될 확률이 꽤 높다 생각했었는데, 남은 시간이 줄어들수록 점점 초조해져 갔다. 1번이나 3번은 둘 다 크게 어렵지 않아서 대부분 풀태를 짰을 거고, 2나 4번은 나이브랑 쉬운 섭태 몇 개만 긁어도 내 점수는 나올 테니 충분히 뒤집힐 수 있을 것 같았다. 끝나고 나서 바로 슬랙과 카톡을 켰다. 스코어보드가 올라와 있었고, 나는 3등이었다.
스코어보드를 보고 나서 정말 너무 기뻤다. 그간 2달간의 노력을 보상받은 것만 같아서 좋았고, 내가 PS를 조금 늦게 시작한 편이라 스펙이 많이 없었는데 그래도 좋은 스펙 하나를 얻어냈다는 생각에 정말 행복했다. 너무 기분이 좋기도 했고, 또 실감도 안 났다. 사실 실감은 지금도 안 나는데, 최근 2주 동안 날 압도하던 엄청난 스트레스가 사라지고 좋은 결과로 돌아왔다는 사실 그 자체만으로도 정말 기쁘고 후련하다.
사실 나만큼, 혹은 그 이상으로 간절했던 학생이 정말 많았을 것이고, 그런 학생 중 탈락한 학생도 많다. 이런 학생들 사이에서 얻은 좋은 기회인 만큼, 국제정보올림피아드도 열심히 노력해서 후회없이 치르고 싶다.
오늘 하루 축하해 준 수많은 분들께 감사드리며 글을 마친다.