ICPC Seoul Regional 2020 후기

19년도에는 18년도랑 똑같은 팀(789)으로 나갔었는데, 올해 초만 해도 3학년 2학기에 휴학을 하고 산업기능요원 복무를 하러 갈 계획을 세우고 있었어서 팀원들한테 미리 "나 팀 나간다" 하고 나가고, 내 빈 자리는 어떻게 잘 해서 병특 끝나고 복학하신 gs12117님이 들어가게 되었다. 그런데...

코로나 때문에 방학 중에 끝나기로 돼 있었던 일정이 미뤄짐 + 산업기능요원 안 하기로 결정함 등등의 요인으로 3학년 2학기도 그냥 등록을 하게 되었고, 또 어쩌다 보니 tonyjjw님이 팀원을 찾고 계셔서 결국 팀을 새로 꾸리게 되었다. 팀원은 tonyjjw님과 rhrnald님. 두 분 다 상당한 실력자이셔서 WF 진출 가능성이 아주 없지는 않은 팀이었다. 아무튼 팀 연습도 몇 번 하고 하면서 대회를 준비했다.

---

온라인으로 진행하는 3인 1팀 대회다 보니 준비 과정이 정말 어수선했다.. 아마 주최 측에서도 처음 하는 일이어서 힘들었겠지만 참가하는 입장에서는 정말 귀찮았다.. 뭐 그래도 이런 요인이 대회를 치르는 데 크게 작용한 것 같지는 않았다.

rhrnald님이 상대적으로 코딩보다는 풀이 도출에 강하시고, 나는 그 반대라서 초반에는 나와 tonyjjw님이 키보드를 주로 잡기로 하였다. 아무튼 대회가 시작을 했고, 놀랍게도 대회 직전까지 잘 되던 프린터가 시작하자마자 맛이 가서(...) 문제를 읽는 데 약간의 힘겨움이 있었다.

A는 바로 풀 문제는 아닌 것 같았고, B는 쉬운 문제 같아서 일단 B를 tonyjjw님한테 설명해드리면서 넘겼는데, 놀랍게도 내가 B를 잘못 읽어서(???) 초반에 약간 망할 뻔했다. 내가 결국 문제를 다시 제대로 읽은 다음 코딩해서 맞았다.

그 다음에는 역시 쉬운 문제였던 C를 tonyjjw님이 빠르게 코딩해서 맞았다.

초반에 약간 말린 덕에 스코어보드를 보고 따라가는 꼴이 되었는데, 그 다음으로 쉬운 문제로 추정되는 E를 같이 보기로 했다. 풀이가 어렵지는 않았는데, 초반에 약간 생각을 대충 해서 한 번 틀렸다.

그 다음에 본 문제가 G였는데, tonyjjw님이 문제 설명 + 풀이 요약까지 해 주셔서 나는 그걸 받아서 코딩을 했다. 이거는 케이스를 하나 빼먹어서 한 번 틀렸다..

그리고 나서는 J를 봤는데, bitset으로 gaussian elimination을 짜면 되는 문제였다. 짜 본지 좀 오래 돼서 잘 짤 수 있을지 걱정했는데 생각보다 빨리 짤 수 있었다. 다행히도 한 번에 맞았다.

그 다음에는 처음에 미뤄두었던 A를 풀기로 했다. 사실 초반부터 중간에 컴퓨터가 살짝씩 비었어서 그 때 틈틈이 코딩을 했는데, 이제는 A를 다 짜야 할 것 같아서 코딩을 했다. 코딩 자체는 생각보다 빨리 끝났는데 제출을 하니까 틀려서 그때부터 약간 정체가 찾아왔다. 심지어 H도 FFT를 짜면 쉽게 되는 문제라서 rhrnald님이 코딩을 했는데 예제가 안 나와서 둘이서 열심히 디버깅을 하고 있었다.

그러다가 tonyjjw님이 갑자기 "F가 Dominator Tree인 것 같다"고 하시면서 팀노트에 있던 dominator tree 코드 사용법을 물었다. 나도 써 본 적은 없었지만 대충 배열 이름을 보고 짐작해서 "이거 아닐까요?" 했더니 대충 그런 것 같다 싶은 채로 코딩한 뒤 내서 맞았다...? 최종 스코어보드를 보면 제일 어려운 3문제 중 하나였는데 어쩌다가 날먹을 해버렸다.

그리고 나서 A와 H의 오류도 곧 잡을 수 있었다. A는 내가 처리를 편하게 한다고 점을 swap하다가 실수로 시작점을 바꿔버린 게 원인이었고 (tonyjjw님께 코드 설명 드리면서 봐달라고 하니까 2분만에 찾으셨다;;) H는 팀노트를 베끼다가 중괄호 위치 하나를 잘못 적은 게 원인이었다. 아무튼 그렇게 풀고 나니까 8솔브로 잠시 2등까지 갔던 것 같다.

그 다음에는 L이었는데, 처음에 식이 이 문제에서 본 거랑 비슷하게 생겨서 monotone queue optimization 같은 뻘소리를 좀 했는데 그냥 어그로였다.. 실제 풀이는 17WF에 나온 Money for Nothing 문제와 매우 유사한 DnC optimization으로, 나는 이 문제를 심지어 옛날에 풀었었지만 전혀 기억하지 못하고 rhrnald님이 새로 풀어주셨다. 코딩은 내가 했는데, 처음에 제대로 이해하지도 않고 급발진하느라 트롤을 약간 했다.. 어쨌든 풀긴 풀었다.

I는 tonyjjw님이 처음에 제시하신 \(O((n^2 + m)log^2n)\)짜리 풀이가 될지 안 될지 모르겠어서 (n이 2000이었다) 로그를 하나 떼는 방법을 꽤 오래 고민했는데, 결국 2D Fenwick을 믿고 한 번 짜 보자는 의견이 나와서 내가 슥슥 짜서 냈는데 그게 맞았다;; 제한 가지고 장난 좀 안 쳤으면 좋겠다.. 다행히도(?) \(O(n^2logn)\) 풀이로 푼 팀이 있긴 하다.

이제 2문제가 남은 상황에서 각각 생각을 열심히 했는데, K에서 풀이가 먼저 나왔다고 생각해서 내가 코딩을 하기로 했다. 그리고 내가 30분동안 열심히 코딩해서 제출한 뒤에 그게 사실 풀이가 아니었다는 걸 깨달았다... 골자는 대충 맞는데 디테일이 조금 더 많이 필요했다. 코딩할 때 까지만 해도 팀원 모두가 그게 맞는 줄로만 알았는데, 조금 더 침착했어야 했을까..?

이제는 시간이 얼마 남지 않아서 둘 다 풀기는 힘들고 하나라도 풀어야 하는 상황이었는데, 마지막 몇십 분 동안은 D를 코딩하다가 끝났다. 나는 사실 K에 몰두하느라 D를 별로 깊게 생각해보지 못했는데, D를 내가 잡았으면 풀었을까 하는 아쉬움도 있다. 대회가 끝난 후 좀 더 생각해 봤는데, 실력이 부족해서 그런지 D나 K같은 문제는 풀이를 구체화시키기가 어렵다. 어려운 문제 풀이 생각하는 능력이 계속 ps 인생에서 발목을 잡는 느낌인데, 노력을 더 하면 해결될 문제일까? 

대회가 끝나고, 아쉬운 마음을 가지고 낙성대 차이나당에 가서 저녁을 먹었다. 저녁 먹는 도중에 스코어보드 공개가 있었는데, 결과를 보니 Let Us Win ICPC WF 팀이 압도적인 페널티로 올솔브를 달성해서 1등을 했다. 결국 박터지는 서울대 팀 경쟁에서 새내기 3인팀이 18년도에 이어 또 우승했다. 약간 벽이 느껴지기도 하고, 앞으로 졸업 전까지 더 열심히 ps를 해야겠다는 동기부여가 되기도 했다.

스코어보드를 보면 서울대 6팀이 각각 1, 2, 3, 4, 5, 9등을 기록했는데, 작년에 이어 역대급으로 서울대와 타 대학교 팀간의 격차가 심하게 나는 해였던 것 같다. 아마 최근 4년 (2016 ~ 2019) IOI 대표의 거의 대부분이 서울대에 진학함으로써 이런 현상이 생긴 것 같다.

나는 아마 군대를 갔다 온 후 리저널을 1번 더 나가지 않을까 싶은데, 그 때 팀은 어떻게 구할지 모르겠긴 하지만... 나가게 되면 WF를 한번 더 진출하고 싶은 욕심이 생기는 계기가 된 것 같다.