ACM ICPC 2016 본선 후기

대회 결과 : http://icpckorea.org/2016/REGIONAL/scoreboard.html
우리 팀은 Korea University 'Never Give Up'이다.
결과는 4th place 금상인데 비공식 등수는 전체 6등이다. 1,2,3등이 서울대, 4등이 KAIST, 5등이 National Taiwan University, 6등이 우리.

우선, 원철이가 좋은 곳으로 숙소를 예약해주어서 엄청 편하게 대회 전날 잘 수 있었다. 여러모로 편하게 대회에 임할 수 있도록 많이 도와준 원철이에게 정말 고맙다. 5시간, 6시간 총 2번에 걸쳐서 11시간 숙면을 하고 아침을 간단히 먹고서 대회장으로 향했다.

소음이 많아서 피곤해질까봐 가져온 귀마개를 쓰고 최대한 에너지를 아끼려고 노력했다.

대회가 시작하고 G번을 읽자마자 5번째로? 맞추어서 시작이 좋았다.

나는 G를 읽고 J, D, K, F, A를 읽었다.D를 읽었는데 해석이 잘 안되어서 K를 읽었는데 예전에 인터넷 예선이 끝나고 재현이 블로그에서 봤던 LR 플로우로 푸는 문제인 것 같아서 우선은 넘겼다. 왜냐하면 내가 미처 팀노트에 그 방법을 적어오지 않았기 때문이다.

J를 읽었을 때에, 다각형들의 꼭지점이 주어져있을 때에 다각형을 복원하는 문제를 전에 풀어봤기 때문에 치환하려고 노력하였으나 실패하였다. 여기서 소요된 시간이 1시간 정도이다.

A를 읽었을 때에, 평면 그래프인 성질을 이용해서 무언가 해야할 것 같았는데 1시간을 고민해도 모르겠어서 일단 어렵다고 표시를 해둔 후, 다른 팀원들이 풀 문제가 없을 때 보여주어야겠다고 생각을 했었다.

F를 읽었을 때에, 메테오가 날아오는 방향이 왼쪽인지 오른쪽인지에 따라 경우를 나누어 주어진 건물들을 convex하게 바꾸고 이분탐색하는 방법을 생각하였는데, 양 끝에 긴 다각형이 있어서 사다리꼴로 convex해지는 경우에는 O(N^2)의 수행시간이 걸린다는 걸 깨닫고 분할정복 식으로 해야겠다고 생각을 했었다. 그런데 이미 구현한 방향은 그 쪽 방향과는 거리가 멀어서 sqrt decomposition으로 하면 되지 않을까 생각하였지만, Rikang형이 D번과 K번의 나름 정확한 풀이가 있다길래 D번 짜는 것을 도와주기로 하였다.

D번에서 이분 매칭 후 최소 버텍스 커버를 구하는 부분만 구현해주었고, 한 번의 실수 후 맞출 수 있었다.

K번을 Rikang형 아이디어대로 MCMF로 짜는 도중에 창수가 틀렸던 E번을 수정하였고, K번은 다 짰는데 Runtime Error가 발생하였다. 못 고치고 끝났는데, 대회 끝나고 후문을 들어보니 MCMF로는 어떻게 짜던 TLE가 나고, 재현이나 명우 블로그에 있는 LR 플로우나 일반적인 플로우를 구현해야된다고 들었다.

그렇게 대회가 끝나고 최종 결과를 보니, 대전 리저널 결과만 놓고 보면 카이스트와 패널티 90 차이로 월드파이널에 못 나간다. 너무 안타까웠고 속상했다. 무엇보다 내가 아무것도 할 수 없었고, 해낼 수 없던 상황이 너무나 싫었다. G를 읽고 승재형이 보았던 빨리 풀 만한 문제들 몇 개를 내가 읽었다면 패널티를 정말 많이 낮출 수 있었을텐데ㅠㅠ 팀노트를 성실하게 준비하지 못했던 것도 너무나 마음 아팠다.

국내에서 3등을 했고, NTU는 아마 자국 대회에서 NTU가 1등해서 티켓을 가져갈 것이기 때문에 우리나라 티켓에는 아무 영향도 안 줄 것 같지만, 불가피하게 필리핀 리저널에 가서 티켓을 따와야 하는 상황이다. 남은 기간 열심히 준비하고, 학교 공부랑 과제도 미리미리 해서 좋은 결과가 있으면 좋겠다.

솔직하게 정말 열심히 준비했고, 노력도 많이 해서 속상하다. 내 주제에 무슨 월드파이널을 가겠어 싶었는데 가고 싶다ㅠㅠ
삼성 대회 본선에서 상을 받았을 때에 부모님이 정말 좋아하셨는데... 생각해보니 성과 없는 아들을 묵묵히 지원해주신 부모님께 정말 죄송하고 감사하다.

글 막판에 감성 좀 팔아봤는데 너무 피곤해서 이런 저런 지인들과 관련해서 느낀 점이 너무나 많지만 오늘은 이만 써야겠다.
점점 나아지는 결과를 얻고 있으니, 필리핀 리저널에서는 팀워크가 빛을 발하길 바라며 이만.