2017 ACM-ICPC Daejeon Regional 인터넷 예선 후기

2016년 3월 PS라는걸 처음 알게 되고 ,2016년 8월 처음으로 이걸 제대로 공부해 봐야겠다는 생각이 들었고, 2016년 12월 블로그 이름을 ACM-ICPC 상 탈 사람이라고 달아버리고, 마침내 어제 목표로 하던 ACM-ICPC 대전 리저널 본선으로 가는 티켓을 따기 위한 인터넷 예선을 치루게 되었다.

SCPC, 카카오 코드 페스티벌 등.. 이제 대회 경험이 꽤 생겼지만 이렇게 가슴이 떨린적은 처음인것 같다. 처음부터 이 대회를 목표로 공부를 시작하였으니 그런듯 하다 ..

2시에 대회가 시작된 뒤 등록 문제가 바뀐 걸 인지 못해서 엉뚱한 답안을 작성할 뻔 했지만 팀원들이 잘 지적해주어서 제대로 고쳐서 냈다.

초반 스퍼트는 굉장히 좋았다.. 아니 솔찍히 기대 이상이였다. 우리가 4문제를 풀어낸 시간이 고작 27분 밖에 안걸렸으며 4문제를 풀었을 때 우리의 전국 등수는 9등이였다.

무려 2시간 반이나 남아있었기 때문에 원래 목표로 했던 6~7문제에 도달할 수 있을것이라고 생각하였다. 하지만 너무 빠르게 문제를 푸니 단점이 있었다. 다음으로 어떤 문제를 잡아야 할지가 고민이었다.

우리가 막 4문제를 푼 순간에는 오직 서울대 ACG팀만 5문제를 풀었으며 ACG가 푼 G번 문제는 갓 ACG님들이 무려 2번이나 틀렸었다.. 그래서 이걸 도전해야되나 딴 문제를 찾아야되나 고민이 되었다. 어느정도 시간이 지난 후 카이스트의 구사과님팀이 L번을 풀었다. 

하지만 이 문제 또한 구사과님 팀을 제외한 다른팀들이 도전을 안했기에 조금 생각을하다가 우리팀은 E번을 잡게 되었다. E번은 기하+네트워크 플로우 문제였다.

플로우 모델링 자체는 정말 쉬웠지만 우리팀이 기하에 너무 잼병이라 CCW로 판단할 수 있을거 같았지만 정확하게 정의하지 못해서 두 직선에 대한 방정식을 세워서 교점이 직선위에 있냐로 판단하기로 하였고, 이 때부터 우리팀은 분업을 하게 되었다.

팀원 일호는 다른 문제를 읽고있었고, 팀원 정률이는 위에 정의한 풀이를 수식으로 정리하였고, 나는 디닉을 짰다.

이후 수식이 다 작성이 되었고 E번 소스를 1차적으로 작성하였지만 플로우 소스에 오타가 있었는지 실수가 있었는지 무한루프가 돌아버렸다.

그리고 스코어보드를 한번 보고나니 G번 문제가 생각보다 많이 풀려 있었다. 

이 때 나는 잘못 된(?)판단을 하게 된다.ㅋㅋㅋㅋㅋㅋㅋㅋ 네트워크 플로우 디버깅을 하는데 시간이 오래 걸리니 많은 사람들이 푼 G번을 먼저 풀고 E번 디버깅을 해보자라며 정률이를 설득하였고 G번을 읽기 시작하였다.

G번 문제를 읽고 n^2 디피임은 확실히 알 수 있었다. 디피에 자신없긴 했지만 대략적으로 점화식을 세우고 일호와 내가 연속해서 트라이를 하였다.. 

하지만 결과는 계속되는 WA .. ㅠㅠ

G번에서 정말 시간을 많이 말아먹고나니 E번을 그냥 풀걸 이라는 후회도 들고.. 다행히 인하대의 다른 팀들도 진전이 없어보여서 .. 프리징 된 시점에서는 그냥 G번을 풀고 본선가자는 마인드로 계속 도전하였다.

뭐 결과는... 결국 G번을 못풀게 되었다.

프리징이 풀린 스코어보드를 보고나서 깨달았다.. 당했다는걸 ........

프리징 이후로 5문제를 푼 팀이 꽤나 많았는데 그 팀들중 대부분은 C나 D문제를 풀었다. 하지만 우리는 상위 스코어보드만 보고 C나 D문제는 읽지도 않았다 ... 

정말 문제를 잘골라야 한다라는 교훈을 얻게 되었다.. 아니 차라리 E를 잡고 늘어지기라도 했으면 ..ㅜㅜ 

생각해보면 E는 풀이가 확실하였지만 G는 풀이에 대한 확신이 없었다.. 한 문제를 잡고 늘어지지 않아야 한다는 교훈 또한 얻게 되었다 ㅋㅋㅋ 

그래서 최종 결과는 4문제를 푼 모든 팀들 중에 1등을 하게 되었다.

사실 만족스러운 결과는 아니다. 2시간 반이라는 엄청나게 긴 시간 동안 한문제도 못풀었다는 거니까 .. 하지만 이번 예선 대회로 인해 많은 교훈을 얻었으니 그걸로 된 것 같다.

그리고 인하대에서 1등을 하게 되어 우선 대전 리저널은 확실하게 진출하게 되었다..

5문제나 6문제를 풀고 진출하였었다면 훨씬 기분이 좋았겠지만 대전에 간다는 사실만으로도 충분히 설렌다.

뭐 본선때 그팀들을 다 앞지르면 되니까 말이다 ㅎㅎ..

이제 정말 얼마 남지 않았다. 남은 기간동안 정말 열심히 준비해서 꼭 대전 리저널에서 좋은 결과를 얻어보고 싶다.

).. 그리고 여담으로 팀노트 공간이 부족해서 FFT가 설마나오겠어 하고 팀노트에서 제외해버렸는데 FFT가 나왔다... 구사과님의 팀이 퍼솔한 L번 .... 작년의 l-r flow처럼 대전에서 또 한번 등장할까봐 겁난다.. FFT를 준비해야하나 ..?