IOI 2015 선발고사 후기

꼭 이걸 써야 되는지 써도 되는지는 모르겠다 공개적인 곳에서 자랑하는 것도 아니고,
그래도 이런 경험을 해볼 일이 얼마나 될라나 싶어서 여기다 대강 글로 적어 남기고 싶다.

사실 겨울학교 전까지만 해도 내가 잘하는 지도 몰랐고 국대에 대한 욕망도 별로 없었는데 (기대치가 없으니), 와서 보니까 내가 생각보다 잘하더라.
겨울학교 끝날 때 시험을 치고 대강 6등? 언저리에 머물렀더니 확실히 유혹이 생겼다. 딱히 잘본것도 아닌데 그렇다고 딱히 못 본것도 아니고 그 점수대가 다 비슷비슷해서. 꼴지를 해도 공부야 했겠지만 그래도 목표치를 조금 높게 잡아보기로 했다. 그런다고 죽는것도 아니고 ㅎㅎ

겨울학교 갔다오고 배운게 참 많다.. 세그먼트 트리를 짤 수 있게 된 것도 사실상 그 이후였고, 컨벡스헐트릭도 몇달만에 다시 짰고 등등등... 집에 들어가서 문제를 되게 풀었는데 개인적으로 굉장히 seminal 하다 싶은 문제들을 상당히 많이 풀었다. 사실 갈 수록 소재가 떨어져서 속도가 점점 느려진 감은 있지만.. 암튼 그랬다. 그 와중에 개학도 하고 이사도 했는데, 새 집에 아직 인터넷이 안 들어와서 (이 파트도 인터넷 없이 작성중이다), 시험 전날은 학교에 혼자 남아서 문제를 풀었다.

어찌 보면 당연한 이치지만 뭔가 좋은 문제를 하나 딱 풀고 대회를 치면 잘 보던 거 같아서, 어려운 문제 하나를 잡고 하루종일 풀다가 집에 가기로 했다. (http://geniusainta.com/problems/view/JOI14_pinball) 계속 놀다가 7시부터 노래 틀어놓고 11시까지 하는데 시작할 땐 몰랐는데 나중에는 거의 모의 대회처럼 되버렸다 10시 쯤 되니까 이거 진짜 풀고 집에 갈 수 있을까 싶기도… 결국 20분 늦게지만 풀고 집에 갔다 ^^;

빈 학교에 혼자 남아서 골방에 노래만 틀고 쳐박혀서 문제풀다가, 출출하면 혼자 나가서 돈가스나 한장 사먹고 나오는데 이날 유난히 기분이 좋더라 진짜로.. 문제도 잘 풀렸고 암튼 전날밤은 정말 유례없을 정도로 잘 보냈던 거 같다 예감은 확실히 좋았다

그리고 당일날 시험을 쳤다

첫번째 문제를 보니까 뭔가 기하 냄새가 심하게 나는 문제였다. 자살.. 일단 제꼈다
두번째 문제 역시 마찬가지 느낌이었는데 쿼리 들어오는거 보니까 계산기하보다는 자료구조에 가깝지 않을까 싶었다 얘도 일단 제낌.
세번째 문제를 봤을때는 사실 의아했다 n<=5000인데 저정도는 nlgn에도 풀리지 않을까 싶었던.. 1차 때도 단순 dp 문제가 있었듯이 이것 역시 그냥 빵점방지 문제가 아닐까 싶었다.
네번째 문제는 제정신이 박혀있다면 아무도 코딩하지 않을것이라는 확신이 들었다.

그래서 3번부터 풀었다.
처음에 1차원 dp 점화식을 짰는데 틀리기에 조금 수정해서 2차원 dp를 짰다. (nlgn은 확실히 개소리였다 ㅎㅎ)
잔실수를 몇개 했는데 아무튼 O(n^3) 까지는 금방 완성했다. 이때 1시간 지났었다.

O(n^2) 를 만들려고 하는데 메모리 바운드가 빡세서 이것저것 해야할 게 많았다
토글링 + 부분합 + inchworm + 루프 순서 뒤집기 등 별 잔테크닉을 다 넣어야 풀리는 문제였는데, 부분합에서 멍청한 실수를 하나 해서 (…) 오래 걸리고 inchworm도 멍청한 실수를 계속 해서 (…) 암튼 진짜 계속 틀렸다. ac까지 합쳐서 서브밋 8번 했으니 2개 남긴 셈이다. 계속 코딩미스 내는게 사실 야속했다 나중에 시간 부족할거 같은데. ac를 봤을때 2시간 정도가 지나있었고 남들에 비해서 시간을 너무 많이 낭비한 것 같아서 약간 멘탈에 스크래치..

이후 1번과 2번을 왔다갔다 했던 거 같다.
1번에 대해서 정말 아무 생각도 없어서 일단 1번은 패스를 하고..
2번은 40점 풀이를 떠올린 이후 몇가지 생각을 해봤는데, std::set에 comparator 를 쓰는 거 말고는 40점을 넘기는 방법을 생각해내지 못했고 난 비교 연산자를 구현할 줄 모르기 때문에 (참고로 이 블로그에 비교 연산자 구현이 친절하게 설명되어 있다 ^^;) 일단 40점을 빠르게 긁고 포기했다.

그래서 진짜 1번에 모든 것을 쏟았다. 1번의 풀이가 계산기하에 익숙한 사람이라면 너무나도 trivial한 풀이가 아닐까라고 대강 짐작을 하고, 두시간 이상 1번을 몰두했었는데 딱히 그 시간을 투자해서 얻어낸 건 없었다. (참고로 계산기하를 무지 싫어한다. 그걸 좋아하는 사람이 있기나 하겠냐만 뭐..) 약간 이상한 풀이가 떠올라서 짰는데 7점밖에 안나오더라.. 틀린 풀이인지 맞는 풀이인지도 이것저것 헷갈려서 모르겠고 암튼 총체적 난국이었다.

대강 한시간 좀 덜 남았었을때 세그먼트 트리를 쓰면 풀리지 않을까 싶었다. 이 때 좀 정신을 차린 거 같다. 급히 세그트리를 짜고 별짓을 다해봤지만 생각해보니 그것만 가지고는 안 될 것 같더라. 어려운 문제라는 걸 끝나기 20분 전에 알았다 ㅡㅡ;

아무튼 남은 20분 동안은 문제 풀기를 포기하고 그냥 가만히 있었는데 뭐 당연하겠지만 딱히 좋은 무드는 아니었다. 국대를 못한다고 큰 손해가 가는 건 아니지만, 기대가 컸던 만큼 아쉬운 점이 너무 많았다고 해야 하나.. 이거 떨어지고 koi 나가서 잘 할 수 있을까 걱정되기도 했고 대충 그랬다. 어제 문제도 잘 풀고 예감도 좋았는데 오늘 안 풀리는게 좀 야속하기도 했고.. 근데 사실 딱히 떨어져도 크게 상관은 없을 거 같긴 했다. 시험 끝나기 직전에 질문 폼에 ㅁㄴㅇㄹ 서브밋해놓고 끝냈다 (….)


그런데 시험 후 상황이 내 예상과 완전히 다르게 흘러갔다.

일단 결론을 내자면
1번은 애초에 엄청 어려운 문제였다.
2번은 애초에 엄청 어려운 문제였다.
3번은 애초에 엄청 어려운 문제였다.
4번은 애초에 어ㅓㅓㅓㅓㅓㅓㅓㅓㅓㅁ청 어려운 문제였다.

???

솔직히 말해서 사람들이 일단 3번은 다 기본으로 맞고, 1번 풀면서 200점 이상 맞으면서 나오지 않을까 싶었는데 나중에 보니까 3번을 만점 받은 사람이 나밖에 없더라. 그 외에는 1번을 만점 받으신 분이 한명 계셨다. 복잡한 자료구조 + 계산기하 문제였다고 한다. (찬양..)

되게 얼떨떨했다 평생 해본적이 없던 경험이니까. 그 이후로 계속 정신이 멍했다 내가 뭘 한건지 싶고.. 스코어 합산해서 대충 맞춰봤을 때 대강 전체 3등 정도의 성적이었다. 정신이 없을 수밖에 없다 ^^;

사실 워낙에 경쟁적인 파트가 개입을 많이 하는 시험이다 보니까 다른 참가자의 얘기를 꺼내기가 힘든데 내가 항상 잘한다고 동경하던 분들이 의외로 정신적인 부분에서 많이 지쳐서 몰락한 부분도 상당히 컸다고 생각한다. 사실 문제들이 그럴만도 했던게, 1번에서 나와 비슷한 생각을 한 사람이 꽤 있었을 테고, 2번을 빠르게 긁는데는 무려 실수연산이 (…) 필요하며 (적어도 난.) 3번의 서브태스크가 굉장히 정신없게 주어진 까닭에 긁다가 멘탈 깨질 가능성이 충분히 존재..

정신적인 부분이 참 애매한 부분이다. 사실 결국 실전 짱을 뽑는게 목적이니 당연한 부분이기도 하지만, 그렇다고 하더라도 누구나 안타까워 할수밖에 없는 부분... 사실 내가 만약 3번을 못 풀었다면 나도 정신적인 부분에서 몰락하고 망했을 가능성이 있다고 생각한다. 전체 4등은 침착하게 1,2,3번 문제를 긁었는데 그것만으로도 상당히 훌륭한 성적을 냈다. 그런데 정말 잘하는 사람 중에서도 2번을 40점 긁지 못한 사람들이 수두룩하니.. 아무튼 안타까운 부분인 거 같다 누가 뭐래도.

끝나고 나서는 꽁짜 고기를 얻어먹었다. 여기서는 또 가방을 두고왔다는 둥 말도 안되는 헛소리를 지껄여서 민폐를 끼쳤다 (다시한번 주위분들께 죄송합니다 (__) ) 확실히 정신이 없긴 없었던 상황이었던거 같다. 물론 그건 핑계고 내가 원래 바보일 가능성이 더 높지만 ㅎㅎ

급하게 마무리를 짓자면, 작년 이맘때에 코이스터디 하면서 랭킹 오른다 으허허헣ㅎ 할때는 상상도 못했던 걸 이뤄내서 너무 기쁘다 사실 정말 다 꿈만 같고 으으.. 물론 아직 공식 결과가 발표되지 않은 이상 모두 다 김칫국 마시기 이상도 이하도 아니지만. 나보다 뛰어난 사람들에게 미안해서라도 앞으로 열심히 해야하지 않을까 싶다. 똥글 봐줘서 미안해요 열심히 할게요.

[3/6 추가 : 결국 최종발표 떴습니다. 합격으로. 지켜봐주신 모든 분들께 그저 감사하다고 밖에 말씀드릴 수가 없네요. 열심히 하겠습니다.]