IOI 2015 후기

페북에 굴러다니던건데

http://tncks0121.tistory.com/ 블로그 주인장 분의 "강력한" 건의로 인해 블로그에도 올리게 되었다.

덧붙이고 싶은 내용들을 조금 추가했다.

문제 후기 말고 대회 후기도 써야 하는데 안썼다.

아마 안쓸듯. 나새끼..

boxes
제일 쉬워보였고 실제로도 쉬운 문제였습니다. 일단 O(nk) dp를 빠르게 코딩하고, 그리디 전략과 섞어서 O(n)에 해결했습니다. n이 천만으로 매우 큰데 나름 시사하는 바가 있다고 생각합니다.

(소스 : http://oj.uz/submission/16536)

scales
빠르게 머지소트 55점 풀이를 코딩하고 3번으로 넘어갔습니다. 71점 풀이는 처음반때 decision tree 배울때 생각했던 풀이로 애석하게도 바로 떠오르진 않았습니다 (그랬으면 짰을듯..?) 100점 풀이는 720/729로 허투로 쓰는게 하나도 없어야만 하는 tight한 풀이고, 아마 마라톤 매치 스타일로 푸는 거 같습니다.

(9.27 추가 : 제가 들은 100점 풀이는 branch-and-bound 풀이였는데 백트래킹이 나온것도 조금 충격이었고 커팅이 잘 되는 것도 조금 충격이었습니다. 이런 문제가 ioi에 나와야 하는지에 대해서는 아직도 약간 반신반의하는 바지만 어쨌든 흥미로운 문제라고 생각합니다. 아마 대회였다면 죽었다 깨어나도 이 문제 100점은 못 맞았을 거 같습니다. 위에서 얘기했던 71점 풀이는 코딩하는데 조금 시간이 걸리더라고요. 진짜 teams를 풀 생각이 있었다면 대회 당시에 16점을 버린 건 괜찮은 선택이었다고 생각합니다.)

(소스 : http://oj.uz/submission/16540)

teams
34점 풀이는 유명하죠. 이거 짰을때가 110분째인데 순간적으로 개인 2등이었다고 합니다. 헐..

남은 3시간을 어떻게 보낼까 고민하다 teams가 풀릴법하다 생각해서 모든 시간을 할애했습니다. 그렇게 2시간 넘게 많은 디버깅과 시행착오를 거친 후, 풀이의 틀린 점을 발견했습니다. 남은 시간이 45분 가량이었는데 이때 열심히 붙잡고 몇가지 부분을 고쳐봤지만, 딱히 효과는 없었습니다.

대회 후에 생각해보면 제가 100점을 맞기는 너무 어려운 문제였다고 생각합니다. 차라리 처음부터 77점을 노렸으면 승산이 있었다고 생각하지만 시작할 때는 제 풀이에 지나치게 확신이 있던게 문제였던 거 같습니다. 이런 적이 한두번이 아니었던 거 같은데.. 아무튼 여기서 3시간동안 이득을 못본게 아쉽습니다. 

(9.27 추가 : 계절학교에서 IOI 2015 모의할때 AC 낸 문제입니다. IOI와 합쳐서 생각하면 5시간 조금 넘게 쓰니까 풀리더라.. 라고 결론지을 수 있겠습니다. 자료구조 잘하는 줄 알았는데, 이번 IOI에서 말린 문제들을 뜯어보면 모조리 자료구조였네요. 더 공부해야겠습니다 ㅠㅠ)

(소스 : http://oj.uz/submission/16550)

horses
다들 주는 문제라고 했는데 저한테는 너무 어려웠습니다. NlgXlgN으로 set + 인덱스트리 2개 잡고 dp 역추적하는게 제 풀이이며 역시 디버깅하기도 조금 힘들었습니다. (알고보니 등호 미스..) 결국 끝나기 40분 쯤 전에 풀었고요. 이번 대회에서 boxes보다 쉬웠다는 결론은 제 입장에서는 조금 충격적이었습니다. 금메달을 놓친 가장 큰 원인이 된 문제라고 생각합니다 (ㅠㅠ) 풀어서 다행입니다.

(9.27 추가 : 계절학교때 금방 풀었습니다. 제가 당시 인덱스트리 고치기 귀찮아서 dp 역추적 했던거로 기억하는데... 하 나새끼... 이 문제에 대한 미련은 앞으로도 더 남을 거 같습니다 ㅋㅋㅋㅋㅋ)

(소스 : http://oj.uz/submission/16557)

sorting
처음 봤을때는 숨이 턱 막히는 문제였지만 돌아보면 horses보다 쉬웠습니다. 삽질을 조금 하다가 적절히 잘 작동하는 NM (54점) 풀이를 작성하고, horses를 풀고 오니까 처음에 안된다고 했던 파라메트릭이 되더라고요?! 이후 루틴을 Nlg^2N으로 줄여서 최종적으로 100점을 받았습니다. 제 풀이를 NlgN으로 줄이기는 쉽습니다.

(소스 : http://oj.uz/submission/16564)

towns
생각을 조금 해봤는데 25점 풀이에도 아무 생각이 안 났습니다. 이것저것 시도해봤는데 다 반례가 나오거나 도움이 안됐다는.. 0점으로 마무리하게 된 건 저한테도 조금 충격적이었습니다. 끝나고 나와서 트리의 지름에 대한 시도는 사실 반례가 아니었다는 걸 듣고 왔습니다 (ㅠㅠ) 아무튼 재밌는 문제라고 생각하며 돌아가서 풀어볼 예정입니다.

(9.27 추가 : 계절학교때 한 3시간 정도 쓰니까 61점 풀이가 나왔습니다. 하지만 majority algorithm 스포를 들은 이후의 얘기인지라 대회장에서 시간이 주어졌을 때 48점 이상 맞을 수 있었을까..? 하면 가능성이 낮다고 생각합니다. 남은 39점은 ioi 같이 나갔던 myungwoo 조교님에게 스포를 들었습니다. 신기하더라고요. 재미있는 문제라고 생각합니다. 여담으로 계절학교때 디스크립션 보니까, 아예 그냥 반지름 정의 주고 빨리 구하라고 써져있더라고요. 트리의 지름이 반례니 운운했던 게 이해가 안됩니다. 나새끼 (2) ......)

(소스 : http://oj.uz/submission/16587)

총평
개인 46/322로 은메달 중상위권 정도의 성적을 받았습니다. 합숙 교육동안 예상했던 성적과 동일했지만 바라던 성적은 아니었습니다. 하지만 다행히도 저는 시간이 있습니다 :) 당장의 목표는 내년에 선발되고 금메달 두개 따는 것입니다. (apio + ioi) 그리고 목표를 이루기 위해 전 귀국 다음날 여름학교로 들어갑니다 (엉엉엉엉)

이번에 대한민국 국가대표는 금3 은1로 개인 1위 보유 + 종합 1위에 달하는 쾌거를 세웠습니다. 24년 역사중 최고의 실적입니다. 올해 WF 동메달에 이어서 연이어 좋은 실적 낼 수 있었던 점, 이런 대단한 팀의 일원으로 속해있던 걸 영광으로 생각합니다.

시험 외적인 부분에 대해서는 나중에 한번 정리하겠습니다. 간략히 말하자면 매우 재밌게 지내고 있습니다 :) 남은 시간 잘 놀다 올게요.