IOI 2022 2차 선발고사 후기

1차 선발고사 후기

20220427 추가 : 2차 선발고사 도중 점수와 등수 변화 그래프

20220427 추가 : 전체 선발고사 도중 점수와 등수 변화 그래프

다행히 성공적으로 국가대표가 되어서 이렇게 2차 선발고사 후기를 적을 수 있게 되었다. 운이 좋았다고 생각한다.

 

2차 선발고사는 사실상 내가 여태까지 공부해왔던 거의 모든 것들을 걸고 치는 시험이기 때문에 매우 중요했다. 그래서 준비를 열심히 했는데, maruii님이 문제 세트를 제공해주시고 풀이를 설명해주시는 등 정말 많은 도움을 무상으로 제공해주셨다.

 

시험 전날에는 잠을 잘 잤다. 그전날에 잠을 별로 안 자는 전략이 유효했던 것 같다. 

 

시험 직전에는 컨벡스헐, CCW, KMP, SA 등 딱히 마주치기도 싫고 구현하기도 싫고 구현해본 적도 없는 알고리즘 위주로 공부하려 했는데, 귀찮아서 컨벡스헐과 ccw만 보고 시험을 쳤다. kmp랑 sa는 시험에 안 나왔으니 적절한 선택이었던 것 같다.

 

그리고 1시가 되어 시험이 시작되었다. 원래 내가 받은 점수를 시간대에 따라서 종이에 기록해뒀었는데 며칠 후 코로나로 7일동안 격리되었다가 풀려나니까 종이가 없어져있어서 이 내용은 그냥 내가 기억하는 대로 적당히 묘사하는 것이다.

시험이 시작되자마자 1 2 3 4번을 순서대로 읽기로 했다. 1번은 18점까지는 자명한 서브태스크였고, 당시에 생각을 잘못해서 54점까지도 자명하다고 생각했었다. 그리고 54점까지도 자명하니 그냥 제일 쉬운 문제라고 판단하고 바로 풀어버리려고 했는데, 잘 안 풀렸다. 그래서 일단 2번으로 넘겼다.

 

2번은 좀 어지러운 문제였다. 중복 제거 조건이 들어가서 진짜 어지러워져서 일단 dp인 건 알겠지만 도저히 못 짜겠고 짜기도 싫고 풀이도 모르겠는 그런 문제였다. 그래서 3번으로 넘기니 그나마 적당한 문제였다. 읽고나서 내린 판단은 천천히 잘 긁기에 좋은 문제라는 것이다. 읽자마자 1,2,3번 섭태의 풀이가 보였기 때문에 그 중 2,3번 섭태를 동시에 짜서 바로 제출했다. 일단 양수 점수를 받아내면 분위기 전환이 가능할 것이라는 판단도 있어서였다. 

 

그리고 제일 쉬운 문제를 처리하기 위해 다시 1번으로 돌아왔다. 다시보니, 18점만 자명한 서브태스크이고 54점은 생각을 잘못한 것이었다. 하지만 그와 동시에 저 문제에 홀의 정리를 사용할 수 있다는 관찰을 하였다. 순서를 잘 정해서 배열을 잘 관리하기만 하면 54점을 받을 수 있다는 결론을 새로 내었다. 그리고 홀의 정리를 이용한다는 관찰은 꽤 유의미한 것으로 보였기에 100점 풀이를 고민해보기로 하였다. 이분탐색을 사용하는 풀이를 여러 번 고민해보았지만 모두 답으로 가지 못하였다. 이후 컨벡스헐을 사용한 풀이를 생각해보았고, 꽤 혁명적인 아이디어라는 생각을 하였다. 하지만 이래도 정답까지는 가지 못하였다.

 

그 사이 시간은 흘러가고 있었고, 나는 4번을 읽었다. 4번 문제에 대한 결론은 제법 빠르게 도출할 수 있었다. 13점의 2^(N/2)*다항 풀이는 밋인더미들을 사용하면 슥슥 풀 수 있을듯했고, 나머지 점수는 절대 못 따는 점수였다. 그냥 문제를 보자마자 직감적으로 이걸 느낄 수 있었고, 덕분에 이 문제를 깔끔하게 버릴 수 있었다.

 

이후 3번의 섭태를 두 개 더 짜서 맞추고, 1번의 full task와 2번의 subtask를 번갈아가면서 고민하기 시작하였다. 하지만 결론은 나지 않았고, 시간만 하염없이 흘러갔다. 시간이 반환점을 넘으려 한 시점에, 나의 점수는 0 0 50 0 정도였다. 충분히 위기감을 느낄만한 점수였고, 내 2년반의 삶이 여기에 달려있다는 막중한 책임감까지 달고있는 상황에서 그 위기감은 더욱 극심했다. 이러다가는 무조건 대회를 망치고, 영원히(이번이 마지막이니 영원히다) 국가대표를 하지 못하게 될 거라는 생각이 들었다. 대회를 망치지 않을 일말의 가능성이라도 만들어보고싶었기에, 나는 내가 못 풀면 다들 못 푼다는 생각을 하게 되었다. 내가 연습장으로 쓰고 있는 A4용지에 '나몰다몰'(내가 모르면 다 모른다)라는 네 글자를 아주 크게 적고, 알고 있는 서브태스크들을 긁으러 나섰다. 꽤 분위기 전환이 되었던 것 같다.

 

먼저 1번 54점을 긁었다. 이미 풀이는 다 구상했었던만큼 그렇게 오랜 시간이 걸리진 않았다.

그리고나서는 3번이었다. 3번은 그냥 구현만 안 한 1번을 제외하고는 6번과 7번 서브태스크, 이제 거의 최종 서브태스크들만을 남겨두고 있었다. 그래서 6번 태스크를 고민하고 있는데, 원래의 dp풀이를 pq를 이용해 바텀업 방식으로 잘 사용하면 될 것이라는 생각이 들었다. 그 생각을 하고 다시 문제를 보니 dp[i]의 해집합이 dp[i-1]의 해집합을 포함함을 잘 이용하면 문제가 쉽게 풀릴듯했다. 그리고 그렇게 문제를 풀어 드디어 AC를 받고 초록색을 봤다. 이게 약 3시간 20분 시점, 2/3 구간이었다.

 

한 번 초록색을 보니 그래도 가능성이 있을지 모른다는 생각이 들었다. 그래서 일단 아는 서브태스크를 바로 싹 긁어버렸다. 4번의 13점 서브태스크와 2번의 14점 서브태스크를 약 30분의 시간을 들여서 코딩했다.

이후 시간은 2번의 서브태스크를 고민하는데 사용하였다. 2번의 서브태스크 점수들이 꽤 큼직했기 때문이다. 하지만 구상은 잘 되지 않았고, 나는 이 문제가 서브태스크가 잘 긁히는 문제면 그냥 국대 안 한다는 마인드로 2번을 그냥 버렸다.

이제 남은 건 1번. 1번은 들인 시간이 네 문제 중 굉장히 많은 편인 문제였다. 그래서 한 생각들이 되게 많았는데, 볼록껍질에서 이분탐색을 수행한다는 아이디어도 그 중 하나였다. 그리고 그 아이디어를 사용하니 1번의 23점짜리 서브태스크를 맞을 수 있다는 결론이 나왔다. 이 풀이가 완전히 정립된 것이 4시 20분즈음이었고, 23점이라는 점수는 굉장히 큰 점수였으니 나는 이 점수를 받으면 국대가 되고 못 받으면 못 된다는 결론을 내렸다. 입술을 꽉 깨물고 열심히 코딩을 하였고, 코딩량은 그렇게 많지 않은 문제여서 4시 40분즈음에 코딩이 완료되었고 약 5분간 심장떨리는 디버깅을 끝내고 결국 23점을 받아냈다.

 

77점을 받으니 100점도 해볼만하다는 생각이 들었다. 지금 풀이에서 세그만 박으면 되는 게 아닐까?라는 생각을 했었었다. 그정도면 15분 안에도 해볼만하지않을까라는 생각도 하고 있었다. 하지만 그게 아니라는 걸 몇 분 간의 고민 끝에 깨달았다. 그래서 남은 시간동안은 그냥 점수들을 정리하고 내 잡념들을 정리하면서 그냥 쉬려고 했다. 그러고 있었는데 3분을 남긴 시점에서 2번의 N<=20 나이브 섭태가 해시 등을 이용하면 쉽게 풀린다는 것을 깨달았다. 그리고 혹시 짤 수 있을지도 모르니 열심히 코딩을 해봤지만 역시나 실패하고 끝났다. 최종점수는 77+14+100+13=204. 1차 점수와 합치면 184+204=388이었다.

 

대회가 딱 끝났을 때 내 심정은 반신반의였다. 대회가 끝나고 제일 먼저 한 행동은 메모장을 키고 내 유서?를 적는 거였다. 유서는 아니고 국대가 안 됐을 때의 슬픈 심정을 담은 회고록 같은 거... 한 1분 정도 그러고 있다가 사람들 점수를 보려고 디코를 켰다. 상황이 그렇게 나쁘지는 않아보였다. 0솔한 문정후가 3솔이라고 개소리한 거 때문에 깜짝 놀란 거 말고는... 점수공유를 마저 제대로 해보려는 상황이었는데 어딘가에 국대명단이 떴다고 해서 달려가봤더니 떠있었다. 나도 포함이었다. 너무 기분이 좋아서 문을 열고 소리지르며 뛰쳐나갔는데 그때 딱 엄마가 마트 갔다가 돌아온 시간이었다. '성공'이라고 짧고 크게 잘 말하고 껴안고 행복해했다. 진짜 너무 기뻤고, 약 3주가 지난 지금도 기쁜 상태이다. 사실 기쁜 이유에는 만약 국대가 되지 못했을 때 겪었을 엄청난 우울감을 면하였다는 기쁨이 되게 큰 거 같긴 하다만. 행운의 여신은 약 1년간 나를 비껴갔지만, 나를 완전히 외면하지는 않아서 다행이다.

온 신경이 쓰여있던 선발이 끝난 나머지 힘이 풀려서 지금 계속 놀고만 있지만, 그건 원래도 계속 놀았으니 상관없는 거 같다. 국대가 못 된 평행세계의 나를 생각할 때마다 현재의 편안함이 너무 기쁘다.