UCPC 2023 본선 후기 + 팀 전략에 대해

UCPC 2023 본선에 "25세 김동현 마지막 UCPC -많은 응원 부탁드려요-" 팀으로 출전하였다. 멤버는 역시 UCPC 2021/2022 및 ICPC 2022를 함께한 두 명 (stabilizer_h(안정현) / harinboy(이하린)).

결과는 5등. 대회 끝난 직후에 예상했던 결과보다는 높은데, 그래도 더 잘 할 수 있었다는 약간의 아쉬움이 존재한다.

---

대회 전에 PS 연습을 좀 할까 했으나, 그것은 메이플 하이퍼버닝으로 대체되었다. 대회 전날에도 12시 되자마자 오늘 메할일만 하고 자야지 했는데 다 끝내고 폰질 좀 하니까 3시가 돼서야 잠에 들 수 있었다. 그리고 8시에 일어났다. 사실 전날부터 이미 수면부족 상태였기 때문에 오늘은 아침부터 쭉 수면부족 상태였다. 지금 돌이켜 보니 이게 영향이 유의미하게 있었을 것 같다..

대회장에 가서 세팅을 하는데, Wi-Fi 연결을 하려면 ARS를 해야 하는 시스템이 신기했다. 원래 그냥 노트북 화면으로 보려고 했는데, 자리마다 모니터가 하나씩 있길래 쓰기로 했다. 대충 오랜만에 보는 사람들이랑 인사 좀 하고 자리로 돌아왔다. 11시가 다 돼 가는데 뭔가 어수선하길래 혹시나 했는데, 역시나 대회는 10분 늦게 시작했다.

10분을 더 앉아서 뻐기니 어느덧 시작을 했고, 문제는 13개였다. 나는 A~D를 읽었는데, 다 읽고 나니까 뭔가 이상했다. 풀 수 있는 문제가 존재하지 않았다. 뒤쪽도 상황은 마찬가지인 듯 했고, 스코어보드를 보니까 모든 팀이 공통적으로 겪는 문제라는 것을 알았다. 한 10분쯤 지났는데 여전히 스코어보드는 비어있고, 풀 수 있는 문제는 없고, 하여튼 그러다가 하린이가 M을 풀어보라고 줬다. 일단 산의 꼭대기만 모두 색칠하면 그게 최소인 건 맞는데, 이게 은근히 처리할 게 있어서 코딩이 좀 걸렸다. 거의 다 짜가는 시점에 L 퍼솔이 무려 17분? 만에 나왔고(;;;) M은 짜서 냈는데 틀렸다. 1분 안에 고칠 수 없는 것 같아서 그냥 L을 먼저 짜기로 했다. L은 한 번에 맞았고, M도 다행히 금방 고칠 수 있어서 맞았다. M은 퍼솔도 먹었다.

그리고 나서 스코어보드를 봤는데, C와 F 등등이 풀리고 있었던 것 같다. C는 뭔가 그래프를 잘 변형해서 다익을 쓰라는 문제인 것 같은데 생각이 바로 안 났고, F도 잘 모르겠고 그래서 약간 고민을 하다가 F의 풀이를 찾았다. 그리고 곧 팀원들이 C도 이렇게 하면 된다고 알려줬다. C가 F보다 짜기 쉬울 것 같아서 C를 먼저 짰고, 안 틀리고 맞을 수 있었다. 이 때 쯤에 정현이가 "E 이렇게 하면 될거같다" 라고 했던 거 같은데, 기하라서 일단 나중에 하기로 했다.
* 사실 지금 돌이켜보면 C를 그냥 내가 보고 금방 풀이를 냈어야 될 거 같은데, 못 그런 걸 보니 수면 부족의 영향인 듯 하다.

그리고 나서는 F를 짰다. DFS ordering으로 Mo's algorithm을 돌리는 O(N^1.5logN) 풀이를 기깔나게 짰는데, 틀렸다. 뭔가 고쳤는데 또 틀렸다. 이 쯤에서 뭔가 이상함을 느끼고, K를 짜겠다는 하린이에게 키보드를 넘겼다. 디버깅은 생각보다 오래 걸렸는데, Mo's algorithm을 너무 오랜만에 짜다 보니 구간을 먼저 넓힌 다음 줄여야 한다는 것을 망각한 것이 원인이었다. N 25만에 5초였지만 매우 잘 짰기 때문에 시간초과는 나지 않았다. 그리고 나서 정현이가 H의 풀이를 정리해서 줬다. 그러고 있는 동안 하린이가 열심히 짜서 제출한 K는 틀리고 말았다. 하지만 그 다음에 내가 F 디버깅 -> H 코딩 2연타로 솔브 2개를 추가할 수 있어 다행이었다.

그 다음에 하린이가 K를 열심히 제출하고 틀리고 하는 동안 나랑 정현이가 G를 봤는데, G에서 뭔가 시뮬레이션을 step size (한 번에 보는 구간 길이) 가 같은 과정을 뛰어넘으면 K 하나당 O(N^0.5) 바운드, 즉 O(N^1.5) 바운드가 되는 것 같다는 이야기를 했다. 근데 N이 100만인데? 라고 했다가, 내가 "근데 이거 풀이 슬라이드에 O(NlogN)이라고 써있을거 같으니 그냥 짜서 내보자" 라고 했고, 진짜 짜서 냈더니 맞았고, 풀이 슬라이드에는 O(NlogN)이라고 써있었다. ㅋㅋㅋ

그리고 나서는 하린이가 I의 풀이를 설명해 주었다. 풀이를 듣고 나니 I도 그냥 DP + lazy seg + stack 슥슥 하는 문제라서 내가 먼저 생각했어야 하는 것 같은데.. 요즘 PS를 너무 쉬긴 했다. 하여튼 구현은 머슬 메모리(?) 같은 게 남아있어서 다행히 적당한 시간 내에 할 수 있었다. 이 때도 수면부족 issue로 인해서 lazy seg update 함수 짤 때 "아 이거 첫 줄에 뭐 쓰더라..." 이러면서 앓는 소리 내며 짰던 것 같다.

그리고 나서는 하린이와 정현이가 B의 풀이를 설명해 주었다. 근데 B는 뭔가 홀짝성이 여러 개 있어서 (각 수가 첫번째/두번째인지, 각 카드가 라운드에서 첫번째/두번째로 뒤집히는지) 상당히 머리가 아픈 문제였고, 실제로 풀이를 내가 이해하고 구체화하는데 시간을 꽤 먹었다. 내가 그러고 있는 사이 하린이가 드디어 K에서 빼먹은 케이스를 찾아내고, 맞을 수 있었다. 

이 때 한 시간 반 정도 남았었는데, 그래서 "B를 풀고 E를 짜면 10솔이네" 라는 매우 희망적인 전망이 있었다. 그래서 B를 짜서 냈는데.. 이 때부터가 문제다. 일단 코드 곳곳에 2n을 써야 하는 부분에 n이 써 있어서 여러 번 틀렸다. 그 다음에는, 우리 풀이가 두 종류의 count 값을 세 놓고 그걸로 답을 계산하는 풀이였는데 답 계산식을 한 5번 정도 고쳤다. 식은 확실히 맞다고 결론 내린 다음에도 계속 틀려서 왜인지 한참을 고민하다가 결국 naive를 짜서 비교하기로 했는데, 무려 n=4에서 반례가 나왔다;; 하여튼 그걸 읽고 코드 돌아가는 걸 보니까 count가 갱신되는 점이 내가 처음에 생각했던 점 말고도 또 있었다. 그래서 그걸 고치기 위해 또 머리 싸매고 고민하다가, 결국 대충 후보인거 같은 점을 싹 다 set에 쳐넣어서 한번에 갱신했더니 맞았다. 끝나기 10분 전에!

E를 짤 시간도 정신도 없었기에 그냥 "우리는 왜 B 디버깅에 1시간을 태웠는가"에 대해 이야기를 나누며 남은 시간을 보냈다. 나의 생각은 "내가 메이플 할 시간에 PS를 했으면 B도 풀고 E도 풀었다" 였다.

B 페널티를 엄청나게 쳐박았기 때문에 스코어보드 보고 "아 이거 4등상이네" 하고 있었는데, 생각보다 9솔이 많이 나오지 않아서 5등으로 마무리를 했다. 그나마 다행인 부분이라고 할 수 있다.

이번 대회는 진짜 풀이 생각도 거의 안 하고 팀원이 전달해 준 풀이 듣고 이해하고 구현하는 것만 반복하다 끝난 것 같다. 안 그래도 수면 부족으로 인해 대회 시작 0분째부터 피로도 50% 정도인 상태였는데, 그 상태로 한 문제씩 구현하고 틀리고 디버깅하고 할 때마다 피로도가 계속 쌓이는 느낌이었다. 특히 마지막에 B 풀이 완성하고 구현하고 디버깅할 때는 진짜 머리 터짐 -> 케이스 빼먹음 -> 틀림 -> 화남 -> 머리 터짐 -> 케이스 빼먹음 -> 틀림 -> ... 의 반복이었다 ㅋㅋㅋ... 그리고 마지막으로 저녁 먹고 분당에서 집 가는 데 가방이 너무 무거워서 뒤질 뻔했다.

---

이번 대회 셋에 대한 이야기를 잠깐 하자면, 너무 어려워서 힘들었다... 문제 퀄리티는 전체적으로 꽤 좋았다고 생각하는데, 난이도 분포는 이와 별개의 문제이다. 13문제 중에 "예상 난이도" 골드가 하나밖에 없고 나머지가 플플..플다다..다루 인 건 애초에 출제할 때부터 "월파 난이도" 정도의 셋을 낸다고 상정을 했다는 건데, 이건 참가자들에게 너무 가혹하지 않나 하는 생각이 들었다. 근데 막상 스코어보드를 까 보니 사람들이 다들 잘 풀었다..? 무작정 쉽게 냈다가는 올솔 나올 뻔 했다; 이런 광경을 보고 있자니 난이도를 어렵게 하는 게 맞는지 쉽게 하는 게 맞는지 잘 모르겠다.

그래도 개인적으로는, 어려운 문제들은 그대로 놔두고 그 앞쪽 문제들의 난이도 커브를 약간씩 완화하는 편이 더 좋았을 거라고 생각한다. 대회 초반에 15분 넘게 스코어보드가 텅 비어 있는 경험, 플레 문제를 대회 첫 솔브로 푸는 경험(C나 F를 L보다 먼저 푼 팀도 좀 있었던 듯)을 UCPC에서 하리라고 기대하는 사람은 그렇게 많지 않을 듯 하다. 특히, 아무리 평균 난이도가 높은 대회더라도, 적어도 "이거부터 푸세요~" 정도의 쉬운 문제 하나라도 있으면 이 부분을 크게 개선할 수 있다고 생각한다. 플레 다이아 루비 12개 사이에 숨어 있는 골드 1개를 찾아서 푸는 것은 너무 어렵다 ㅠㅠ

물론 앞서 말했듯이 문제 퀄리티는 매우 좋았다. 그런데 내 뇌가 잔뜩 굳어있던 탓에 팀원들이 풀이 던져준 거 코드 구현만 하다가 끝난 것 같아서 개인적으로 아쉬움이 든다. 예전 같았으면 "아 PS를 열심히 해야지!" 라는 생각을 했겠지만, 이제는 "이제 진짜 PS 접을 때가 됐네" 라는 생각밖에 안 든다 ㅋㅋ

초반에 문제 한 개도 안 풀릴 때의 그 불안감은 분명히 부정적 경험이지만, 그래도 그 다음에 한 개씩 풀리기 시작하면서는 팀 대회의 문제 푸는 재미를 느낄 수 있었던 것 같다. B 디버깅 하다가 못 풀었으면 좀 슬펐을 것 같은데, 그래도 끝나기 직전에 어떻게든 풀어서 다행이다. 마지막 UCPC, 잘 즐기고 갑니다~

---

생각난 김에 우리 팀의 전략에 대해 잠깐 이야기를 해 보겠다.

우리 팀 구성원의 풀이/코딩 능력에 대해 분석해 보자면..

- 나: 쉬운 문제를 매우 빨리 풀 수 있음. 전형적인 문제, 어디서 본 거 같은 문제를 잘 품. 수학 쪽은 약함. 코딩 매우 빠름.
- 하린: 문제를 전체적으로 잘 품. 수학도 커버 가능. 관찰이 어려운 문제의 풀이를 잘 냄. 코딩 속도는 적당한 정도.
- 정현: 수학 관련 문제 잘 품. 코딩은 익숙치 않음

대충 이렇기 때문에, 보통 팀 전략은 아래와 같은 형태를 취한다.

- 내가 컴퓨터 앞에 앉는다. 대회가 시작하면 쉬운 문제를 찾아서 나한테 던지면 내가 푼다.
- 나는 스코어보드를 따라가면서 쉬운 문제를 읽고 풀기를 반복한다. 그 동안 정현/하린은 안 풀린/이제 막 풀린 문제 중심으로 풀이를 낸다.
- 더 이상 보자마자 풀 수 있는 문제가 없는 시점에, 중간 난이도 문제 하나를 푼 하린이와 교체해서 하린이가 문제 하나를 짜는 동안 내가 다른 문제 풀이를 찾거나 정현이가 던져주는 풀이를 이해한다. 그리고 다시 내가 그걸 짠다.
- 이쯤부터는 다시 내가 컴퓨터 앞에 거의 앉아있는데, 코딩하는 시간이 길어지면서 그 사이 나머지 2명이 던져준 풀이가 쌓이기 때문이다. 가끔 가다 하린이가 짜는 편이 더 나은 문제(지문,풀이 설명이 오래걸림 or 하린이가 디테일까지 다 완성함)가 생기면 내가 컴퓨터 앞에서 나와서 풀이를 생각한다.

코딩을 특정 팀원만 한다는 점에서 MolaMola 팀의 전략 (https://zigui.tistory.com/19) 과 비슷한 부분이 어느 정도 있기도 하다. 다만 우리 팀은 한 명(나)이 키보드를 70~80% 정도 잡고 있는다는 차이가 있다.

이 전략의 장점은, 쉬운 문제가 충분히 많은 셋에서 매우 강하다. 그 대표적인 예시가 바로 서울 리저널이다. 2022 예선 같은 경우는 처음 3문제 정도를 내가 그냥 혼자 읽고->풀고, 하린이한테 풀이 하나 받아서 풀고, 다시 읽고->풀고 해서 초반 스퍼트를 매우 빠르게 달릴 수 있었고, 2022 본선도 (1등 팀을 논외로 하자면..) 대충 비슷한 흐름으로 초반에 스코어보드를 쭉 따라가면서 중간에 하린이가 한 문제 짜고, 다시 내가 마저 딴 거 짜고 해서 초반 흐름이 좋았다.

단점은, 쉬운 문제가 적을수록 안정성이 급격히 떨어진다는 점이다. 그런 셋이면 쉬운 문제를 어떻게든 찾아서 내가 코드를 짜야 뭔가 돌아가는데, 내가 초/중반에 망하면 (ex. UCPC 2022) 그대로 팀이 붕괴한다. UCPC 2023 같은 경우는 초반에는 그래도 괜찮았는데, 이 경우에는 코딩하는 사람한테 초반부터 너무 큰 과부하가 걸리다 보니 후반에 가면 코딩 능력이 크게 감퇴하는 듯 하다.

사실 이 팀으로 나갈 가능성이 있는 대회 중에 남은 게 놀랍게도 World Finals(아직확정아님..) 뿐이라 전략을 더 잘 짜야 할 듯 하다. UCPC 2023을 약간 월파 체험판(?)이라 생각하면 괜찮았을지도 모르겠다.