2026 RUN Spring Contest 후기

2026년 5월 3일, 올해 역시 KAIST RUN Spring Contest가 있었다. 작년에 이어 올해도 부원으로써 참가하게 되었다. 그동안 블로그를 유기한 이유는 블로그 설정을 뭔가 잘못 만져서 그걸 고칠 때까지 글을 쓸 수 없었기 때문이다 ㅜㅜ 어떻게 잘 처리해서 블로그 폰트 변경 작업까지 완료했다!

닉네임은 σㅏe=>v로 참가했는데, 요즘 PS보다 PL에 빠져있어서 PL에 나오는 “$\sigma$라는 환경에서 $e$라는 식을 평가하면 $v$라는 값이 된다”라는 의미의 $ \sigma \vdash e \Rightarrow v $라는 식을 적당히 유니코드로 쓴 것이다. 사실 그냥 특수문자가 많은 식을 스코어보드를 깔 때 어떻게 읽을지 궁금했다.

한편, 이번 학기를 좀 바쁘게 사는 중이어서 이 대회가 APAC 이후로 처음으로 나가는 CP 대회였다. 그래서 그렇게 좋은 성적을 기대하진 않았다.

대회 준비

아침 겸 점심은 간단히 Quiznos에서 먹었다. 나는 음식이 비싸고 그렇게 맛있지도 않다는 이유로 Quiznos를 별로 좋아하지 않지만, 일요일 아침에 여는 곳이 별로 없는데다 동선 상의 이유로 어쩔 수 없이 Quiznos를 선택하게 되었다. 안녕원 친구도 밥을 먹는대서 같이 먹었다.

대회 시작

대회를 시작했다.

A번 제출 (13:15:55, 13:17:07)

문제를 읽자마자 든 생각은 ‘이거 완전히 랜덤으로 짜도 1/4 확률로 도는 거 아님?’ 이었고, 대회가 끝난 후 알게 된 바로는 실제로 그게 맞았다. 그러나 왠지 안 될 거 같다는 생각이 들어 적당히 많은 제약들에 대해 조건을 맞추는 수열을 반환하는 코드를 짰다. 처음에는 부호를 하나 잘못 써서 틀렸고, 그걸 고쳤는데 범위가 큰 서브태스크에서 TLE를 받았다. 이것이 파이썬이 느려서라고 생각했고 C++로 옮기기 시작했다.

A번 제출 (13:29:38)

그럭저럭 빠르게 C++로 번역 후 제출했으나, 여전히 동일한 서브태스크에서 TLE를 받았다. 스코어보드를 보는데, A번이 애당초 그리 쉬운 문제같지는 않아서 접근이 잘못되었다고 생각하고 B번 문제를 보기로 결정했다.

B번 풀이

간단히 식을 정리하니 피보나치 꼴의 무언가가 나왔다. 정수 해를 가지는 방정식을 풀어야 할 일이 생길 거 같아 확장 유클리드 알고리즘을 몇 달만에 구현해보기도 했는데, 결국 쓰지 않았다. 식을 정리하니까 범위가 좀 크게 나와서 피보나치를 빠르게 구하기 위해 행렬 거듭제곱도 짰는데, 위 두 개를 구현하는 게 너무 오래 걸려서 시간을 꽤 날렸다. 그럼에도 뭔가 유의미한 접근이 떠오르지 않았고, 그러다 뭔가 잘 해싱하는 건가? 라고 생각했다. 그러나 범위가 너무 커서 일반적인 해싱으로는 도저히 답을 낼 수 없을 거라고 판단한 후, A번 풀이가 생각나서 다시 A번으로 돌아갔다.

A번 AC (14:13:48)

사실 비둘기 집의 원리를 써야 할 거라는 생각은 지문만 읽어도 바로 할 수 있다. 문제는 그걸 어떻게 적용하느냐인데, 생각해보니 전체 수열에 대한 비둘기 집의 원리가 아니라 각 제약 조건 ($x < y < z < w$, $k$)에 대하여 $x$에 따라 비둘기 집의 원리를 적용할 수 있다는 관찰을 했다. 바로 구현하니 AC를 받았다.

B번 AC (14:47:37)

다른 문제를 볼까 하다가도 B번은 너무 수학 문제여서 이걸 내가 풀지 못하면 안 될 거 같다는 생각이 들어 계속 B를 잡기로 했다. 그러다가 $F_n$이 매우 커지면 답에 영향을 끼칠 수 없다는 사실을 관찰했고, 어떻게 잘 접근하니 닫힌 꼴의 식이 나왔다. $F_n$과 $F_{n+1}$이 서로소라는 성질까지 사용해야 했는데, B번 위치에 있기는 조금 어려운 문제 아닌가 하는 생각이 들었다. 근데 뒤쪽 문제를 보니 딱히 다른 데 놓기도 애매한 것 같기는 하다. 하여간 그렇게 적당히 작은 범위의 피보나치 수는 행렬 거듭제곱으로 구하고, 큰 범위의 수는 그냥 고려하지 않는 코드를 짜서 냈더니 바로 맞았다.

C번 풀이 (15:35:25 – 15:42:10)

D번이 조금 풀렸길래 D번을 볼까 하다가, C번을 읽어보니 좀 자명해보이는 조합론 문제여서 그냥 C를 잡기로 했다. 1번 정점과 2번 정점이 만족하는지 여부와 1번과 2번 모두에 연결된 정점에 따라 적절히 case work하는 풀이를 짰는데, 처음에는 모든 정점이 재료를 얻을 확률이 동일하다고 착각해서 잘못된 풀이를 짜다가 시간을 날렸다. 그 이후 다시 고쳐서 풀이를 제출했는데, 네 번이나 틀리게 되었다.

C번 AC (16:03:44)

조금 더 생각해 보니, 1번과 2번 정점에 모두 연결된 정점이 최대 한 개라는 잘못된 가정을 하고 있다는 걸 깨달았다. 저러한 정점이 여러 개 존재한다면 그 확률을 구하기 위해 다항식 곱셈이 필요했는데, 설마 FFT가 필요할 거라고는 생각하지 않았고 실제로 계산을 해봐도 필요하지 않았다. 그 와중에 디버그 출력을 지우지 않아 한 번 더 WA를 적립했고, 결과적으로 5번 틀린 후 AC를 받게 되었다.

D번 AC (16:51:37)

간단히 생각해보면 먼저 그리디하게 최대 몇 개의 병을 구울 수 있는지 구한다면, 그 범위 내의 병을 굽는 순서와 상관없이 모든 병을 굽기만 하면 올바른 방법이라는 걸 알 수 있다. 따라서 비슷한 방법을 다시 한 번 적용해주면 풀 수 있다. 거의 읽자마자 풀이가 나와서 금방 구현할 수 있을 거라고 생각했다.

그런데 python 유저라서 저런 그리디를 짜려면 세그먼트 트리가 필요했다. 나는 팀 노트가 두뇌 활동을 느리게 해 사람을 멍청하게 만든다고 주장하며 팀 노트를 가져가지 않았기에, 근 $n$달간 짜지 않았던 세그먼트 트리를 대회장에서 짜야만 하는 상황이 발생했다. 다행스럽게도 30분간의 고통스러운 디버깅 후 멀쩡히 작동하는 비재귀 세그먼트 트리를 구현하는 데 성공했다.

그런데 그냥 구현상의 실수를 nmk번 해서 4번의 WA를 받았다. 대부분 마이너한 실수였기에 고쳐서 AC를 받으니, 대회가 거의 1시간밖에 남지 않았다.

E번 풀이

문제를 읽자 마자 XOR Trie로 풀어야 하는 문제같이 보였다. 정말 큰 문제는, 나는 XOR Trie가 뭔지 모른다는 것이다! 몇 달 전 AtCoder가 끝난 후 Lulusphere가 나에게 설명해준 적 있었는데 그때 잘 들을 걸 하는 생각이 마구 들었다. 그래서 빠르게 포기하고 넘어가기로 했다.

F번 서브태스크 1, 2 — 30점 (17:39:54)

문제를 읽어 보니 무슨 이상한 수학적인 그래프 이론 문제 같았다. 대충 트리에서의 풀이와 $K = 1$일 때의 풀이를 생각해봤는데, 그걸 일반적인 그래프로 확장하기는 쉽지 않아 보였다. 다행히 서브태스크를 보니 $K = 1$일 때의 풀이를 묻는 서브태스크가 있어서, 그거라도 구현하기로 했다. 겸사겸사 완전 탐색으로 풀 수 있는 $N \le 10$인 서브태스크까지 풀어 점수 30점을 얻었다.

뒤쪽 문제 읽기

G번 문제는 막 $\sum$ 기호 위에 floor가 있고, $2^{30}$이 있고 심지어 인터랙티브여서 무서워서 건드리지도 않기로 했다. H번 문제는 너무 flow 응용처럼 생겨서 flow를 전부 잊어버린 나는 손댈 엄두도 내지 못했다. I번은 다들 42점을 긁었길래 E번의 서브태스크만 마저 긁고 돌아와서 풀기로 생각했다.

E번 서브태스크 1, 3 — 40점 (17:55:21)

서브태스크 1은 ${\cal O}(N^2)$를 짜면 풀리는 간단한 서브태스크였고, 서브태스크 3은 XOR Convolution을 나이브하게 ${\cal O}((2^{10})^2)$에 한 후 이분 탐색을 하면 되는 서브태스크였다. 그런데 구현 실수를 너무 많이 하여 10분 내로 풀려고 한 계획은 무너지고 5번의 시도 끝에 15분만에 제출했다. 점수가 2점 더 높은 I번을 먼저 잡을걸 하는 생각이 들었지만 어쩔 수 없이 시간이 모자라 I번의 서브태스크는 긁지 못했다.

대회 종료

대회가 종료된 후에는 열심히 문제에 대해 토론을 했다. A번이 랜덤이 된다는 놀라운 사실부터, E번은 정말 XOR Trie가 맞다는 등의 정보를 얻었다. 에디토리얼을 보다가는 G번 쯤에 졸았던 것 같다.

아래는 대회 종료 후 스코어보드이다. 470점으로 마무리했다. flake는 프리즈 전에도 나와 동일하게 400점이었는데, 프리즈가 끝나고 완전히 동일한 서브태스크를 긁어서 470점이 되었다.

I번 섭테를 긁지 못한 것 외에는 딱히 아쉬움은 없었던 것 같다. 무엇보다 최근에 PS/CP를 유기했던 건 사실이라 더욱 그랬다. AtCoder/Codeforces는 시간이 허락한다면 최대한 치려고 노력하고 있지만, 학기 중에는 도저히 시간이 나지 않아 매우 아쉽다. 특히 토요일 저녁에 도저히 시간이 나지 않아 AtCoder을 블루에 주차해놓은 후 한 번도 치지 못 하는 중인 것이 슬프다.

Codeforces grandmaster로 유명한 kolorvxl 친구는 뒤풀이 자리에서 Rated ARC를 치고 있었다. 나처럼 시간이 나지 않는다고 유기하는 게 아닌 저 정도의 노력을 갖추어야 레드에 가는 것이라는 걸 깨달았다. 정말 대단하다.