UCPC 2023 예선 준비 과정 + 대회 후기

6 solve로 59등을 한 우리팀.

군대 이슈로 3년 만에 참가한 알고리즘 대회였다.

재학생 3인 1팀으로 진행되는 대회라, 아는 사람도 별로 없고 '동일 학교 소속 팀' 추가선발을 노리기 위해 같은 학교 지인분들인 kimyh9797, dudqk9696, leedongbin(나) 세 명으로 팀을 구성했다.

2020 예선에서는 대회 도중 서버가 터져서 본선 커트라인이 엄청 낮았기 때문에 본선에 진출했었는데,

작년부터 대학원생까지 참가 자격 범위가 넓어져서 커트라인이 많이 올라갔다. 대충 플래티넘4 난이도까지는 다 풀어야 본선 진출일 거라고 예상하고, 대회 전에 세 번 정도 디코로 만나서 연습 셋을 풀어봤다.

 

연습 과정

• UCPC 2022 예선

이미 kimyh9797님이 참여했던 예선 대회였지만, 기출문제가 가장 좋은 연습문제이기도 하고 대회 중에 시간이 없어서 아예 못 본 문제가 있다고 하셔서 작년 기출로 연습했다.

이때 커트라인이라고 볼 수 있었던 D번 문제를 열심히 풀다 시간 부족으로 끝났는데, 이후 얼마 지나지 않아 업솔빙에 성공했다. C++의 pbds라는 자료구조를 사용하면 쉽게 풀 수 있다던데, 나는 몰라서 세그먼트 트리로 구현했다.

풀었다면 6솔로 본선 커트라인이라, 컨디션만 좋다면 예선 통과 해볼 만할지도..?라고 생각했던 것 같다.

시간이 부족하다는 피드백으로, 다음 연습부터는 dudqk9696님이 구현을 맡아주기로 하셨고, 구현하는 게 귀찮아서 군대에서 수학 문제만 골라 풀었던 나는 이때부터 세그먼트 트리 문제들만 집중적으로 연습했다.

• shake! 2022

두 번째 연습은 골드~플래티넘 문제가 적당히 섞여있는 셋으로 골랐다.

난이도를 가리고 문제를 풀까 생각했는데, 어차피 실제 예선 대회 때도 상위권 분들의 스코어보드를 따라갈 계획이었어서 알고리즘 태그만 가리고 풀었다.

이때 나는 B를 빠르게 풀고 C를 풀다가 맞왜틀에 정신이 나가버렸고, D, G를 푼 kimyh9797님이 나 대신 C를 풀어주셔서 나는 정신을 다잡고 F를 푸는 데 성공했다. dudqk9696님은 A 이후 E를 풀다가 말려서 못 푼 채로 연습이 끝났다.

시간 부족으로 플래티넘4 문제들을 읽지도 못해서, 예선에 자신감이 좀 떨어진 상태였다.

그래서 이날 피드백으로 '말렸을 때 어떻게 할 것인가?'에 대한 토론을 했었고, 결론은 '붙잡고 있지 말고 다른 사람이 처음부터 다시 풀어주자.'였다.

• shake! 2020

2021년도 문제는 너무 많이 풀려있어서 이전 년도 셋으로 골랐다.

D번 문제의 실수 오차 처리가 너무 어려워서, 속도 제한이 10인 점을 이용해 10! 을 곱하여 정수로 변환했다. 오버플로우까지 발생해 버려서 __int128 자료형을 써서 억지로 풀었다.

이후 G번 문제를 잡았는데, 세그먼트 트리에 뇌가 절여진 나는 스위핑+분리 집합 문제를 2시간 동안 세그먼트 트리 풀이로 삽질하고 있었다....

내가 헤매는 동안 kimyh9797님이 B, C, E번, dudqk9696님이 A번을 풀어주셨다.

이때부터는 생각이 한쪽으로 치우치지 않기 위해 다시 다른 알고리즘 문제를 연습했다.

예선 대회에 우리가 자신 있어하는 DP, 수학, 세그먼트 트리 문제가 커트라인 문제로 출제되길 기도했다.

 

예선 진행

직접 만나서 토론하는 게 편할 것 같아서, 대회가 14~17시라 스터디룸을 13~17시로 예약했다.

3년 전 UCPC 2020 예선 때의 루틴 그대로, 스터디룸 근처에서 맥도날드를 먹고 마실 것을 사서 들어갔다. 생각보다 좁았다.

대회 1시간 전에는 간단한 골드 문제로 워밍업을 했고, 이전에 썼던 ICPC 팀노트를 참고하면서 자주 안 쓰던 알고리즘들을 리마인드 했다.

• 0:02: (A AC by kimyh9797) A번을 보자마자 풀이에 들어가셨고, AC를 받았다. 이후 스코어보드를 따라 내가 D번, kimyh9797님이 I번을 잡았다. dudqk9696님이 스코어보드를 대신 봐주며 문제가 풀릴 때마다 알려주셨다.

 

• 0:16: (I AC by kimyh9797) 간단한 누적합 문제였고, 금방 AC를 받아주셨다.

 

• 0:19: (D WA*2 by leedongbin) 그냥 뻔한 구현 문제였는데, 어디서 오타를 친건지 2번이나 WA를 받았다. 전략대로 다른 분들이 나 대신 D번 문제를 봐주셨고, 나는 다음으로 많이 풀린 K번을 풀러 갔다.

 

• 0:26: (D AC by kimyh9797) 다행히 실수 없이 풀어주셨고, 이때 K번의 풀이에 대해 다 같이 고민했다. 그리디와 이분탐색 풀이 두 개가 나왔는데, kimyh9797님이 그리디 풀이로 시도해 본다고 하셔서 나는 B번으로 넘어갔다.

 

• 0:47: (K TLE, WA by kimyh9797) 그리디 풀이가 안 되는 것 같았다. 말리기 전에 내가 K번의 이분탐색 풀이를 즉시 시도했고, 스코어보드에는 B, C가 비슷하게 풀려있었다. B번은 좀 어렵다고 생각해서, kimyh9797님이 C번을 잡았다.

 

• 1:10: (K WA, AC by leedongbin) 이분탐색 풀이가 맞았고, 토론 중에 나왔던 의견을 코드에 깜빡하고 반영을 안 해서 WA와 9분의 시간을 날렸다. 나는 다시 B번으로 돌아갔고, dudqk9696님이 상위권에서 조금씩 풀리고 있는 F번을 잡았다.

 

• 1:27: (C AC by kimyh9797) mst+기하학이라는 풀이를 금방 떠올려주셨고, 수식이 복잡해서 dudqk9696님이 대신 구글링해주셨다. C번 AC를 받고 나서, 다 같이 B번 풀이에 대해 고민했다. 나는 TLE 풀이밖에 생각이 안 났는데, kimyh9797님이 트리+dp 풀이를 시도해 본다고 하셔서, 나는 B번을 맡기고 dudqk9696님이 풀고 계신 F번을 도와주러 갔다.

 

• 1:50: kimyh9797님이 B번의 풀이가 틀렸음을 알았고, 나는 F번 풀이가 전혀 감이 오지 않았다. 손 놓고 있을 수는 없었기에, 나는 B번의 TLE라고 생각했던 풀이를 기도메타로 짜보기 시작했다. F번은 세 명 모두 감을 못 잡아서, kimyh9797님이 H번을 맡고, dudqk9696님이 브루트포스 풀이라도 시도해 보셨던 것 같다.

 

• 2:13: (B AC by leedongbin) 믿음으로 냈던 풀이가 AC를 받았다! 나는 당연히 TLE가 날 거라고 생각했는데, 집에 오는 길에 곰곰이 생각해 보니 $M log(M) + N log^2(N)$ 풀이였고, 실제로 이게 정해였다. (자기가 짠 코드 시간복잡도도 모르네...) small to large 테크닉 문제를 거의 안 풀어봐서 시간복잡도에 대한 확신이 없었던 것 같다. 아무튼 살짝 들뜬 마음으로 다시 F번 문제를 고민했다.

 

• 2:30: F번 문제가 정말 많이 풀렸는데, 우리 팀은 아무리 봐도 감이 오지 않았다. E번 문제가 기댓값을 구하는 깡수학 문제라서, 수식 조합으로 찍어맞히기라도 해보겠다는 마인드로 나는 E번으로 넘어갔다.

 

• 2:41: (H WA by kimyh9797) 나와 dudqk9696님은 더 이상 진전이 없었고, 시간도 얼마 없어서 다 같이 H번을 고민했다.

 

• 2:51: H번 풀이에 해결할 수 없는 반례가 있다는 것을 발견했고, 얼어있는 스코어보드를 보면서 경우의 수 행복회로를 열심히 돌렸다.

 

• 3:00: 대회가 종료됐고, 동시에 스터디실 대여 시간도 끝나서 호다닥 뛰쳐나왔다.

 

결과 / 후기

스코어보드 프리즈가 풀리고 확인해 보니, ~7 solve 팀이 49명, ~6 solve 팀이 64명이었다.

6 solve인 우리 팀이 혹시 추가 선발이 되진 않을까 했는데, 어림도 없었다. 7 solve 팀마저도 일부 탈락한 게 충격이었다.

커트라인이 ~플래티넘 3 All solve라니... 너무 어렵다.

평소 수학 문제에 자신 있던 나였는데, 못 풀고 있던 E, F, H번 문제가 모두 수학 관련 문제라는 점에서 현타가 왔다.

H번 문제를 내가 좀 더 일찍 잡아봤다면 풀었을까? 하는 약간의 아쉬움이 남았다.

비록 본선에 진출하진 못했지만, 대회 중에 서로 말린 문제를 커버해 주는 케미가 상당히 좋았고, 다른 문제들은 시간이 더 있었더라도 풀기 어려웠을 것 같아서 크게 미련은 안 남는다.

후에 열릴 ICPC에서는 꼭 본선 가기를...