2023 ucpc 예선 후기

작년에는 대회를 많이 쳤는데 (ucpc, scpc, icpc, 모비스, 코드잼, RUN spring/fall contest,  등등) 올해에는 아직까지는 참가한 코딩대회가 별로 없었다(코드잼 멸망, RUN spring contest 출제, scpc 미뤄짐). 오랜만에 큰 대회를 하니까 신났다.

 

ucpc 예선이라고 전날에 딱히 공부를 하지는 않았다. 전날에 플로우를 열심히 외웠던 모비스와는 ucpc는 내 취약분야인 문자열 / 기하 / 플로우 문제를 잘 안 내고 내더라도 안 풀어도 될만큼 어렵게 내기 때문에 걱정이 안 됐다. 그리고 만약 낸다고 하더라도 팀원들한테 던져주면 슥삭하고 풀어줄 수 있기 때문에 덜 걱정되었다. 나름 오랜만에 cp를 해서 그런지 대회 1시간 전에는 조금 긴장하기는 했다.

 

다른 팀들은 오프라인으로 모여서 예선을 치지만, 우리 팀은 디스코드 통화방에 모여서 예선을 쳤다. 디스코드를 사용하면 집 침대에 누워서 생각할 수 있다는 점이 좋은 것 같다. 대회 시작 3분전에 각자 통방에 모여서 누가 ABCD를 풀지 정했다.

 

대회가 시작하고 ABCD를 풀기로 한 나는 가장 쉬워보이는 제목을 가진 A번을 보자마자 호다닥 코딩했다. 코딩 중간에 한자 키를 잘못 누르고 취소하는 방법을 몰라서 코드블럭을 한 번 껐다 켰다. (3분)

 

B번을 봤는데 변수가 3개나 주어지고 (N, M, K) M 범위가 이상하길래 C번부터 봤다. C번은 보자마자 수학으로 원 2개 감싸는 곡선 둘레를 구하는 것에 mst를 얹으면 된다는 것을 깨닫고 코딩을 하면서 식정리를 했다. 두 원이 겹치면 간선 길이가 0이라는 조건을 double로 처리하면 안된다는 것, arccos가 나오는 것 등등해서 식정리가 조금 귀찮았던 것 같다. 그래도 쉬운 문제니까 빨리 풀었다. 원큐에 AC가 안 뜨면 실수오차 해서 좀 귀찮아질 뻔했는데 다행히 AC가 바로 떴다. (19분)

 

arccos과 같은 수학 식정리를 하는 사이에 마루이가 I를 잘 밀어줬다. (14분) 김지훈은 G번을 보고 있었다. 슼보에 아직 안 풀려있길래 좀 어려운 문제인가 했다. 말하기로는 구현이 더러운 문제라고 했던 것 같다. 이렇듯이 스코어보드에 별로 안 풀려있는 문제를 자신감 있게 공격하는 것이 상당히 놀랍다. 과거 런 가을 대회에서도 이렇게 해서 F번을 퍼솔했는데 이런 거를 보면 대단한 것 같다.

 

슼보에서 D가 가장 많이 풀려있었지만 마루이가 먼저 잡고 있어서 두 번째로 많이 풀린 K를 밀러 갔다. K는 입력이 N 하나에 길이 N의 배열이 주어지는 깔끔한 문제여서 읽으면서 아주 기분이 좋았다. 읽어보니까 답에 대한 파라메트릭 서치를 사용하고 싶었고, 답을 고정하니까 priority queue로 그리디하게 풀고 싶었다. 그리디가 성립하는지는 잘 모르겠는데 머릿속으로 exchange argument가 성립하는지 짧게 생각해보고 적당히 되는 것 같길래 코딩에 들어갔다. 전날 모비스에서도 pq 그리디로 1번을 밀었는데 비슷한 문제가 나와서 그런지 깔끔하게 코딩이 잘 됐다. 깔끔하게 AC를 띄웠다. (27분)

 

이쯤되니까 스코어보드에 띄워진 초록색 카펫을 따라갈 수 없게 되었다. 그래도 누군가가 풀어놓은 F번을 푸는게 나을 것 같아서 F번을 잡았다. 대충 보니까 앳코더에서 비슷한 문제를 풀었던 것 같다. 그리드에 있는 원소들은 그대로 두고 왼쪽 위 시작점을 옮기는 테크닉을 그대로 사용했다. 홀짝 나누는 것은 그리드를 홀짝으로 나누어서 4개의 sub-그리드를 만들면 그냥 풀릴 것 같아서 바로 코딩에 들어갔다. 코딩을 하고 예제를 넣으니까 예제가 안 나왔다. printf 디버깅을 좀 해보니까 그리드를 홀짝으로 나눈다고 원소들이 나누어진 그리드 안에서 노는 것이 아니었다. 그래도 각 sub-그리드별로 매칭되는 sub-그리드를 관리해주면 풀이를 되살릴 수 있어서 덕지덕지 코드를 추가했다. 잔실수가 많이 날 수 있는 타입의 코드여서 좀 걱정을 했는데 이것도 AC를 원큐에 띄웠다! WA가 나오면 90줄의 순수한 애드혹 코드를 볼 생각에 걱정이 좀 있었다. 오늘은 컨디션이 좀 좋은 것 같았다. (54분)

 

마루이는 중간에 B번에서 시간초과로 고통받고 있었다. 도와주러 가고 싶었지만 나도 F번에서 다양한 인덱스들과 함께 고통받고 있어서 도와주러 못 갔다. Nlog^2N 코드가 TLE가 뜬다길래 조금 걱정하고 있었는데 그냥 유파 압축을 안해준 간단한 실수였다. 다 풀고 도와줘야지 했는데 F를 풀기 전에 이슈가 해결되었다. (41분) 김지훈은 G번을 풀고 (무려 퍼솔!) 다른 문제를 보고 있었다. (52분) 마루이가 H번을 좀 보고 있어서 J번(D3)과 E번(D3)을 번갈아서 보고 있었다고 한다. 

 

이쯤되니까 우리 팀이 문제 수 차이로 압도적인 1등이었다! 신이 나서 빠르게 캡쳐를 했다.

55분대 대회 상황

나랑 거의 동시에 문제를 푼 김지훈은 나한테 E번을 던져줬다. 읽어보니까 제곱값의 기댓값을 구하라는 문구에 998244353이 있는 것을 보고 신나서 E번을 풀겠다고 했다. 기댓값의 선형성을 사용해서 식전개를 하면 풀릴 것 같아서 노트에 열심히 식정리를 하고 있었다. 근데 이게 식정리가 만만치 않았다. aabc aabb abcd와 같이 서로 다른 숫자를 뽑는 가짓수를 세야 되는데 abcd의 케이스에서 이항정리에 전체에서 나머지 빼는 아이디어를 사용하니까 구해야할 값이 대략 6개 정도 되었다. 식정리를 열심히 하고 코딩을 했는데 예제가 안 나왔다! 길고 긴 식정리 코드들의 특징은 디버깅이 어렵다는 것이다. 그리고 이번 예제 2번은 역시 손으로 디버깅할만한 사이즈가 아니어서 랜덤하게 새로운 예제들을 만들면서 쉬운 디버깅용 예제가 나오기를 빌었다. n=3, A=[1, 1, 1]에서 반례가 나오길래 디버깅을 해보니까 식정리가 어디선가에서 틀렸다는 결론이 나왔다. 다시 식정리를 하고 코딩을 하고 예제를 넣어봤는데 다시 예제가 안 나왔다! 이때부터는 나의 길고 긴 코드가 틀렸을지 풀이가 틀렸을지 감을 못 잡고 있었다. H번을 풀고 J번을 보고 있는 마루이한테 나의 풀이를 설명하다보니 틀린 점이 눈에 보였다. 풀이를 고치고 다시 코딩을 했는데 예제가 또 안 나왔다! 100줄의 수학식을 나열한 코드의 중간에 +가 *로 쓰여있는 것을 찾으니까 그제서야 예제가 나왔다. 이번에는 진짜 맞았으면 좋겠다 하면서 제출을 했는데 원큐에 AC가 떴다! 100줄의 수학식과 내 풀이를 의심하지 않아도 되어서 너무 기뻤다. (152분)

 

남은 문제는 J번 밖에 없었다. 시간이 28분 밖에 안 남았기도 했고 10문제를 풀기도 해서 안일해졌다. 그래도 아무것도 안 할 수는 없으니 남은 시간동안 팀원들과 풀이 구상을 했다. knuth optimization, dnc optimization 등의 아이디어와 함께 O(n^2)의 풀이를 최적화해서 우겨넣을 생각과 스파스 테이블 형식의 dp를 잘 비빌 생각을 동시에 하고 있었다. 그래도 시간이 부족해서 코딩도 제대로 못 해보고 끝났다.

 

대회가 끝나고 모든 문제에 제출한 팀들이 상위권에 조금 보이길래 올솔이 나왔을 것이라고 생각했다. 1등은 아니겠지?라는 생각도 하면서 좋은 컨디션의 대회를 친 팀원들과 자축을 했다. 좀 놀고 나서 11시에 슼보를 보니까 1등이었다. 예상도 못하고 있었는데 1등을 하니까 백준 문제를 열심히 해서 받은 선물 같았다. 앞으로도 열심히 oi문제들을 밀어야지.

 

1등 움얌얌