IOI 2017 결과 및 총평

전체 결과: IOI Statistics, IOI 2017 official scoreboard

대한민국 결과: IOI Statistics

역대 대한민국 결과: IOI Statistics

2017년 국제정보올림피아드에서 우리나라는 금1, 은2라는 성적을 거둬 종합 10위에 그쳤다. 2017년도 문제들은 예년이 비해 좀 어렵게 느껴진다. 그리고 한 동안 안나왔던 Output Only 문제가 Day 1에 출제되었다.

Nowruz 문제는 2차원 격자판의 빈 칸에 적절히 장애물을 설치해서 빈 칸들이 서로 트리를 이루게했을 때, 리프 정점의 개수를 많게하면 점수를 더 받는 문제다. 김동현 군을 제외한 우리나라 대표학생들은 Output Only 문제에서 상당히 적은 점수를 받았다. 불행인지 다행인지 nowruz에서 조금 더 높은 점수를 받았더라하더라도 메달에 영향을 받는 학생은 없다.

Wiring 문제는 개인적으로 푼 사람 수에 비해 많이 어려운 문제라고 생각한다. 최적해가 $O(N+M)$이지만 $N, M \leq 100,000$ 정도의 제한을 가지고 있어서, 적절한 $O(NM)$ 커팅이나 sqrt decomposition 같은 방법으로 만점을 받은 학생도 여럿 있다고 생각한다. Scientific Committee에서 의도한 풀이를 모르겠다. 확실한 것은 N제한이 최대 100만인데, $O(N \lg N)$ 풀이를 200ms 대에 통과시키면서 시간제한이 2초인 books 문제가 있는데 wiring 문제의 N, M 제한이 최대 10만이라는 것은 의도한 다른 쉬운 풀이가 존재한다는 말이다.

Train 문제는 대회에서 만점을 받은 학생이 4명밖에 안되지만, 어렵지 않은 문제라고 생각한다. 부분문제가 나뉘어져있는 꼴은 만점 풀이 접근과 상관 없어 보이고, 부분문제 각각이 독립적인 모양을 띄어 부분점수를 올리기 위해서는 nowruz 문제처럼 시간을 꽤나 투자해야할 것 같다. 문제를 알맞게 변형하면 꽤나 쉽게 풀이를 생각할 수 있는데, 만점자 수가 적어서 의아한 감이 있다.

Prize 문제는 90점 이상을 받기는 굉장히 쉬운 문제라고 본다. 하지만 100점을 받기 위해서는 sqrt decomposition이라는 아이디어와 짜잘한 최적화가 필요하므로 어느정도 시간 투자를 필요로하는 문제다. 적당히 95점 정도의 점수를 받으면 우선 넘어가도 괜찮을 것 같아보인다.

Simugrh 문제는 굉장히 어렵다... 51점을 받기 위해서는 문제에 대해 꽤나 깊게 분석해야하는데, 내가 모르는 다른 간단한 풀이가 있는 것인지 51점 이상 받은 학생들이 굉장히 많아서 놀랐다. 51점 풀이를 어떻게 생각했느냐에 따라 100점 풀이 접근 여부가 갈라져서 만점자가 적은 것 같다. 나는 51점 풀이에 대한 방향을 잘 잡았는지, 100점으로 발전시키는 것은 어렵지 않았다.

Books 문제는 많이 알려진 "물건들고 정렬하기" 문제다. 이 때, 종종 이용했던 아이디어로 50점을 받는 것은 매우 쉽게 느껴진다. 50점 풀이를 떠올린 후 100점 풀이가 멀지 않게 느껴져서 도전 욕구를 불러일으키는 문제다. 하지만 50점 풀이에서 100점 풀이로 가는 과정에서 생각 정리가 완벽하지 않으면 꽤나 심하게 말릴 수 있는 문제이기도 하다. 풀이의 정확성을 위해 생각해야하는 경우가 많고, 한 두 가지의 예외처리 등이 포함되어 있어 완벽한 생각 정리가 필요하다.

우리나라 대표학생들의 성적을 들여다보면 Day 2 성적이 굉장히 좋다. Day 1 때 Output Only 문제와 기대보다 높은 난이도의 문제들에 놀라 당황해서 좋은 성적은 아니지만, Day 2에서는 잘 회복한 모습을 보여줘서 다행이다. Day 2 성적은 김현수 군을 제외한 세 학생의 성적에 크게 흠 잡을 곳이 없다. (서규호 군의 books 12점은 아쉽지만...)

끝으로, 전년도 대회에서는 좋은 모습을 보여줬지만 이번 대회에서 멘탈이 가루가 된 모습을 보여준 14년 만의 목메달 김현수 군에게 이 자리를 빌어 심심찮은 위로의 말을 전한다.