UCPC 2025에 참여하였습니다.

지난 ICPC 2024 에 같이 참여했던 diordhd의 소개로 TLEwpdus(?), diordhd, daniel604로 팀을 꾸리게 되었습니다. LGM과 대회에 참여한다는 상상은 해본적도 없었는데, PS를 시작한 이래 최고의 행운이 아닐까 싶습니다. TLEwpdus만큼 PS 실력도, 경험도 풍부한 분과 함께할 참여할 기회가 드물다는 걸 알고 있었기에 많이 배우고 싶은 마음이었습니다.

TLEwpdus의 작명센스로 팀 이름은 인공지능 사용 적발 시 실격 처리 됩니다, 팀원명은 각각 Yann LeCun, Yoshua Bengio, Geoffrey Hinton로 참여하였습니다. (저는 그중 Geoffrey Hinton를 담당했습니다.)

예선

scoreboard1

동현이형 diordhd이 A ~ D, 제연이형 TLEwpdus은 E ~ H, 저는 I ~ K를 잡고 대회를 시작하였습니다.

A, B, D, E, G, H, I를 각자 밀었고, (제연이형의 H 퍼솔!) C는 제연이형과 동현이형이 조금 아이디어를 나누다 풀었습니다. (사실 어떤 분이 어떻게 풀었는지 놓쳤습니다.) F는 제연이형이 2차원 펜윅으로 TLE를 받고, 2차원이 아닌 풀이가 있음을 알고 다시 제출하여 맞았습니다. 그 사이 동현이형과 J 아이디어를 떠올리고 제출하였지만 엣지 케이스를 놓쳐서 2번 틀리고 맞추었습니다. 대략 한 시간 정도 남아서 다같이 K를 고민하였고, 제연이형이 트리의 지름 위을 이용해서 풀 수 있음을 발견하였지만 서로 다른 지름까지의 거리가 많지 않다는 관찰을 놓쳐서 풀지 못했습니다. 사실 제연이 형이 이 문제를 이용하면 될 것 같다 하였지만 시간도 부족하고 짤 수 없어 저 문제의 링크를 제출하였습니다(?).

대회가 끝나고 C, F, G를 업솔빙해보았는데 쉽게 밀어낸 팀원분들이 든든했습니다. 특히 F는 시간 제한이 꽤나 빡빡했습니다.

팀연습

예선 일주일 후 컴퓨터 한 대로 진행되는 본선도 익숙해질 겸 5시간 셋 CERC 2023으로 팀연습을 진행하였습니다. 제 입장에서 짧게 요약하자면, C번을 제연이형이 웰노운이라며 풀어주었는데 풀이가 너무 아름다웠습니다. 그리고 J번을 구현에 쩔쩔매다 못 풀었습니다.. 구현을 충분히 고민하지 않고 알 수 없는 자신감으로 문제에 들어갔는데 엣지 케이스가 자꾸 나와서 멘탈이 흔들렸습니다. 구현 전에 정리하고 들어가는 게 얼마나 중요한지 다시 한 번 배울 수 있었습니다.

본선

대회 시작전 후원사 부스가 운영되었기에 한 시간 정도 일찍 가서 부스들을 구경하고, 다양한 기념품도 수령했습니다. (이번 UCPC 옷이 핑크빛인데 색이 마음에 들었습니다.)

scoreboard2

대회장에 착석한 순서대로 제연이형 TLEwpdus이 A ~ E, 동연이형 diordhd은 F ~ I, 저는 J ~ M을 잡고 대회를 시작하였습니다.

잡은 문제들을 읽었는데 마땅히 풀이가 생각나는 게 없었고, M이 case work을 하면 해를 구성할 수 있을 것 같아서 그려보다 도무지 아닌 것 같아 포기하였습니다. 그 사이 팀원분들이 B, C, E, I를 밀어주었고 (제연이형의 B 퍼솔!) 동현이형의 H 풀이를 들었습니다. H 풀이에 case도 너무 많고 construct까지 해야하는 말도 안되는 구현량이었기에 dlwocks31이 보고 싶어지는 문제였습니다. 동현이형이 구현을 시작하고 제연이형과 같이 A를 봤는데, 원래 dp로 접근하던 중 갑자기 제연이형이 $\text{number of leaves}/{2}$ 로 구성할 수 있음을 알아내고 제출하였습니다. 그 사이 K를 고민하였는데 2개씩 끊어서 생각하면 case를 나눌 수 있는 관찰을 했습니다. 제연이형이 slope trick처럼 직선을 관리하는 풀이를 짜서 제출했지만 WA를 받았습니다. 다행히 반례를 찾을 수 있었고 다시 제출해 맞출 수 있었습니다. 때마침 H 스트레스 테스트까지 짜던 동현이형이 지옥에서 탈출하면서 술술 풀려나가기 시작했습니다!

H를 맞춘 후 40분 정도 남은 시점에서 다같이 제연이 형이 G 코드 짜는 것을 보기로 하였습니다. 종료 5분을 남기고 제출하였지만 WA를 받았고 init() 호출을 빼먹었음을 알고 빠르게 다시 제출해 맞출 수 있었습니다. 실제 맞았습니다!! 가 떴을 때는 종료 2분 전이었기에 다같이 어깨동무를 하고 좋아했습니다. 마지막 문제를 풀 때는 제연이형의 침착함이 빛을 발했던 순간인 것 같습니다. 제출을 해두고 Alt Tap을 반복하며 디버깅 하던 순간은.. 정말 인상적이었습니다.

최종 3등으로 2등상을 받으며 대회를 마무리할 수 있었고, 스코어보드 프리즈 이후에 문제를 맞춘 팀들이 많아 스코어보드를 공개하는 과정도 정말 짜릿했습니다.

마무리

이렇게 처음으로 상을 타게 되었습니다. 컴퓨터가 쉬는 시간도 거의 없었고, 서로의 아이디어와 구현을 검증함에 팀워크도 완벽했기에 너무 만족스럽고 행복한 대회였습니다. 앞으로도 대회에 같이 나가고 싶지만 동현이형은 정말 마지막 대회였기에 더이상 같이 참여할 수 없게 되었습니다. (제연이형과는 NYPC에 나가게 되었습니다!) 지난 ICPC부터 함께하며 문제가 안 풀릴 때면 동현이형이 참신한 아이디어를 내주길 기다리곤 했는데.. 아쉽게도 이제는 그럴 수 없게 되었습니다. 그래도 마지막 대회에 같이 수상할 수 있었기에 뿌듯하네요. 앞으로도 동현이형과 제연이형의 앞날에 좋은 일만 가득하길 응원합니다!