2024 UCPC 본선 후기

예선 후기 : https://leo630.tistory.com/224

서론

4번째 UCPC 본선에 참가했습니다. 월파를 제외하면 아마도 1557 팀으로 치는 마지막 대회입니다. 서론에 쓸 내용들은 대부분 위에 링크한 예선 후기에 잘 나와 있으니 참고해 주세요. 

 

대회 전

사실 요 근래 몇 주간 저의 정신 상태는 번아웃, 또는 슬럼프, 혹은 둘 다라고 할 수 있을 정도로 정상이 아니었습니다. 그 원인은 UCPC 예선부터 이어진 4연 삽질으로, 2번째였던 코포 라운드까지는 나름 해학적으로 넘기려 노력하였으나 이어진 2연타에 정신을 잃고 말았습니다. 이에 해당하는 대회는 각각 7/27일, 28일에 열린 SCPC 2차 예선과 코드포스 Pinely Round 4입니다. SCPC에서는 정말 많은 실수와 오만함으로 4년만에 본선 티켓을 걷어차는 기행을 선보였고, 코드포스에서 역시 이상행동을 연발한 끝에 다른 한국인들이 다 오르는 와중에 퍼플 퍼포먼스를 뽑아내는 기염을 토했습니다. 둘 모두 자세히 설명하자면 길지만 부끄럽고 추하기 때문에 이만 줄이겠습니다. 특히 두 코드포스 라운드는 셋 운도 꽤 괜찮았기 때문에 제정신으로 쳤더라면 이미 2400점이었다는 사실이 정말 뼈아프게 다가옵니다. 이 내용을 블로그에 올려야 하나도 꽤 고민했지만, 가린다고 가려지는 것이 아니기 때문에 그냥 시원하게 밝힙니다. 그런 까닭에 올해 SCPC 후기는 없습니다 죄송합니다..

 

아무튼 이러한 이유, 그리고 다른 일정들로 인해 저 기간동안 PS를 거의 하지 않았습니다. 다행인 것은 제가 내려온 대신 두 팀원의 폼이 꽤 올라왔다는 것으로, 자꾸 저를 갈군다는 점만 빼면 좋은 소식이라고 할 수 있었습니다. 다른 두 명이 잘할수록 저는 어차피 코딩만 열심히 하면 되기 때문에 & 1컴 대회기 때문에 대회가 망할 거라는 생각은 들지 않아서, 목표는 팀명만큼 = 메달을 따기 위해 필요한 정도 = 2등상으로 잡았습니다. 

 

대회 날에는 포스텍 팀들 & 다른 아는 분들과 간단히 인사를 한 후, 다른 팀들의 전력을 분석하는 데에 시간을 보냈습니다. UCPC는 참가자 신상을 본선에 가서야 확인할 수 있기 때문에 상당히 중요한 과정입니다. 이를 마친 결과 강한 팀이 꽤 많다는 것을 깨닫고 목표를 2등상에서 3등상으로 수정할 수 있었습니다. 

 

대회 중

 

문제: https://www.acmicpc.net/category/detail/4263

 

petamingks가 앞, kwoncycle이 가운데, 제가 뒤를 보고 시작했습니다.

 

~0:18 (1솔브)

J~M중에서 먼저 읽은 문제는 J와 L으로, J는 전형적인 트쿼 문제로 보이지만 풀이가 바로 떠오르지 않았고 L은 이분 매칭 문제라는 것을 알 수 있었습니다. 그 사이 petamingks가 솔브가 나온 D를 빠르게 풀었습니다.

 

~1:19 (3솔브)

첫 솔브 후 꽤 오랜 시간을 1솔브로 있었는데, 이 시간동안의 타임라인은 다음과 같습니다. 먼저 kwoncycle이 F 풀이를 찾아 코딩을 시작했지만, 마무리가 되지 않은 채 나왔습니다. 이후 제가 들어가 L에 필요한 플로우 코드를 열심히 치던 도중, petamingks가 E를 풀었고 코딩이 짧다고 해 양보했습니다. 허나 예제가 잘 나오지 않았고, 그 사이 kwoncycle이 A 풀이를 찾아 E를 프린트한 후 컴퓨터를 잡고 코딩했습니다. kwoncycle이 A를 뚝딱 짜서 맞았고, 3분 후에 E의 디버깅 역시 끝나 AC를 받을 수 있었습니다.

 

~1:57 (5솔브)

이후 제가 컴퓨터를 잡아 L 코드를 완성했지만, TLE를 받았습니다. 이때 kwoncycle의 C 풀이가 있었기에 바로 컴퓨터를 양보했고, 나오자마자 디닉을 BFS로 바꾸면 된다는 것을 깨달았습니다. kwoncycle은 C를 빠르게 코딩했지만 틀렸고, 바로 컴퓨터를 뺏어 RTE를 한 번 받은 후 L을 맞았습니다. 5분 후 kwoncycle이 C의 오타를 찾아 맞았습니다. 

 

~3:21 (7솔브)

5문제를 푼 후 남은 문제는 다음과 같았습니다.

F: kwoncycle이 관찰 및 코딩을 끝냈으나 마무리 부분이 부족

H: 레전드 기하 문제, leo020630이 코딩해야 함

J: 트쿼 문제, leo020630이 풀고 코딩해야 함

M: 다 잘 푸는데 뭔지 모르겠는 문제

 

우선 상황이 먼저 해결된 문제는 F로, 마무리 부분이 다행히도 제가 아는 내용이었기에 듣자마자 kwoncycle에게 설명한 후 kwoncycle이 코딩에 들어갔습니다. 이후 저는 petamingks와 M을 열심히 풀었으나 꽤나 오랜 시간 진전이 없었습니다. 다행히 petamingks가 핵심적인 관찰을 해냈고, 이를 토대로 \(O(Nlog^2N)\)풀이를 짰으나 TLE를 받았습니다.  F 역시 kwoncycle의 레전드 코딩 실수로 계속 WA를 받아 컴퓨터가 비는 상황이 발생, 저는 더 늦기 전에 H를 짜겠다고 선언한 후 코딩에 들어갔습니다.

 

다행히 프린트한 코드를 토대로 (4번 틀린 끝에) F의 오타를 모두 잡아 AC를 받았으며 kwoncycle이 M의 시간 복잡도를 \(O(NlogN)\)으로 줄여 M 역시 맞을 수 있었습니다.

 

~4:48 (9솔브)

이후 저는 H와의 사투에 들어갔고 두 팀원은 남은 문제 중 가장 많이 풀린 J에 달라붙었습니다. 사실 제 블로그를 열심히 보신 분들은 아시겠지만 상당히 암울한 상황인데, J 같은 문제는 보통 저에게 일임되는 경우가 많았기 때문에 두 팀원이 풀어줄 확률이 상당히 낮았습니다. 두 팀원들도 그것을 알기 때문에 petamingks가 잠깐씩 B를 보기도 했지만 결국 포기하고 J에 올인했습니다. 다행히 1시간 정도를 남긴 시점에 petamingks가 기적적으로 풀이를 찾아 H 코딩이 끝나면 바로 짜기로 결정했습니다. 저는 그 사이 여러 예제를 만들어 보며 H 코드를 완성, 제출했지만 WA를 받아 바로 J 코딩에 들어갔습니다. 해야 할 것이 정말 많은 풀이를 전달받고 아찔했지만 최대한 빠르게 코딩해 30분만에 완성, 바로 제출했지만 다시 WA를 받았습니다.

 

모두 마음이 꺾일 법도 한 상황이지만, 저와 kwoncycle이 J 페어 코딩을 하는 동안 petamingks는 H 예제를 만들어 두었습니다. 이를 통해 H의 틀린 부분을 잡을 수 있었고 4시간 40분 시점에 H에서 AC를 받았습니다. H 에러를 고치는 동안 kwoncycle은 J 예제를 만들었고, 아쉽게도 모두 맞게 나와 당황했지만 하노이에서 쓴 인간 스트레스 방법 (모든 정점 쌍 다 넣어보기) 를 통해 틀린 부분을 찾아 고친 후 제출했습니다. 그렇게 4시간 48분에 마지막 AC를 받으며 대회를 마쳤습니다. (이때 소리를 좀 질렀는데 생각보다 너무 크더라고요.. 죄송합니다)

 

 

스코어보드 공개 때에는 1557 팀으로 친 다른 대회 (서울 리저널, 플레이오프) 와 마찬가지로 4등상-5등상 경계에 걸린 상황이기 때문에 마음을 졸이며 지켜봤습니다. 사람들이 너무 잘 풀어서 당황하기도 했지만, 결과적으로 10등에 안착해 4등상 막차를 탈 수 있었습니다. 2021 UCPC에 Hyperbolic 선배와 같이 나가 10등을 했을 때에는 제 성과가 아닌 기분이었는데, 3년의 시간이 지나 같은 성적을 거두니 감회가 새로웠습니다.

 

추가로 뉴트렌드의 역전 우승 + 우승 소감이 정말 인상깊었습니다. 진짜 저 팀은 뭘 해도 하겠다는 생각이 드네요.. 저희 팀원들은 어떨지 모르겠지만 저는 그냥 숭배하기로 했습니다. (당연하지만) 월파 가서도 잘 하길 바랍니다. 싸인 받아 올게요

 

대회 후에는 포스텍의 선배 마라탕 사주세요 팀 + 그냥 놀러온 menborong 선배 + 연세대의 대회나갈때마다팀명바뀌는팀, xladlfma 팀과 뒷풀이를 갔습니다. 팀 연습을 같이 하면서도 베트남에서 잠깐 뵌게 다였는데 이번 기회에 이야기 나눌 수 있어서 좋았습니다.

 

문제별 요약

문제	풀이	코딩	비고
A (P4, 1:16, +)	kwoncycle	kwoncycle	재미있는 코포식 구성적 문제다. 대회 때에는 기본적인 관찰만 해서 주었더니 kwoncycle이 알아서 잘 풀었다.
B (D2, -, upsolved)			대회 중에는 petamingks가 잠깐씩 봤는데, 풀이 설명 시간에 자기 생각이랑 똑같다고 해 조금 아쉬웠다. 문제가 올라온 후 9000B를 짜고 업솔빙했다.
C (G1, 1:57, +1)	kwoncycle	kwoncycle	퍼즐 느낌의 구성적 문제다.
D (G4, 0:18, +)	petamingks	petamingks	셋에서 가장 쉬운 문제다. 기본적인 테크닉을 요구하는 교육적인 문제인 것 같다.
E (P4, 1:19, +)	petamingks	petamingks	직관이 필요한 게임 이론 문제다. 역시 petamingks가 잘 풀어주었다.
F (P1, 3:02, +4)	kwoncycle, leo020630	kwoncycle	색상에 대한 관찰을 하면 outerplanar graph를 세 가지 색으로 칠하는 문제가 된다. 소통이 조금 빨리 되고 코딩을 잘 했다면 퍼솔이었는데 아쉽다.
G (D3, - )			문제를 읽지 않았다. 풀이 설명을 들은 후 좋은 판단이라고 생각했다.
H (P2, 4:40, +2)	leo020630	leo020630	그냥 시키는 대로 하면 되는 기하 문제인데, 케이스 처리가 이를 어렵게 한다. 왜 이런 문제를..
I (D5, - )			대회 중에는 문제를 읽지 않았다. 풀지 못한 문제 중 가장 쉬운 문제라 읽지 못한 것이 아쉬웠다.
J (P1, 4:48, +1)	petamingks	leo020630	풀이가 다양한 트리 문제이다. 우리는 sparse table을 응용한 케이스 워크 풀이로 해결했는데, 정해가 상당히 아름다워 감탄했다.
K (D2, - )			문제를 읽지 않았다. kwoncycle이 읽었으면 좋았겠지만 시간이 너무 부족했다.
L (P3, 1:52, +2)	leo020630	leo020630	아이디어 하나를 요구하는 이분 매칭 문제이다. 대회 중에는 쓸데없이 디닉을 쓰고 코딩 실수도 해서 2번이나 틀린 후 늦게 맞췄다.
M (P4, 3:21, +2)	petamingks, kwoncycle	leo020630	관찰이 필요한 그리디 문제이다. 우리 팀은 cost가 convex하다는 신기하지만 정해에는 필요 없는 관찰을 해 이분 탐색으로 해결하였다.

 

느낀 점 + 피드백

 

여태까지 치른 팀 대회 중 후기 작성이 제일 힘든 대회였습니다. 보시다시피 머신 운영이나 의견 교환 등이 굉장히 활발하고 빠른 속도로 이루어졌기 때문에 정리가 쉽지 않았네요.. 아마 빠진 부분도 꽤 있을 것이라 생각됩니다. 팀적으로 못한 부분은 코딩을 좀 못했다 말고는 크게 없는 것 같은데 등수가 생각보다 낮아서 새삼 UCPC는 쉽지 않음을 느꼈습니다. 코딩이 말리지 않았다면 페널티로 3등상으로 올라가거나, B / I / K를 푸는 고점이 있었을 것 같아 아쉽습니다. 그래도 2명이 크게 말렸고 + 비교적으로 약한 K - 스타일의 셋이었음에도 불구하고 복구를 잘 한 점에서 팀이 꽤나 강해졌다는 사실을 다시금 알 수 있었습니다.

 

대회는 얼마 없는 팀 단위 온사이트 대회인 만큼 여전히 재미있었습니다. 옛날에는 아는 팀도 하나 없어서 조용히 대회만 치고 왔는데 4년 굴렀더니 아는 분들이 좀 생긴 점도 좋았습니다. 특히 이번 UCPC는 개최 자체가 좀 힘들었다고 들었는데 운영진 + 후원자 분들이 정말 수고해주신 것 같습니다.

 

ICPC에서 만나요~