UCPC 2025 본선 후기

UCPC 2025 후기글이다. 원래 따로 뭔갈 쓸 계획이 없었는데, 개뜬금없는 결과를 받아버려서 쓰기로 했다.

0. 대회 전

대회 시작 전에 뭔갈 든든하게 먹지 않으면 박는 징크스가 있어서 전날 자기 전에 근처 식당을 알아봤었다. 원래 한 7시에 일어나서 미리 갈려고 했는데...어김없이 기상에 실패해 그냥 plast랑 같이 연구소에서 대중교통 타고 아슬아슬하게 도착했다. 도착 후 등록하려고 가니까 래오가 조금만 더 늦게 오면 리버스 2등상 받는다길래 다시 나가서 근처 편의점에서 삼각김밥으로 아침을 해결했다.

 

도착이 늦었기 때문에 대충 돌아다니면서 포스텍 사람들이랑만 인사 좀 하고 자리에 앉았다. 저때 하이퍼볼릭 선배가 '님들 몇등할거임?' 물어보시길래, 대충 절대 못 이길 것 같은 3igm 2팀만 위로 보내고 나머지 다 이기고 3등할거임 ㅅㄱ 이러고 다녔다. 물론 실제로는 저 정도 급의 팀이 2팀보다는 훨씬 많았다.

 

팀 나니가cki의 구성은 아래와 같다.

changhw - 연세대의 초고수시다. 현재 직장인 초년 생활을 보내시고 계시고, 이번 대회가 은퇴 대회다.

kwoncycle - 본인이다. 

IBory - 아이보리다. changhw님과 같은 이유로 은퇴 대회가 될 예정이시다.

 

팀 전략은 간단한데, 그냥 IBory님이 자료구조나 웰노운 문제들을 풀고, changhw님이 애드혹이나 게임이론 같은 문제들을 풀고, 저 2개의 필터로 걸러지지 않은 문제를 kwoncycle이 짬처리한다- 로 정리할 수 있겠다. 팀 성향이 어떻게 보면 작년 월파팀인 AllSolvedin1557과 비슷하다고도 할 수 있지만, 차이가 있다면 그때보다 내가 실력이 400점 정도 높다.

 

참고로 UCPC 예선 때는 IBory 필터에서 모든 문제가 다 걸러졌기 때문에 그냥 골드 1개 풀고 3시간동안 놀았다.

1. 대회 중

I (00:13) +1

IBory가 보더니 걍 정렬하면 왜 안됨?을 시전하고 1분만에 짜서 틀렸다! 이상한 코너케이스를 놓친 거였고, 고치고 AC.

E (00:28)

곧바로 내가 E를 짰다. 저 당시 바로 뒤쪽 팀에서 미친 성량으로 "이거 매내처 아님?"을 외쳐서 "음 펠린드롬만 보면 되나?"라고 생각했고, 실제로 예제도 그랬다. 하지만 매내처를 팀노트에서 다 옮기고 난 후 뒷부분을 코딩하던 중에 어림도 없는 풀이라는 걸 깨달았고, 조금 생각해보니 그냥 딸깍으로 되길래 매내처를 유기한 후 새로 짜서 AC.

C (01:02) +3

E를 맞은 후 IBory와 changhw가 정수론 같은 C를 나에게 던졌다. 조금 생각해본 후 아마 시복이 보장이 될 것 같은 완탐 풀이를 짜서 냈는데, 어째서인지 WA가 자꾸 떴다. 눈 씻고 코드를 뜷어지게 봤지만 틀린 점이 없어서 K를 짜려는 IBory에게 컴퓨터를 넘겨줬다. 이후 계속 프린트된 코드를 봤지만 틀릴 수 없는 코드여서 좀 멘붕이 왔는데...알고 보니 저 둘이 문제를 잘못 읽은 상태로 나에게 문제를 넘겨줬다! 구체적으로는, [mod K를 고를 때 부분집합의 크기도 K여야 한다]는 이상한 constraint가 달린 채로 문제 전달이 됐었고, 하필 예제도 저래서 깜빡 속아버렸다. 하지만 본인 또한 문제를 잘 읽지 않았으니 공동 책임인걸로-

 

아무튼 원래 버전의 C는 자명한 n/2 답이 있고, 거기서 쉽게 develop할 수 있었기에 뚝딱 짜서 AC.

K (01:35) 

사소한 이슈가 있었지만 템포 자체는 나쁘지 않아서 계속 문제를 풀어나갔다. C를 푼 후 changhw와 같이 솔브가 나오고 있던 A와 B, H를 봤고, B는 N^2 풀이까지 금방 나왔지만 그 뒤는 당장 모르겠어서 유기했고, A는 changhw가 [path로 트리 덮으면 되는거 아님?] 관찰을 냈고, 그걸 내가 [그럼 리프끼리 대충 잘 잇고 좌표리슝좍하면 되는듯]로 이어받아 풀이를 완성했다. 그러는 동안 IBory가 아까부터 잡던 K 구현을 마쳤고, 어려운 포지션의 문제라 걱정했는데 다행히 한번에 AC!

B (02:27), A(02:40) +1

이후 내가 A 구현을 시작했고, 빠르게 구현을 마친 후 손 테케를 돌려봤는데 뭔가 잘 안나왔다. 당시 내 풀이는 [dfs ordering을 한 후 양쪽 끝 leaf를 잇기]였는데, 이러면 일부 트리 edge가 안 덮일수도 있어서 망한다. 어떻게 고칠 지 고민하던 중에 changhw와 IBory가 B 풀이를 만들어와서 컴을 넘겨주고 다시 changhw과 A 토론을 했다. 대충 [리프들이 한쪽에 몰리면 이게 잘 안됨...]을 얘기하니 changhw가 [음 그럼 센트로이드 같은거 하면 혹시 해결됨?]을 제안했고, 저러면 대충 내가 아는 문제로 reduction이 되서 이걸로 짜기로 했다. 대충 IBory가 B에서 뇌절이 올때마다 컴을 구걸해가며 A 코드를 조금씩 짰고, 얼마 안 있어 B 구현이 끝나 AC를 받았고, A는 n=2를 이상하게 해서 한번 틀리고 AC.

G (03:21)

IBory가 B를 짜는 동안 chanhw와 G를 같이 고민했고, N^2 풀이까지 낸 후 잠시 화장실을 다녀왔다. 갔다 오니 chanhw와 IBory가 G 얘기를 하고 있었는데, 무슨 대화 중이었는지는 모르지만 해시라는 단어가 잠깐 들렸고, 난 그걸 듣자마자 깨달음을 얻어 풀이를 찾았음을 강력하게 주장하고 바로 컴을 잡았다. G의 문제 세팅은 일종의 트라이로 볼 수 있는데, 저기서 롤링해시가 자연스럽게 되기에 N^2 풀이를 NlogN로 줄일 수 있다. 여기선 해시값들이 birthday paradox가 터지는 세팅이기에 내 최애 소수인 (1<<57)+1557을 해시 mod로 잡은 후 꾸역꾸역 필요한 구현들을 마쳤고, 떨리는 마음으로 제출했더니...한 번에 AC!

 

AC 직후 유일 7솔로 잠깐동안 전체 1등을 찍어서 지나가던 나정휘 님을 붙잡고 자랑했다. 최종적으로 G를 한 번에 맞은 팀이 우리밖에 없었고, 푼 시점도 굉장히 빨랐기에 패널티적으로 큰 이득을 봤다.

H (04:37) +3

G를 짜는 동안 changhw가 열심히 H 풀이를 만들어왔다! H는 대회 시작에 봤는데, 걍 쉬운데 할게 좀 많으니 나중에 해야지- 라고 생각하고 미뤘었다. 근데 다른 걸 다 짜고 돌아오니 스코어보드에서 H에 미친 불기둥이 그려져있어서 어라 이거 안 쉽나?라고 생각이 들었다. changhw도 저걸 의식해서인지 A4 반 페이지 분량의 케이스워크 및 구체화를 컴을 안 잡는동안 빡세게 해왔고, 풀이도 더 짜기 쉬운 걸로 잘 개조했다고 해서 믿고 IBory의 M을 도우러 갔다. 대충 IBory의 자신만만한 deg3이상짱짱잘됨풀이를 들은 후, 그럼이건어캄?을 시전하니 스턴이 걸려 :IBory_dead:가 되었고, 그러는 사이 changhw가 구현을 마쳐 제출했으나 아쉽게도 WA를 받았다.

 

하지만 이런 사태를 대비해서 틈틈히 내가 H의 체커를 만들어뒀었고, 그걸로 스트레스를 돌려봤는데...반례가 안나온다? 뭔가 이상해서 스트레스의 input과 output이 제대로 들어가나 확인하려고 아무 거나 찍어봤는데, 저때 우연히 찾기 힘든 반례가 띡 나와버려서 changhw와 함께 "ㅋㅋㅋㅋㅋ이게포로식가챠다허접들"을 외치며 코드의 오류를 고친 후 제출했다. 그랬더니 이번엔 오래 돌다가 TLE를 받았다? 잠시 멘붕이 왔으나, 다행히도 changhw의 #define endl "\n" 템플릿의 부재가 그 원인이었고, 저거까지 넣으니 정말정말 오래 돌다가....AC!

 

이후 IBory가 수정된 완?벽한 M 풀이를 짜기 시작했으나, 아쉽게도 짤 시간이 부족해 대충 4시간 59분에 M에 저희이만큼짰어요 코드를 내고 대회가 마무리 되었다. 대회 후 백준에서 6 wa 적립 후 맞았다고 한다.

2. 대회 후

WA가 살짝 있긴 했어도, 이정도면 팀으로 낼 수 있는 최고의 퍼포먼스를 냈기에 홀가분한 마음으로 의자에서 일어났다. 프리즈 전 등수는 3등이었고, 이를 토대로 예상 등수를 계산해봤다. 1등 2등 팀은 높은 확률로 (n>=8)솔을 했을 거라 우리보다 위에 있을 거라고 생각했고, 그 외의 팀의 경우 우리 팀과 패널티 차이가 꽤 커서 동솔일 때 우리가 더 등수가 높기에 [이거 3등으로 2등상 가능?]이라는 행복한 상상회로를 돌렸다. 대충 포스텍 사람들과 향유회 사람들 조금 만나면서 아니이놈들왤캐잘함 찬양을 들으면서 인사 좀 하다가, 늘 있는 기업세션 좀 듣고, 곧이어 스코어보드 언프리징이 진행됐다.

 

최종 스코어보드는 아래와 같다.

UCPC 본선 결과(Frozen)(Unfrozen)

 

스코어보드를 까보니, 상당히 의외인 결과가 나왔다. 개인적으로 무조건 9솔까지 했을 거라고 생각했던 우리 위 두 팀은 구현에서 다들 말리셨던 것 같고, 다른 대부분의 강팀들도 8솔에서 멈췄다. 얼떨결에 스코어보드 개봉 직전까지 1등 자리를 유지해버렸고, 혹시? 설마? 우승이니? 하는 마음이 들 때쯤 바로 BIGSHOT 팀이 J를 풀어버리며 바로 따잇당해버렸다. 저 팀은 무슨 프리즈 후 3솔을 했던데, 저 팀이랑 월파에서 맞다이를 해야 한다는 점이 상당히 두려운 부분이다. ibm선생님의 그냥PS접을게요 가 실제로 실천되기를 바래야겠다.

 

아무튼 그렇게 슼보 공개 이후 포스텍 사람들이랑 사진 한번 찍고, 치킨집 가서 밥 먹고 해산했다.

아래는 대회의 전리품들이다. 저번에 뭐 어디서 받은 갤럭시 버즈를 엄마한테 줬기에 헤드셋은 아빠 줄 것 같다.

 

3. 후기

진짜 상상도 못한 결과를 받아서 아직까지도 실감이 안 나는 상태이다. 오프라인 대회에서 이정도로 고점 퍼포먼스와 성적을 내본 게 거의 처음이라 되게 기쁘면서도, 이런 퍼포먼스를 작년 wf에서 낼 수 있었다면? 과연 올해 wf에도 이렇게 할 수 있을까? 같은 생각도 든다. 뭐 내 운빨이 함께라면 어떻게든 되지 않을까? 안되면 그냥 아이보리_gap changhw_gap 을 외치면 된다 ㅅㄱ.

 

운좋게 2등상을 받긴 했지만, 역대 UCPC에서 2등상을 받았던 사람들 라인업을 보면 포로 -> 그냥 PS력이 한참 떨어지는게 담백한 팩트인지라 스스로 너무 자만하지는 않으려고 한다. 대신 남은 1달 동안 PS 폐관수련 빡세게 해서 UCPC급 퍼포먼스, 혹은 그 이상을 WF에서 다시 낼 수 있게 하고 싶다.

 

끝!