UCPC 2023 예선 후기

올해부터는 나도 UCPC 참가 자격이 생겼다. 팀은 교내에서 구하기가 쉽지도 않고, 나 또한 폼이 많이 죽었기 때문에 PS 향유회 톡방 사람들과 (지금은 톡방을 나왔지만) 잔잔하게 치기로 했다. 팀원은 amsminn과 ljwljw8541이고, 편의상 각각 채완과 장어라고 칭하겠다.

 

작년 정올 이후, 간간이 치는 코포를 제외하면 PS에 투자한 시간이 장담컨대 20시간도 안 됐기 때문에 걱정을 많이 했다. 특히나 대학에 오고 나서는 여러모로 할 일이 많아서 인생 그 자체였던 PS를 거의 거들떠보지도 않았다. 그런데도 욕심만 많아서 UCPC 같은 큰 대회의 본선행 티켓을 놓치고 싶지는 않았다.

 

예선은 홍대의 스터디룸에 모여서 치기로 했다. 대회가 2시에 시작하는데 아침에 오버워치 하다가 시간 계산을 잘못해서 1시 55분에 겨우 도착했다. 채완이는 지하철 배차 억까를 당해서 25분 정도 지각했다.

 

아무래도 코딩이 가장 빠른 내가 A를 잡기로 했고, 장어와 채완이가 골드 이하를 미는 동안 내가 나머지 문제의 풀이를 내는 것이 기본 전략이었다. 그러나 채완이가 언제 올 수 있을지 모르는 상황에 장어 혼자 초반 슼보를 따라가는 것은 무리이기도 하고, 내가 쉬운 문제를 빠르게 풀어버리면 문제없다는 생각으로 그냥 슼보를 따라갔다. 근데 이게 사람 심리상 슼보에서 우후죽순 풀리는 문제를 두고 다른 문제에 집중하는 게 말이 안 되는 것 같다.

 

스팟보드가 타임라인을 보는 방법이 없는 것 같아서 그냥 기억나는 대로 적겠다.

 

A는 mod 4에서 돌리면 되는 구현이라 빠르게 풀었다. 거의 같은 문제를 어디선가 풀어본 것 같다.

 

B, C를 차례로 읽다가 D가 풀려서 봤더니 풀이가 자명했다. 작은 타일의 한 칸씩 가장 많은 걸로 바꿔주면 되고, 실수 없이 맞았다.

 

I도 풀려서 장어에게 맡겼었는데, 풀이가 잘 안 나오는 듯 해서 도와주러 갔다. 생긴 게 정리해서 같은 꼴 만드는 유형이라 어렵지 않게 풀었다. 근데 막 스위핑하면서 머리 쓰기 싫어서 세그를 가져다 썼다. 급한 마음에 배열 크기를 잘못 잡아서 런타임 에러를 받는 이슈가 있었다. 여기까지 20분 안쪽으로 걸렸다.

 

C가 기하여서 내가 풀어야겠다고 생각 중이었는데, 마침 슼보에서도 풀리길래 잡았다. 일단 겹치는 여부 판별은 적당한 기하 지식을 활용하면 되고 그 이후를 그룹 지어서 생각해 보면 최소 스패닝 트리와 같은 상황이며 실제로 그렇게 하면 된다. 그런데 구현 과정에서 실숫값을 정수형에 저장하거나, acos()의 반환값이 60분법이라고 착각하는 등의 이슈가 있어서 조금 지체되었다.

 

10분쯤 B가 풀리길래 (난 그래프 풀기 싫어서) 채완이한테 오면서 B를 읽어보라 했다. 25분쯤 채완이가 도착하면서 mst, dsu, s2l 로 된다는 얘기를 했고, 나는 오버킬 같다고 했다. 암튼 그러고 열심히 구현하길래 난 내 할 일 했더니 AC를 받아왔다. 그리고 그게 정해였다. 왤캐 잘함?

 

이쯤에서 쉬운 문제는 K 정도만 남았고, 나는 K를 채완과 장어에게 던져준 뒤 그나마 풀린 F를 보러 갔다. F는 이상한 연산이 잔뜩 있는 게 내가 풀어야 하는 문제였다. 처음에는 '연산이 교환법칙 같은 게 성립하나?' 같은 생각을 하다가 5번 쿼리의 존재로 그런 식으로는 못 푼다고 결론지었다. 홀짝이 나뉘어 있다는 사실에 집중해서 고민해보니 홀짝성이 같은 칸들은 항상 같이 움직인다는 사실을 관찰할 수 있었다. 그래서 $(0, 0), (0, 1), (1, 0), (1, 1)$의 4칸만 어떻게 움직이는지 시뮬레이션하면 모든 칸의 위치를 알 수 있으므로 5번 쿼리를 잘 처리할 수 있다. 구현은 살짝 까다로웠지만 크게 말리지 않았다.

 

내가 F를 고민하는 동안에 채완이가 K가 파라메트릭 서치라는 얘기를 해서 봤더니 맞는 것 같았다. 나는 거기다가 결정함수는 DP로 짜야할 것 같다는 소리를 했고, 채완이는 그리디를 주장하는 것 같았지만 받아들였다. 그래서 채완이가 DP + Parametric Search를 짜서 K를 잘 풀었다. 그러나 정해는 그리디였고, 디피 접근이 틀린 건 아니지만 그리디 풀이가 더 자연스러워서 내가 오히려 방해를 한 것 같다. 깊게 고민하지 않았으면 그냥 팀원을 믿고 맡기는 게 우월 전략이라는 배움을 얻었다.

 

F를 풀면서 7솔을 달성했을 때 1시간 20분 정도가 남았었고, 우리 팀은 페널티가 아주 좋은 상태로 슼보를 잘 따라와서 본선 진출을 거의 확신했다. 남은 문제 중에는 H가 꽤 풀렸으나 출력 형식부터 귀찮게 생겨서 팀원들에게 넘겼다. 다음으로 풀린 G를 읽었는데 별로 좋아하는 스타일이 아니고 딱히 생각나는 풀이도 없었다. 사실 E를 풀고 싶었다.

 

E는 개꿀잼 기댓값 문제였다. 제곱의 기댓값을 바로 계산하는 건 어려우니까 반전수를 여러 변수의 합으로 나타낸 뒤 제곱하고 전개해서 구하자는 전략을 세웠다. 나름 티피컬한 방법이다. 그리고 울프람 알파를 동원해서 한 시간 동안 정말 열심히 식을 정리하고, 코드를 완성했지만 예제가 나오지 않았다. 대회 종료가 10분이 채 안 남은 시점에서 한 케이스를 중복으로 계산했음을 발견했고, 빠르게 고쳤으나 여전히 예제가 나오지 않았다. 그렇게 틀린 부분을 계속 찾다가 대회가 끝났다.

 

H는 맞는 관찰을 했으나 구현하는 게 쉽지 않던 모양이었다. 시간이 여유로웠다면 E, H 둘 다 해결 가능성이 있었을 것 같아 아쉬웠다.

 

결과는 30등으로, 7솔 1등을 하고 본선 진출에 성공했다. 기대보다 높은 등수를 받아서 상당히 만족스럽다.

 

이번 대회는 운이 좋았던 것 같다. 전체적으로 나와 잘 맞는 유형의 문제들이 출제되었고, 코딩이 말리는 일도 없어서 페널티 싸움에서 우위를 점할 수 있었다. 또한 팀원들도 실수 없이 문제를 잘 풀어주었다. 그러나 결과적으로 보면 플레 이상을 한 문제 밖에 풀지 못했으며 수학 문제에 꼬라박다가 대회 중후반을 날렸다. 차라리 E를 버리고 G를 도전하던가 H를 같이 코딩했으면 더 좋은 결과를 얻지 않았을까 싶다.

 

본선은 전체적으로 난이도가 상승하는 데다 3인 1컴이기 때문에 예선과는 다른 전략이 필요하다. 아마 그때는 진짜로 플레를 막힘 없이 풀어내야 수상권에 들 수 있을 텐데, 연습을 얼마나 할 수 있을지 고민이다.