IOI 2022 1차 선발고사 후기

20220427 추가 : 대회 도중 점수와 등수 변화 그래프

 

써도 되는지 모르겠지만 써봅니다... 2차 선발고사가 끝나고 만약 떨어지게 된다면 1차 선발고사 후기는 영영 세상에 나오지 못할 거 같아서 그냥 지금 쓰고 올려봅니다.

 

선발고사 이전 : 평소보다 훨씬 빠른 수면시간인 12시 반에 수면을 청해봤지만 잠이 잘 안 왔고 결국 세 시에 다시 깼다. 다시 자려고 노력해봤지만 결국 6시는 되어서 다시 잠들었다. 선발고사 당시 컨디션에 영향을 줬을 거 같다. 

 

시작 후 한 시간 : 선발고사 전략은 모든 문제를 섭태가 적은 순서대로 읽어보는 거였다. 섭태 개수는 각각 6개, 7개, 5개, 6개로 가장 섭태개수가 적은 3번 문제부터 읽어보았다. 그리고 절망했다. 당장 보이는 풀이로 긁을 수 있는 점수가 단 '1점'뿐이었다. 원래는 보이는 섭태들을 한 번 긁어보려 했지만, 이미 꼬여버렸다.

그리고 1번, 2번, 4번을 읽었는데 읽고나서 멘탈이 붕괴되기 시작했다. 만점 풀이는커녕 서브태스크도 한자리 점수밖에 못 긁겠고 지금 보이는 점수들만 긁으면 총점이 50점이 안 되는, 그야말로 대재앙적인 상황이었다. 30분동안 멘탈이 나간 채로 이리저리 돌아다니면서 서브태스크 풀이들을 구상해봤지만 진척이 없었다.

그래서 일단 가장 서브태스크 풀이가 가장 많이 보이는 4번의 서브태스크를 긁고 점수를 받으면서 분위기 전환을 해보기로 하였다. 소소한 맞왜틀을 10분 정도 한 이후 결국 1시 54분에 4번에서 35점을 받아냈다. 하지만 그것이 지금 내가 긁을 수 있는 점수의 전부였다. 그거 외로 긁을 수 있는 것은 2번 7점뿐이었고, 2번 7점은 좀 미뤄놓기로 한 상태였다.

 

시작 후 두 시간까지 : 0 0 0 35라는 패닉적인 점수에 충격먹은 나는 멘탈이 2차적으로 부숴졌다. 그냥 이미 부서진 멘탈이 다시 부서져서 흔적도 찾지 못할 정도로 산산조각났다. 또 문제를 사방으로 돌아다니면서 풀이들을 찾아보았지만 결론은 나오지 않았고, 4번이 가장 쉬운 문제라는 추측을 하고는 4번에 시간을 박기 시작하였다. 그리고 4번에 약 30분 가량 시간을 들인 결과, 다익스트라 알고리즘을 이용한 제곱로그 풀이를 내었다. N=5000인 서브태스크에서 TLE가 났지만, N=500인 서브태스크는 맞추어서 15점을 올렸고 50점이 되었다.

 

시작 후 세 시간까지 : 트리 문제인 1번에서 간단한 관찰을 하였다. 어쩌면 자명한 관찰인데 그걸 이렇게 늦게 한 것이 당시 나의 상태가 영 좋지 않았다는 것을 얘기해주는 것일지도 모른다. 그리고 그 관찰을 토대로 O(NQ)의 시간복잡도를 가지는 나이브 알고리즘을 짜서 33점을 받았다. 그리고 완전이진트리 서브태스크도 높이가 작다는 성질을 이용해 저 나이브 알고리즘을 똑같이 구현해서 5점을 추가, 38점을 받았다. 그런데 생각해보니 만점도 비슷하게 될 거 같았고, 실제로 그랬다. 하지만 그걸 똑같이 짜보려니까 서브트리 max 쿼리를 온라인으로 정점이 추가되는 트리에서 해야된다는 문제점이 있었고, 그걸 해결하는데 15분 정도 고민을 하였다. 하지만 생각해보니 만점이 비슷하게 되는 이유와 비슷한 이유로 서브트리 max 쿼리도 amortized O(logN)에 잘 된다는 생각이 들었고 그것을 구현, 3시 56분에 만점을 받았고 그제서야 나는 어느 정도의 심리적 안정을 얻을 수 있었다.

 

마무리까지 : 이후 제곱로그 알고리즘이 TLE가 난 4번으로 갔다. 간단한 커팅들 몇 개를 추가해주자 5000 제곱로그가 돌았고, 4번이 68점이 되었다. 이때 점수가 100 0 0 68이었다. 마지막 서브태스크만을 남기고 4번을 다 긁고나니 만점 욕심이 났다. 그리고 만점에 근접한 풀이를 하나 냈다. 그런데 그 풀이가 O(Nlog^2N) 리차오세그 풀이였다. 50만에서 돌 거 같지는 않았다. 하지만 일단 이 방향으로 풀이가 나왔으니 정풀도 이 방향일 것이라고 추측한 나는 이 문제는 답이 없으니 버리는 방향으로 가닥을 잡았다. 이후 아무리 봐도 1점이 최대치인데다가 섭태 점수까지 짠 3번을 아예 버리고, 2번을 많이 긁어서 200점을 넘긴다는 전략을 세웠다. 그리고 오랜 고민 끝에 2번의 Subtask 2까지 긁는 15점 풀이를 짰고, 30분간의 맞왜틀 끝에 15점을 받았다.(4시 39분 제출, 5시 8분 15점) 그리고 2번을 고민해봤지만 별 성과는 없었고, 3번에서 말도 안 되는 그리디 풀이를 하나 짜서 틀린 다음(그걸 짜본 이유는 만약 그 풀이가 맞는데 나만 못 맞춘 것이라면 망하기 때문에 그 가능성을 차단하기 위함이었다.) 그냥 생각했던 1점 풀이를 짜서 1점을 받았다. 총점 184점이었다.

 

마무리 : 예상등수는 약 8등 정도였다. 1번은 10명 정도는 풀었을 거 같고, 4번은 68점을 다들 받고 100점을 받아내는 초인들이 몇 명 있을 거 같았다. 그리고 2번은 15점은 다들 받을 것이고 몇몇은 서브태스크 한 두개를 더 긁었을 거 같았고 3번은 애초에 1점이 최대라는 게 말이 안 되니까 약간은 더 긁혔을 거 같았다. 하지만 점수를 보기가 너무 긴장됐던 나는 6시에 대회가 끝나자마자 테트리스(tetr.io)를 켰다. 테트라리그를 돌리긴 좀 그런 거 같아서 40line을 한 판 하면서 마음을 안정시켰다.(기록은 1분 57초였다) 그리고 점수를 물어보러갔는데, "200 업다운"이란 멘트가 나왔다. 그 순간 진짜 예상보다 더 조진 줄 알았다. 그리고 처음 나오는 세 명의 점수가 나보다 높았다. 그래서 예상대로구나 했는데, 그 후로 나보다 높은 사람이 단 한 명도 없었다. 그렇게 4등이었다. 정신적 극한에 몰린 채로 대회를 친 거치고는 만족스러운 결과였다. 얘기를 들어본 결과 1번은 관찰을 못해서 못 푼 학생이 많았고, 오히려 4번이 100점도 받을만한 문제였다. 나는 4번을 못 풀고 1번만 풀었는데, 4번은 못 풀어도 68점 섭태까지 긁을 수 있지만 1번은 못 풀었을 때 긁을 수 있는 섭태가 제한적이어서 1번 4번 둘 다 푼 한 명을 제외하면 1번만 푼 사람이 4번만 푼 사람보다 유리한 환경이었다. 그리고 그 덕을 꽤 봐서 4등을 하였다. 하지만 점수차가 촘촘하기 때문에 이 4등은 그냥 '이번에 이긴 사람을 또 이기면 국대를 할 수 있다'라는 심리적 안정을 얻을 수 있는 점만으로 만족해야 할 거 같다. 어차피 서브태스크 한두개로 뒤집힐 거니까. 이번 선발을 그래도 적당히는 쳐서 적어도 지금 이 순간 내 멘탈이 뭉개지지 않고 버틸 수 있는 것으로 만족한다.