UCPC 2023 예선 후기

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

사실 이 팀으로 일주일 전에 FunctionCup 2023도 쳤는데, 귀찮아서 후기는 안 썼지만.. 그래도 나름 괜찮게 친 거 같아서 그냥 비슷한 느낌으로 대충 치기로 했다. 개인적으로는 PS 연습도 졸업논문+이것저것 때문에 바빠서 거의 안 하다시피 했는데 최근에 코포/모비스 예선/FunctionCup 등등 개인대회 퍼포먼스를 봤을 때 괜찮겠거니 싶었다.

결과는 4등. 초반에는 참 좋았는데, 중반에 내가 시간을 한 30분 갖다버린 게 좀 큰 듯 하다. 프리즈 이후에 어떻게 수습을 잘 하긴 했으나 그 대가로 페널티가 약간 망했다. 본선 전에 팀연습을 한번쯤 해야 하나 싶기도 하다.

문제별 풀이는 https://static.ucpc.me/files/2023/ucpc23-prelim-solutions.pdf 여기에 가면 있으니 따로 적지는 않았다.

대회 타임라인

나는 항상 하던 대로 앞 4개를 읽었다. A는 언제나처럼 브론즈 문제였기 때문에 바로 Python 제출창 코딩을 시전했고, 작년의 아픔을 딛고 한 번에 맞을 수 있었다 (1min AC). 풀이 슬라이드에 따르면 전체 1등인 거 같다. 굿~

그 다음에 지나가면서 B, C, D를 봤는데 세 문제 모두 풀이는 금방 가닥을 잡을 수 있었다. 다만 B는 small-to-large를 짜야 하고, C는 "두 원을 모두 둘러싸는 끈의 최소 길이"를 구해야 해서 바로 구현할 수 있는 D를 짰고, 한 번에 맞았다 (6min AC).

원래 C는 수학담당 팀원인 정현이가 식을 만들어주면 그걸로 나머지를 구현할 생각이었으나, 대충 검색을 해 보니 생각보다 간단한 거 같아서 그냥 내가 식을 세워서 풀었다. 식은 실제로 별로 어렵지 않았고, 나머지 부분은 그냥 MST 구하기였기 때문에 후딱 짜서 내니 무려 퍼솔이었다 (18min AC).

그 다음에는 남겨둔 B를 구현하기로 했는데, 사실 한 10분은 걸릴 줄 알았으나 코드가 생각보다도 훨씬 짧게 끊겨서 딱 5분만에 짜서 맞았다 (23min AC). 문제 세팅이 워낙 전형적이라 그랬나 싶다.

그 동안 뒤쪽 문제중 I와 K가 풀렸었는데, I는 하린이가 잡고 있었고 K를 내가 짜기로 했다. 좀 있다가 I도 맞았다(26min +2 AC). K는 딱 봐도 파라메트릭+그리디를 하면 되는 문제였는데, 초기값을 1을 넣어야 되는 걸 0을 넣어서 (세미나를 1일차부터 시작할 수 있음) 한 번 틀렸다. (32min +1 AC).

여기서부터가 약간 문제인데.. 그 다음으로 많이 풀린 문제인 F는 이 쯤에서 풀이가 나와서 정현이가 열심히 짜고 있었다. 사실 그런 줄 모르고 나도 F 풀이를 따로 생각하고 있어서 버린 시간이 한 7분쯤 되는 거 같긴 한데.. 여튼 하린이는 E를 시도하고 있었고, 나는 남은 문제인 G, H, J 중에서 그나마 내가 제일 풀 수 있을 것 같아 보이는 G를 잡았다. 그런데 G 풀이의 초입 부분 (고려해야 하는 집합 가짓수가 O(nm)개임) 에서 어떤 집합을 잡아야 하는지에 대해서 뭔가 갈피가 잘 안 잡혀서 한참을 헤맸다. F라도 빨리 풀어야 할 거 같은데 팀원이 이미 잡고 있고.. G는 안 풀리고, E도 틀리고.. 하여튼 그래서 한 20~30분간 진전이 없었다.

그러다가 뭔가 진전(?)이 생겼는데, 정현이가 짜던 F 코드를 내가 디버깅하게 된 것이다. F가 딱 봐도 구현하다가 머리 터질 거 같은 문제라서 코드를 봤는데 역시 엄청났다. 머리가 터지기 전에 다행히 오류를 찾아서 맞을 수 있었다. %2를 안 붙여서 런타임 에러를 받았는데 예제는 그걸 안 붙여도 맞더라.. (87min +3 AC).

그리고 나서는 하린이가 H를 "예전에 비슷한 걸 본 적 있다"면서 풀러 갔고, 나는 G를 다시 도전했다. 이번에는 다행히 올바른 풀이의 길로 제대로 들어섰고, 구현은 set이 좀 많이 필요하긴 하지만 코드 양 자체는 생각보다 얼마 되지 않아서 금방 짤 수 있었다. 한 번 틀렸는데, 식을 한 군데 잘못 쓴걸 다행히 금방 찾았다. 그와 거의 동시에 하린이도 H를 짜서 맞았다. (121min +1 AC) (121min AC). 놀랍게도 둘 다 프리즈 되고 1분 후에 맞아서 어쩌다보니 힘을 숨기게 되었다(?)

이제 E와 J가 남았는데, E는 나머지 두 명이 보는 게 훨씬 효율이 좋을 것 같아서 나는 그냥 J로 달렸다. E는 사실 하린이가 처음에 시도했다 틀린 게 약간만 보완하면 맞는 풀이였어서 그걸 메꾸니 맞았다 (139min +1 AC).

그동안 J에서는 DP를 기반으로 뭔가 열심히 관찰을 했는데, 결론만 말하면 내가 editorial에 있는 DP식과 똑같은 식을 제시하고, 하린이가 올바른 점화식까지 세워 주었다. (사실 나는 점화식이 왜 맞는지 아직 이해 못함) 그런데 초기값 구하는 게 생각보다 어려워서 그걸 잘못 짜서 틀렸다...고 생각 중이다. 올솔 까비~