2020 ICPC Seoul Regional 후기

Intro

ICPC 서울리저널에서 7등을해서 교내 1위, 대학순위 3위를 기록했다!
팀원은 cheetose,ryute,knon0501(나) 이다. 

고대에서 잘하는 두 팀(Powered by zigui, 1WA=5 push up)이 모두 은퇴를 해서 교내 1위는 할 것 같았다.
연초에는 3오렌지 정도면 충분히 월파를 노릴만하다는 생각을 했으나 UCPC와 ICPC 예선을 말아먹으며 갈수록 자신감이 똑떨했다...
그래도 팀연습을 10번이나 했고 나는 2학기를 ICPC준비에 올인할 생각으로 17학점을 전부 꿀과목으로 채웠다.
팀연습을 많이 한 것이 패널티를 줄이는 데에 정말 많이 도움이 된 것 같다.
본선에서는 팀원 모두의 강점이 드러나서 좋은 결과를 얻었다. 월파를 갈 수 있을 진 모르겠는데 가면 좋겠다 ㅋㅋㅋ

본선준비

예선 때 망한 요소를 되짚어보며 에디터를 코드블럭에서 서브라임 텍스트로 변경했고 스테이플러를 준비해서 출력물을 정리하기로 했다. 그리고 에디터 내에서 단축키로 바로 출력할 수 있게 했는데 매우 편리했다.
전날까지도 팀연습을 했는데 결과가 괜찮아서 나쁘지 않은 느낌이었다. 그래도 긴장이 많이돼서 4시간밖에 못잤다 ㅋㅋㅋ 다행히 본선 때 졸리지는 않았다. 아침에 일어나니 배가 아파서 불안했지만 다행히 대회 중에는 괜찮았다.

~6 min

cheetose님이 세팅과 문제 출력을 하면서 내가 A, ryute님이 B를 읽었다.
ryute 님이 B가 쉽다고 하더니 바로 맞았다.

~31 min

A가 까다로운 구현문제였는데 내가 바로 키보드를 잡았다. 내가 구현력이 안좋은 편인 데다가 그 시점에서는 절대 잡아서는 안되는 문제였다. 이 대회에서 내가 한 가장 큰 실수인 것 같다... 그 사이 스코어보드에서는 C와 E가 조금씩 풀리고 있었고 ryute님이 cheetose님에게 H를 설명하자 cheetose님이 이거 FFT라며 바로 짜고 AC를 받았다. H 퍼솔이었는데 스코어보드에 약간의 혼란을 준 것 같았다 ㅋㅋㅋ

~59 min

ryute님이 J를 보고 이거 선대인 것 같다고 했고 나는 I의 pst를 이용한 $O((n^2+m)\cdot \log n )$풀이를 만들었으나 팀노트에 있는 pst 구현체를 한번도 사용한 적이 없었다. 내스타일로 직접 짤까 생각도 해보고 ryute님한테 풀이를 전달해서 대신 코딩시킬까 생각도 했으나 지금 시점에 잡을 문제는 아니라고 판단하고 L을 좀 보다가 생각보다 어려워서 C를 읽었다. 그 사이 E 풀이가 나와 cheetose님이 코딩을 했는데 2번의 실수후에 AC를 받았다.

~82 min

내가 C를 잘못 해석하고 성급하게 코딩을 하고 심지어 그걸 제출할 뻔 했으나 팀원들의 제지로 다행히 그런 참사는 없었다. ryute님이 제대로 된 풀이를 만들고 코딩해서 AC. 우리팀이 실력에 비해 C번을 푸는 것이 약간 늦었는데 내 잘못이 큰 것 같다 ㅋㅋㅋ. C 풀이가 늦게 나와서 10등 아래로 잠시 떨어졌는데 이 이후는 계속 10등 이내를 유지했다.

~92 min

C를 푼 직후 cheetose님이 바로 가우스소거법을 구현해서 J를 풀었다.
그 사이 나는 I를 오프라인으로 풀면 pst 대신 그냥 세그를 써도 풀린다는 것을 깨달았고 G를 읽었다.

~126 min

G는 볼록함수일 것이라는 믿음을 가지고 이분탐색을 쓰면 된다. 실제로 얼마 전에 그런식으로 푸는 문제 를 풀어본 적이 있었다. 그래서 호다닥 구현을 했으나 틀렸다... 틀린 이유를 도무지 모르겠어서 키보드를 ryute님에게 넘겨주고 지문을 다시 읽어보는데 역순을 고려 안했다는 것을 깨달았다. 고치고 AC.

~158 min

내가 I를 구현해서 맞았다. 다른 팀원들은 F와 A를 보고 있었다.

~226 min

ryute님의 L풀이가 나와서 코딩까지 했지만 cheetose님이 스트레스를 짜보니 틀리게 나왔다. 이후 풀이가 잘못된 가정을 하고 있었다는 것이 밝혀졌다. cheetose님은 A를 풀러 떠났고 나는 L을 잡았다. L은 어떻게든 CHT를 쓸 수 있는 형태로 식변형을 시도했으나 모두 실패했다. 사실 L은 내가 예전에 Aliens Trick 와 Monotone Queue Optimization 을 써야하는 문제를 만들 때 관찰해봤던 식이기도 한데 저 식은 Monge가 아니라서 DnC Opt로도 풀리지 않는다. 이후 내가 몇가지 관찰을 더 해서 분할정복을 하면 Monge Array가 된다는 사실을 알아내고 DnC를 두 번 하는 $O(N\cdot \log^2 N)$ 풀이를 만들었으나 $N$이 100만에 1초라 당연히 안되는 풀이였다. 그 와중 cheetose님이 A를 한번에 턱하고 맞아왔다! 정말 대단한 것 같다 ㅋㅋㅋ

~300 min

나는 L을 계속 잡았지만 더 이상 괜찮은 생각을 떠올리지 못했고 ryute 님과 cheetose 님은 F를 SCC로 접근하여 열심히 풀고 제출했으나 맞왜틀을 외쳤다. 결국 1분 전에 말도 안되는 $O(N)$그리디를 L에 제출하고 마무리.

대회 종료 후

아마도 대학순위 3등을 할 것 같았고 실제로 스코어보드를 까보니 3등을 했다! 정말 기뻤고 1년동안 마음고생 많이 했는데 마무리가 좋아서 기쁘다. 1년 동안 수고한 팀원들 모두 고맙다 ㅎㅎ.
여담으로 작년 팀원이었던 jrguyyoo 와 nemo 도 17등으로 작년 23등보다 높은 등수를 얻었다. 축하해!