IOI 2017 후기

처음 나가는 IOI라서 되게 설레기도 하고 긴장도 조금 됐는데 완벽하지는 않지만 그래도 내 당시 상태에서 할 만큼은 하고 온 것 같다. 새롭고 다시는 해 보지 못할 경험을 많이 했다는 점은 되게 좋은 것 같다.

IOI라고 해서 대회 환경이 좋음이 보장되는 것은 아닌 것 같았다. Practice session 초반에 채점이 안 되는 것부터 뭔가 낌새가 이상했는데, Day 1때는 대회 시작 시점에 문제 pdf가 올라와 있지도 않았으며(프린트된 문제가 있어서 상관은 없었지만) 중간에 채점 큐가 조금씩 밀리기도 하고 Day2 때는 채점이 아예 안 되던 시점도 있었다. 이런 상황에서 굳이 연습할 필요까지는 없지만 제출을 좀 더 신중하게 쓰는 연습은 분명 필요한 것 같다.

내 최대한의 실력을 발휘 못 한 것 같아 아쉬웠다. 두 날 모두 매 순간 판단 자체는 잘 했는데, (첫날 nowruz를 긁고 wiring을 잡는 판단, 두번째 날 prize부터 풀고 simurgh, books를 긁은 뒤 books를 풀려는 판단 모두 내 당시 상황에서 최적의 판단이었다) 생각이나 코딩이 마음처럼 안 따라줬다. 첫날 nowruz에서 BFS를 생각 못한 것, wiring에서 N^2 DP 짜다가 말린 것, 둘째날 prize, simurgh 디버깅하다가 시간 날린 것 중 한 두개만 제대로 했어도 금이었다는 생각에 아쉬움이 많이 들기도 했지만 이미 지나간 일인데 어쩌겠는가.

Day1은 섭테 점수가 비상식적으로 짰다고 생각한다. Wiring과 train 모두 마지막 섭테에만 50점 가량 달려있는 걸 보고 ‘JOI Spring Camp인가’하는 생각이 들 정도였다. 물론 일단 섭테가 그렇게 나온 상황에서는 못 푼 내가 잘못이다 ㅠㅠ

Day 2는 좋은 셋이었다고 생각한다. Day1과 같은 대회 셋이라는 게 믿기지 않을 정도였다. Interactive 문제들이 모두 재미있는 아이디어를 요구했고, books도 여러 관찰들을 통해 복잡한 코딩 없이 풀 수 있었다.

Day1 때문에 결과적으로 금컷이 역대급으로 낮아졌다(353.04였나?) 놀랍게도 내가 두번째 날 simurgh를 풀었으면 은탑, books를 풀었으면 금꼴이었다… 물론 난 둘 다 못 풀어서 40등이다.

문제가 전체적으로 복잡한 코딩보다는 아이디어를 요구하는 스타일이었던 것 같다. 어떻게 하면 말랑말랑한 머리를 가질 수 있을까 ㅠㅠ

문제를 풀고 못 풀고는 실력이니 결국 평소에 문제를 많이 푸는 것 밖에 답이 없다. 거기에 더해 IOI 대회장에서 참가자 입장으로 할 수 있는 최선의 전략은 ‘문제/섭테 난이도 빨리 알아보기’, ‘(둘째 날의 경우) 상위 메달을 따려면 어느 문제/섭테를 풀어야 하는지 알아보기’ 정도가 될 것 같다. 올해 결과로 알 수 있듯이 말리는 경우에 이런 전략이 매우 중요해진다. 개인적으로 국대 교육이 좀 더 실제 OI스러운 분위기가 되면 좋을 것 같다. (그러면 분위기를 잡을 조교가 필요한데…. ㅠㅠㅠ)

내년 IOI는 일본에서 열리는 만큼 문제 퀄리티는 기대해도 좋을 것 같다. (이미 JOI Spring Camp 셋만 해도 웬만한 IOI 셋 뺨친다) 내년 국대들은 일본 스타일 문제 잘 푸는 학생들이 나가면 잘 하겠지..?

정보를 하는 사람 입장에서 IOI는 꼭 참가자가 아니더라도 참여하는 것만으로 되게 재미있는 것 같다. 기회가 되면 조교로 가서 문제 번역 같은 것도 해 보고 싶다.

첫 번째 문제(Nowruz)가 output-only일 때부터 조짐이 안 좋았다. 나머지 두 문제를 보는데 wiring은 쉬운데 나한테만 어려운 문제 같았고 train은 게임 문제라서 머리가 아팠다. 한 문제도 못 풀 수도 있겠다는 생각이 들었는데 그런 생각은 일단 하지 않기로 했다.

그래도 nowruz가 좀 하면 점수가 나올 것 같아서 먼저 잡았다. 십자가 모양을 dfs하면서 적당히 뿌려주는 방식으로 코드를 짰더니 55점 정도가 나왔다. (사실 대회 중에는 점수 합산이 안 됐어서 정확히는 모른다) 그 이상 점수를 받는 것은 일단 생각이 잘 안 나서 이쯤 하기로 했다. 이 때가 1시간 30분? 정도였다. 그 때까지는 괜찮았던 것 같다.

Wiring을 그 다음으로 잡았는데 1도 모르겠었다… 7점 섭테가 n^3 dp인 것 같은데 그것도 모르겠어서 이 때 쯤부터 약간 “망했다”라는 생각이 든 것 같다. 그래서 중간에 train 5점 섭테를 긁고 오니까 이번에는 n^2 dp가 생각났다(??!) dp식이 정말 예쁜데, D[i][j] : (왼쪽에서 i번째 빨간점, j번째 파란점까지 매칭했을 때 최소 비용)이라고 하면 D[i][j] = min{D[i-1][j], D[i][j-1], D[i-1][j-1]}+abs(x[i]-y[j])이다. 이걸로 어떻게 비비니까 제약 조건이 달린 총 30점짜리까지 긁을 수 있었다. 사실 여기서 dp식이 LCS랑 비슷하다는 걸 보고 방향을 틀었으면 좀 나았을 수도 있는데 나는 이걸 줄이려고 시도하다가 결국 망했다. 맞는 줄 알았던 관찰이 사실 완전 틀린 거라는 걸 끝나기 1시간 전 쯤에 깨닫고 train을 긁으러 갔다.

Train의 11점짜리 섭테 두 개가 각각 A, B가 모든 역을 가진 경우여서 좀 쉬웠는데, 둘 다 코딩을 했는데 SCC로 접근을 하다 보니 예외 처리가 좀 까다로워서 마지막 1시간을 통째로 train에 쏟아붓고 결국 둘 중 하나만 긁었다.

“그래도 5시간 동안 한 문제는 풀겠지”라는 생각으로 들어갔는데 그게 무참히 깨지고 나니까 약간 충격이었다. 다른 친구들 점수를 물어봤는데 제연이는 그래도 wiring을 풀어서 좀 나았지만 현수와 규호는 나보다 더 상황이 안 좋았다. 나 빼고 다들 nowruz가 20점대인 게 좀 컸고, 규호는 그래도 2, 3번을 나름 긁을 만큼 긁었는데 현수는 완전히 말린 것 같았다. 심지어 서브태스크 점수가 엄청 짜서 못 푼 문제는 많이 긁어봐야 20~30점이어서 되게 심각한 상황이었다. 나와서 스코어보드를 보니 아주 가관이었다. 금컷이 160, 은컷이 100 언저리였는데 내가 은컷 거의 바로 밑이었다. 그래도 이렇게 되면 Day 2 때 뒤집을 수는 있다는 생각으로 대충 멘탈을 챙겼다.

문제를 읽었는데 오늘은 인터랙티브가 두 개나 있었다… 나머지 하나는 뭔가 day 1 wiring과 비슷한 느낌이었다. 그래도 인터랙티브면 점수를 아예 못 받지는 않겠다는 생각이 들었고, 섭테도 day 1보다 훨씬 후해서 일단은 안심이었다.

Books를 일단 먼저 생각해 보기로 했는데 처음에는 아예 모르겠었다. 뭔가 대충 짜서 냈는데 n=4인 섭테도 틀리길래 이러면 안 되겠다고 생각하고 일단 접었다.

Prize가 쉬워 보이길래 잡았는데 섭테가 20 / 90 / (소수점) ~ 100 이렇게 된 걸 보고 처음에 잘못 읽었나 싶었다. 일단 90점을 빨리 받고 던지자는 생각으로 잡았고, 제일 싼 게 아닌 상품이 최대 O(루트n)개 있다는 것을 관찰하니 O(루트n*logn) 풀이가 떠올랐다. 그런데 처음에는 이상한 이분탐색을 짜서 상수가 컸는지 계속 20점이 나왔다. 중간에 풀이를 2~3번 갈아엎었는데 계속 20점이길래 “말린 건가”하는 생각도 약간 들었지만 침착하게 풀이를 다시 생각한 결과 상수가 적은 분할정복 풀이를 짜서 90.64점을 받았다. 그 다음에 코드를 좀 고쳐 보면서 95.7, 95.87을 거쳐서 100점을 띄우고 넘어갔다. (끝나고 나서 알았는데 이 때 조교형들한테 까였다… 사실 까일 만 했는데 나는 원래 그런 걸 최대한 할 수 있는 걸 안하고 넘어가면 계속 신경 쓰이는 타입이라 어쩔 수 없었다. 10분도 안 썼어서 다행이다)

Simurgh 51점 풀이는 “각 간선이 왕의 길에 속하는지 여부를 O(1)만에 알아내자”라는 생각으로 접근하고 dfs tree에서 생각을 하면 금방 나온다. 처음에 절선 BCC로 이상한 걸 하려고 했다가 안 된다는 걸 깨닫고 dfs tree로 넘어간 게 다행이었다. 그런데 디버깅이 내 발목을 잡았다… 아무리 해도 51점이 안 나오길래 끝나기 1시간 전 쯤부터 “좀 아니다” 하고 books로 넘어갔다.

Books를 다시 보니 이번엔 뭔가 길이 보였다. 그리고 이 때 쯤에 뭔가 채점 시스템 문제로 인해 대회가 15분 연장됐어서 마음이 좀 편해진 것도 있었다. 그런데 좀 고쳐서 내도 계속 12점만 나오길래 대회 종료 15분 전 (이 때 기준으로는 대회 시작 5시간 때쯤) 에 simurgh로 다시 넘어갔다.

이 때 내 코드에서 중요한 예외 처리 하나를 안 한 것을 발견하고 그걸 고쳐서 내니 51점이 떴다. 이 때가 5시간 3분이었던 것 같다. 그리고 나서 books도 뭔가 하나를 더 고쳐서 내니 50점이 떴다. 5시간 11분에 그걸 띄우고 나니 갑자기 15분이 더 연장됐다(?!)

Simurgh 70점과 books 100점 중에 하나를 선택해야 했는데 books를 풀면 금, 못 풀면 은이라는 생각이 들었고, (놀랍게도 완전히 정확한 판단이었다) books를 마지막으로 잡았는데 s가 0이 아니면 s를 포함하는 사이클 구간에 대해 50점 풀이와는 다르게 처리를 해야 하는데 그걸 캐치를 못 해서 결국 201점으로 대회를 마무리했다.

끝나고 나서 보니 제연이는 books를 풀어서 250점으로 잘 봤고, 규호도 마지막에 simurgh를 풀어서(!!) 202점으로 잘 봤다. 현수는 아쉽게도 simurgh를 풀다 말렸다..

스코어보드가 업데이트 된 후 최종 결과는 1금(제연) 2은(나, 규호)이다. Day 1에서 말아먹은 걸 Day 2에서 나름 커버를 친 것 같아 다행이었다. Day 2 스코어보드만 보니 3금(!!)이라서 “Day 1 날아가면 3금이네” 이런 농담도 하고 그랬다.

대회가 이란에서 열린다고 해서 가기 전에 엄청 걱정했었는데 실제로 가서 보니 별로 위험하지는 않았다. 거기 가이드들이 계속 ‘이란이 중동에서 제일 안전한 나라임’하고 엄청 강조했는데 맞는 것 같다. OI는 전에도 여러 번 참여해 본 적이 있었지만 이번처럼 ‘국가 대표’로 선발돼서 온 적은 처음이라 엄청 긴장할 줄 알았는데 대회장에 앉으니까 그렇게 엄청 긴장이 되지는 않았다. 물론 대회 말리는 건 긴장과는 무관하다 ㅠㅠ

개인적으로는 은메달을 받은 것이 불만족스러운 일은 아니지만, 또 올해 우리나라 결과를 절대 ‘못 했다’라고 말할 수는 없다고 생각했지만 우리나라 특성상 메달 색을 엄청 중요시하기 때문에 약간 불안하기도 했다. (실제로 한국 와서 메달 색 얘기가 몇 번 귀에 들렸는데 아직까지는 걱정했던 만큼은 아니었다)

시설은 전체적으로 괜찮았다. 방도 깨끗하고, 벌레도 안 나오고, 밥도 (입맛에 맞는 거만 골라 먹으면) 맛있었다. 음료수 중에는 무려 바질 씨 음료도 있었다!! 그리고 IOI 측에서 호텔 내에 Xbox랑 보드게임 같은 걸 비치해 두어서 호텔 안에서도 재미있게 놀 수 있었다 ㅎㅎ

Excursion은 솔직히 말하면 별로 볼 게 없었다…..ㅠㅠ 여기저기 많이 가기는 했는데 뭔가 확 인상이 남는 건 없었다. 플라네타리움은 진짜 지루했고, 궁전, 식물원 등 밖에서 돌아다녔던 프로그램은 더웠다는 것밖에 기억이 안 난다. 일정이 맨날 딜레이돼서 좀 답답하기도 했다. 그래도 신기한 점이 몇 가지 있었는데, 일단 버스 안에 물 냉장고가 있다. 나는 원래 물을 잘 안 마시는데, 물을 안 마시고 밖에 몇 시간 돌아다니니까 목 말라 죽을 뻔했다. 날이 워낙 건조하다 보니 물을 자주 마셔줘야 되는 것 같다. 그리고 이란에서는 아라비아 숫자를 안 쓰고 자기들 숫자를 쓴다. 10진법으로 0~9를 쓰는 건 똑같은데 모양이 좀 다르다. 그리고 이란에서 삼성이랑 LG가 엄청 유명한 것 같다. 공항에도 대문짝만한 광고가 있었고, 무엇보다 정말 신기했던 건 어느 거리에 삼성 전자제품 판매점이 수십개가 넘게 거의 연속해서 붙어있는 것이었다. 처음에는 한 블록 정도 떨어져 있길래 ‘되게 많네…’정도로 생각했는데 나중에 가니까 거의 10개 정도 되는 가게가 붙어있었다. 도대체 어떻게 안 망한 건지 모르겠다.

가이드 이야기를 안 할 수가 없다. 여자 분이셨는데 한국을 엄청 좋아한다고 했다. 핸드폰에 한국 아이돌 노래가 진짜 가득한 걸 보고 엄청 신기했다. 내가 낯을 엄청 가려서 처음에는 그냥 별로 교류를 안 하려고 했는데, 그 분이 진짜 많이 챙겨주고 우리랑 친해지려고 하는데도 별 반응을 안 하니까 넷 중에서 그나마 얘기가 통했던 제연이하고만 말을 했다. 그걸 보고 있자니 내가 외국까지 와서 이렇게 아무하고도 인연을 못 만들고 가야 하나라는 생각도 들고 무엇보다 가이드분이 너무 우리를 좋아하고 잘 해줘서 내가 가만 있는게 미안한 생각이 들었다. (그 분은 맨날 아침 일찍 일어나 우리 방 앞으로 와서 깨워주시고 평소에도 뭐가 있으면 항상 먼저 가서 챙겨주시고 했는데 다른 가이드는 그냥 팀 학생들 끌고 다니는 정도만 하고 그랬다) 그래서 한 셋째 날 부터는 없는 말주변을 끌어모아 이야기도 많이 하려고 노력했다. 그래서 Excursion 중에는 (하는 게 재미없기도 했지만) 가이드랑 같이 다니면서 이야기를 듣는 게 제일 재미있었던 것 같다. 나랑 제연이는 Excursion을 다 따라다니면서 가이드와 친하게 지냈고, 규호와 현수는 상대적으로 덜 친하게 지냈는데, 그래서인지 가이드가 (나랑 제연이랑만 있을 때) 그 둘에 대한 불평을 좀 했던 것 같다 ㅎㅎ.. 그리고 가이드가 맨날 우리 둘한테 ‘노래 불러줘’, ‘춤 춰줘’ 하면서 그걸 동영상으로 찍으려고 했는데, 그거는 계속 거절하다가 마지막 날 밤 마지못해 했던 것 같다 ㅋㅋㅋ 가이드분이 마지막 날 되니까 울려고 그러셔서 기분이 좀 그랬다…마지막날 밤 이것저것 많이 하면서 얘기를 되게 많이 했었는데 나랑 제연이가 자기 동생 같다면서 가는 걸 엄청 아쉬워했다. (진짜 신기했다…) 한국 돌아오고 나서도 가끔씩 연락을 하고 있다.

대회 참가자들과 인연을 쌓지 못한 건 좀 아쉬웠다. 그래도 유타(올해 탑골드) 한테 기념품 나눠주면서 얼굴도장 찍고 미국에서 혼자 온 애하고도 사진찍고 (미국하고 이란하고 뭐가 있나? 해서 미국에서 혼자 와서 3등하고 가는 거 보고 되게 멋지다고 생각했다) 전 세계에서 내로라하는 학생들 얼굴을 엄청 많이 볼 수 있었다는 점에서 만족한다. 오히려 참가자들하고는 규호가 같이 사진 찍고 다니면서 제일 교류 많이 한 것 같다.

폐회식 날 뭔가 카메라가 날 비추길래 인사했는데 (그 때 표정이 되게 이상했다) 그게 CNN 뉴스에 (한 3초 정도) 떡하니 나와버렸다… 심지어 뉴스 내용은 미국 이란 간 갈등 때문에 미국에서 혼자 온 참가자 관련 내용이었다. 뉴스에 내가 나온 걸 보고 ‘표정관리 좀 할걸..’하는 생각이 들었다. 그래도 우리나라에서 CNN에 단독샷으로 출연해 본 사람이 얼마나 되겠는가! ㅎㅎ

이란에서 얻어온 전리품(?) 중 제일 마음에 드는 것은 멕시코 팀이 준 엄청 큰 밀짚 모자였다(???) IOI 측에서도 기념품을 엄청 많이 주기는 했는데, 다 나한테는 별로 필요 없는 거라서 IOI 티셔츠, 가방 정도만 좋았다. 멕시코 모자는 학교에 가져오려고 하는데 계속 까먹고 있다…

문제가 어땠든, Excursion이 구렸든 어쨌든 IOI에 Contestant로 참여하는 것은 두 번 다시 못 할 소중한 경험이므로 평생 잊지 못 할 것 같다. Call for tasks에 문제를 내든 조교로 같이 따라가든 앞으로 있을 IOI에도 참여해보고 싶다.