UCPC 2025 예선 (Team SCP)

2025년 7월 13일 어제 UCPC 예선이 있었다.

결과는 9+653/11로 15등, 본선 진출권에 들었다. 만족스러운 결과다..!

팀 구성

parkky, ssamt님이 팀원을 구한다고 하시길래 냉큼 들어갔다. 다들 너무 고수분들이라서 잘 할 수 있을지 걱정되기도 했다.

SCP라는 팀명은 각자의 닉네임 이니셜을 따서 만들었다. 내가 만들었다😋

그 전 주 토요일에 팀 연습을 한 번 하고 바로 예선을 치게 되었다. 내가 ABCD, parkky님이 EFGH, ssamt님이 IJK를 보기로 하시고 들어갔다.

예선 과정

A (00:03)

놀랍게도 한 번 틀려버렸다. 1800초 이하의 시간에 뛰는지를 검사해야 하는데 딱 1800초에 뛰었는지를 검사했다. 예제만 돌려봐도 답이 나왔을 텐데 참 슬픈 일이다. 검토를 하려고 했는데 제출을 해 버렸다. Ctrl+Enter을 누르지 말자.

그 외에는 딱히 어려울 것 없는 문제였다. 다 더한 값이 1500보다 작은지를 검사하면 된다.

B, C, D 훑어보기

저번 UCPC 예선 때는 B가 어려웠다는 이야기를 들어서 한 번에 보지 않고 훑어보기로 했다.

B는 0이 있어야 최대한 턴을 많이 진행할 수 있다는 걸 관찰했다. 그리딘가? 하고 일단 넘어갔다.

C는 뭔가 이상한 자구나 스위핑 문제같은데, 내 수준에서 풀 만한 게 아닐 거 같아서 넘어갔다.

D는 스위핑같다고 체크하고 넘어갔다.

풀 만해보이는 문제는 B, D였고 B가 더 쉬워보여서 B -> D 순서로 풀기로 했다.

B (00:07)

먼저 예제처럼 하나라도 0이 있으면, 주변 값들을 0으로 만들 때까지 1씩 줄이고 … 를 반복해서 0을 옆 칸으로 퍼트리고 하는 식으로, 전체 값의 합만큼 턴을 진행할 수 있다는 걸 관찰했다.

0이 없을 때 2개를 모두 1씩 줄인 턴이 k개라면 진행할 수 있는 턴의 개수는 (전체 값의 합-k)가 된다는 것도 알 수 있다. 이걸 그리디하게 할 수 있을까.. 라고 생각해보니까 그냥 주어진 수들 중 가장 작은 수만큼만 1을 빼면 된다는 걸 깨달았다. 따라서 값은 (전체 값의 합-주어진 최솟값)이 된다.

D (00:35)

문제 지문이 좀 난해해서 이해에 시간을 겪었다. 결과적으로 구하는 것은 빈 구간들 사이에 길이 L짜리 작업을 잘 끼워넣을 수 있는 개수이고, 따라서 빈 구간의 위치나 시작점은 중요하지 않고 각 빈 구간의 길이만을 알면 된다는 결론을 얻었다. 빈 구간이 $i$개 있고 $i$번째 구간의 길이가 $a_i$일 때, 구해야 할 것은 \(\displaystyle\sum_{i=1}^n \max\{a_i-L+1, 0\}\)이 된다.

저걸 각 쿼리마다 구하면 ${\cal O}(QN)$이라서 느리다. 이를 해결하기 위해 빈 구간을 정렬한 후 이분 탐색으로 $a_i > L$인 $i$를 구해서, 누적 합으로 \(\left(\sum_{k}^n a_i\right) - (n-k+1)(L-1)\)을 구해주면 된다.

근데 인덱스 실수로 2번이나 틀렸다. 누적합을 할 때마다 IndexOutOfRange를 보는 거 같다. 정진해야겠다. 고치는 와중에 parkky님이 H번, ssamt님이 E번을 푸시고 도와준다 하셨는데 도와주시기 전에 고쳐서 낼 수 있었다.

뒤쪽 문제 훑어보기

이때까지 풀려있던 문제는 내가 푼 A,B,D와 다른 분들이 푸신 E,H,I였다. 남은 문제들을 한 번 훑어보기로 하였다. F,G 역시 다른 분들이 보고 계셔서 건너뛰었다.

그래서 남은 문제가 J와 K였는데, 그 중에서는 J가 K보다는 할만해보였다. 둘다 간단한 케이스를 손으로 그려보았는데 J는 실마리가 보였고 K는 더 어지러워졌기 때문이다.

J (01:44)

작은 케이스 ($t=10, 11, 100, 101_{(2)}$)를 손으로 그려보니 $b = \operatorname{bitcount}(t)$라고 할 때 그래프가 $2^b$를 주기로 가진다는 걸 관찰했다. 정당성을 증명하는 것도 어렵지 않았는데, 간선이 받아올림되는 경우가 $(2^b-1) \oplus t \longrightarrow 2^b$의 경우가 유일하다는 것을 보일 수 있다. 따라서 ${\cal O}(t)$ BFS 세 번 돌리는 풀이를 짰다.

그런데 예제가 안 나왔다. 15분동안 디버깅하다 BFS를 스택에 넣고 했다는 걸 깨달아서 바로 고쳐서 AC. deque에서 아이템을 꺼낼 때 popleft를 해야 하는데 그냥 pop을 한 게 화근이었다.

C

사실 아무리 봐도 자구 문제라서 다른 분들에게 떠넘기고 나중에 다시 봤는데, 그래도 문제를 좀 읽다가

딱 이 말을 하니까, “왜 저 생각을 못 했지” 하고 ssamt님이 바로 가서 구현하시더니 AC를 받으셨다. 너무 고수시다.

G를 열심히 깎자

그 사이 parkky님이 G를 풀고 계셨는데, 계속 TLE가 나서 더 나은 방법이 필요했다. 그래서 끝날 때까지 다 같이 머리를 맞대고 G를 깎기만 했다. 결국 끝날 때까지 G를 풀지는 못해서 9솔, 프리즈 전 15등으로 끝났다. ssamt님께서 이거 프리즈 끝나고 한 문제 더 푼 거면 등수가 안 바뀌겠다 하셨는데, 진짜로 정확히 15등이어서 놀랐다.

후기

처음으로 나가본 팀 대회라서 좀 긴장하긴 했지만 그래도 팀을 잘 만나 좋은 성적이 나온 거 같다. 본선에서도 이렇게만 잘 할 수 있으면 좋겠다..!