Day 239. UCPC 2023 예선 후기

장렬하게 예선탈락. 역시 세상은 넓고 괴물딱지들은 많았다. 내내 머리만 갸웃대다가 대회 시간이 끝났다. 수 회의 팀 연습으로 조금은 가다듬어졌다고 생각했는데 괴물들이 세상에 너무 많았다. 나는? 고물 정도 되는 것 같다.

포스터가 없어서... 이렇게나마 캡쳐를...

SUAPC 2023w에서 15위라는 성적을 거두고(이것도 팀원들이 다 했지만), 그 사이 루비도 두 문제 풀고 P3까지 찍어서 조금 많이 기고만장해 있었다. 기고만장? 기고만장까지는 잘 모르겠고, 본선 진출을 어쩌면 노릴 수 있지 않았을까 하는 막연한 기대감.

왜냐하면 나는 아직 PS 입문 1년차였기 때문이다. 작년 UCPC 본선 컷을 전혀 몰랐다. 작년 UCPC 셋 난이도도 몰랐다. 참가비도 없어서 약간 코포 레지스터하듯이 가벼운 마음으로 전 SUAPC 팀원들에게 콜을 넣었다. 우리 UCPC 나갈래요?

흔쾌히 승낙. 정보 받아 팀 등록은 내가 다 했다. 원래 이런 건 나가자고 한 사람이 하는 게 국룰이었다. 그러고 나서 지난 문제를 보는데 뭔가 이상했다. 얼라리? SUAPC 때보다 좀 많이 어려운 것 같은데? 큰일났다...

왜 큰일났느냐. 나는 (아직도) DFS와 BFS도 제대로 짤 줄 모르는 몸이었다. 이딴 게 어떻게 플래티넘을 달았지? 수학의 힘이올시다. 그래도 근래 배운 FFT라던가, 온라인 대회이니 남의 구현체를 뜯어(?)오면 되지 않을까 하는 나이브한 마인드. 물론 이 마인드를 고쳐먹었어도 4솔보다 더 많이 풀었을 거라고는 장담을 못 하겠는데...

사실 그 마인드가 아니었어도 배울 게 너무 많았다. 취사선택이 필요했고 아무래도 그래프는 blobdead가 훨씬 나아서 교집합을 적게 만들면 될 것 같다고 생각해서 기하 쪽을 공략했었다. 컨벡스 헐 쪽. 하나쯤은 나오지 않을까... 하고 생각했다. 기본 난이도가 꽤 되다 보니 성공만 하면 파괴력이 꽤 있을 거라고 생각했고... 근접하지도 않았다(ㅜ). 기하가 나오기는 했는데... 하... 젠장, 스몰 투 라지나 배워 올걸.

4솔 중에서는 가장 높은 수준의 페널티였다. 한 문제만 더 맞았으면 5솔 중에서도 상위권인 70등 내에 들 수 있었다는 소리다. 아쉬움이 큰 이유기도 하다. K가 그렇게 어려운 문제는 아니었는데 세 명이서 사이좋게 말렸다. ㅋㅋ.

우리 팀 blobsad가 푼 문제는 A, C, D, I의 네 문제이다.

대회 시작 전 지난 예선이 10문제이고 A번이 브론즈 문제인 거 감안하여 4문제, 3문제, 3문제를 끊어서 각각 blobdead(ez_code), blobglitch(parkhwijoo), 내(nflight11)가 보기로 했다. 그런데 11문제더라. 내가 K번까지 같이 잡기로 하고 서로 문제를 보기로 했다.

이게 웬걸? blobglitch가 맡은 세 문제는 지금 이 후기 쓰는 기준으로 D3 P3 D5다. 대형 폭탄을 넘겨 줘 버렸다.

 

A는 브론즈라서 내가 보기도 전에 답이 나왔다. 가장 쉬운 문제. 업솔빙 때도 그냥 풀 줄 알아야 코딩 짬 좀 먹은 사람이라는 타이틀을 지킬 수 있다. 아직 업솔빙 시작도 안 해서 안 풀려 있지만. 아무래도 이걸 대회가 아닌, 마음 편히 잡을 수 있는 환경에서 틀리면 조금 많이 자존심이 상해야 한다.

D도 blobdead가 감이 잡힌다 하면서 휘리릭 탁 하고 구현을 마쳐놓았었다. 저거 도대체 어떻게 하는 거지. 지금도 모르겠다. 실버? 3??? 모르겠다... 아직 기여가 정착되지 않아서 그런 건지 아닌 건지. 블루의 실력을 여실히 맛보았다.

I는 내가 구현까지 마친(?) 문제. 물음표가 나온 이유는 어느 정도는 인터넷의 도움을 받았기 때문이었다. 어떠한 list \(\text{arr}\)에 대해서 다음 식의 값을 구하는 게 중요한 문제였다. \[\max\{\text{arr}[i]-\text{arr}[j]\mid i>j\}\] 그런데 난 이걸 \(O(N^2)\)으로밖에 구현하지 못했고, 최소한 \(O(N\log N)\)이 필요한 상황에서 저걸 넣으면 문제가 터져나간다. 결국 인터넷의 도움을 받았다. 아이디어는 내가, 구현은 stackoverflow의 누군가가 맡은 셈이나 다름없다.

C는 문제가 더럽게 나온다고 생각해서 차음에 던져두고 E를 보고 있다가 내가 이렇게이렇게 하면 될 것 같은데 구현은 못하겠다고 말하니 그거 MST 아니냐는 답이 돌아왔다. 이런 젠장. MST가 맞았네? 실수 가중치가 돌아가는지, 0 가중치가 돌아가는지 두 번 묻고 나서 그럼 가중치 구하는 함수는 내가 만들겠다고 했다. 역사인함수 들어가는 더러운 꼴이라 blobdead는 가중치 구하는 거 빼고 나머지를 다 하기로 했다. 내가 우선 가중치 만드는 함수 구현해서 카톡으로 전송했고, 받은 blobdead가 멋들어지게 마무리.

이 시점에서 77분이 지나 있었다. 반환점에 도달했다는 것.

 

blobglitch와 남은 시간 동안 못 푼 문제를 와리가리하면서 눈팅했다.

F는 transpose랑 한 칸씩 움직이는 거로 구현해도 터질 테니 다른 좋은 풀이가 있는지 머리를 쥐어짰지만 이렇다 할 것은 찾지 못했다.

E는 제곱의 기댓값이라 망한 문제. 그냥 기댓값이면 매우 쉽게 풀 수 있었는데(매우는 좀 오바인가? 라고 생각하겠지만 E번 난이도가 D3이니 비교하면 매우 쉬운 게 맞다.) 하필이면 제곱이라. 공분산이 0이 아닐 테니 문제는 확실히 복잡해지겠지만 운이 좋으면 돌파구를 생각할 수 있지 않을까? 하고 틈 날 때마다 기웃댔는데 마땅히 좋은 방법으로 흘러가지는 않았다. 

J는 단 한 팀도 프리즈 전까지 풀지를 못해서 손조차 대지 않았고, B는 왜 푼 사람이 많은지 아직도 의문이다. 스몰 투 라지가 그렇게 웰노운인가요?

K는... 지금 돌아보니 무슨 짓을 했는지도 기억이 안 난다. 마지막에 이분탐색을 한다는데, 머릿속에 들어올락 말락... 머리가 많이 굳었다 ㅋㅋ...

 

이번에는 오픈콘 전에 스코어보드 프리즈를 까지 않아서 두근두근한 중계도 없었다. 이건 본선 진출자들이 누리는 특권이니 어쩔 수 없다.

 

85등으로 탈락하긴 했지만 K번을 제외하면 풀 수 있었던 문제는 모두 풀어내서 큰 여한이 없다. 다만 이제 고급 알고리즘들도 머릿속에 집어넣을 때가 왔을 뿐. 스몰 투 라지, 세그먼트 트리, 스위핑(이건 고급인가?), 기타등등... 

더 정진해야지. 내 부족함이 부각된 대회였다고 생각한다.