2026 Kaist Run Spring Contest 후기

 

지난 5월 3일 KAIST에서 진행된 2026 Kaist Run Spring Contest에 온사이트로 참가하였다. 백준이 없어져 기록을 남기기도 어려워졌기 때문에 이렇게라도 기록을 남긴다.

 

일단 서울에서 출발해야 했기 때문에, 오고가는 열차표를 예매했다. 서울역 -> 대전역 09:33 - 10:42 표와 서대전역 -> 용산역 20:39 - 21:54 표를 예매했다.

 

서울역 도착

서울역에는 꽤 빨리 도착해서 시간이 좀 남았다. 그래서 맛있게 호두과자도 하나 사먹고 출발했다. 맛은 약간 안에 들어있는 팥이 고체보다 액체에 가깝다고나 할까..? 굉장히 물러서 평소에 먹던 것과 느낌이 조금 달랐는데 이것도 나름대로 맛있었다.

 

가는 길에는 얼마 전 재미있게 본 영화인 <프로젝트 헤일메리>의 원작인 책을 조금 읽기도 하고, 리체스에서 래피드 경기도 한 판 뒀다. 대전에 내려서는 시간이 부족하지는 않은 것 같아 택시를 타지 않고 지하철을 탔다. 버스를 타는 것보다는 그냥 걷는 게 낫다고 판단해서 그냥 걸었다. 하지만 이내 비 오는 날 열심히 걷다 보니 왜 다들 대전역에서부터 택시를 타고 다니는지 깨달을 수 있었다.

내 걸음이 꽤 빠르기 때문에 총 걷는 데에는 30분 정도 걸렸다

 아무튼 대회장에 들어갔더니 내 자리는 맨 앞 줄이었다. 약간 당황했지만 뭐 자리가 중요한 건 아니다. 내향적인 성격이기도 하고 solved.ac 디스코드에서 본 사람들도 대부분 내가 얼굴은 전혀 모르기 때문에 대체로 조용히 앉아 있었다. 대회장에 일찍 도착한 것도 아니라서 지루하거나 그러진 않았다.

 

대회는 BIKO로 진행됐다. BOJ와는 다르지만, NYPC나 KOI 환경과 대체로 비슷했기 때문에 적응에 큰 어려움은 없었다. 하지만 가장 큰 충격이었던 것은 실시간 스코어보드를 유저 화면에서 볼 수 없다는 것이었다. 그래서 운영진 분들이 Zoom을 통해서 스코어보드를 공유해주셨다...! 새삼 백준이 참 좋은 플랫폼이라는 걸 느꼈다.

 

아무튼 대회가 시작되었다.

---

[0:00 - 0:12]  A. Second Run (AC, 100)

문제가 9문제이고 난이도순으로 정렬되어 있다는 정보가 있었기 때문에 당연히 A번부터 봤다. (지금 생각해보면 C나 D 정도 문제 먼저 잡고 퍼솔을 노리는 쪽이 좋았을 것 같기도 하다.)

 

보통 대회 첫 문제는 문제 지문을 읽자마자 어떻게 풀지 생각이 나서 바로 코드를 구현하러 가야 하는데, 생각이 나지 않았다. 약간 코드포스 div1 A번을 열었는데 어, 이게 뭐지? 하는 느낌이 들었다. M/4나 4개의 음표 같은 부분에서 4가 중복되는 게 비둘기집의 원리를 써야 할 것 같은 느낌이 들었는데, 이것저것 아이디어를 내봤지만 잘 안 됐다. 스코어보드에는 하나둘 첫 문제를 맞힌 사람들이 생겨서 분명히 간단한 풀이가 존재할 것이라는 믿음을 가졌지만 결국 결정론적인 풀이는 찾지 못했다.

 

생각해보니 랜덤으로 수열을 만들어도 기댓값이 $M/4$라는 생각이 들어 랜덤을 짜도 충분히 풀 수 있겠다는 생각이 들었다. 그래서 50번 랜덤으로 수열을 만들어서 성립하는지 검사하는 코드를 짰고, 처음에는 M = 0일 때 검사 코드가 잘못되어 있어서 1WA를 받았지만, 금방 틀린 부분을 찾고 12분만에 첫 AC를 받았다.

 

비록 BOJ가 서비스 종료했지만, solved.ac 기준으로 난이도를 매긴다면 G5를 줄 것 같다.

---

[0:12 - 0:40] B. RUN Sequence (AC, 200)

문제 지문 자체는 굉장히 간단하다. $a_1$과 $a_2$의 범위가 각각 $1 \le a_1 \le R$과 $1 \le a_2 \le U$로 제한되어 있고 피보나치 점화식을 만족하는 수열 {$a_n$}에 대해 $a_N$으로 가능한 값의 개수를 구하는 문제였다.

 

처음에는 $a_N$의 상한과 하한을 구하는 방향성으로 접근했고, 예제 2에서 상한과 하한 사이 모든 값이 가능하다는 점을 관찰해서, 이를 바탕으로 아이디어를 전개하고 있었는데, 생각해보니 $N$이 매우 커져도 가능한 수열의 개수가 $RU$를 넘지 않는다는 것을 깨닫고 다른 방향으로 접근을 시도했다.

 

$N$의 범위가 굉장히 커서 분할 정복을 이용한 거듭제곱을 활용하는 문제라고 생각해서 일단 피보나치 수를 구할 때 활용하는 행렬 [[1, 1], [1, 0]]을 가지고 열심히 식 정리를 했고, $a_N = f_{N-1} U + f_{N-2} R$이라는 식을 얻었다. 이때 인접한 피보나치 수는 항상 서로소이므로 서로 다른 $(R, U)$ 쌍에서 같은 $a_N$이 나오려면 $(R, U) = (a + k f_{N-1}, b - k f_{N-2})$와 같이 되어야 한다.

 

따라서 $N \le 50$만 되어도 항상 답은 $RU$이고, $N$이 이것보다 작을 때는 $RU$에서 중복되는 개수를 빼주면 된다. 따라서 정답은 꽤 간단한 꼴로 표현되고, $RU - \max(0, R-f_{N-1}) \times \max(0, U-f_{N-2})$이다. 처음에 max 함수가 들어간다는 것을 생각을 못해서 틀렸는데, 여기서 50점을 받았다. $R$ 값과 $U$ 값이 작은 데이터를 넣어봐도 max 함수를 넣지 않아서 틀리는 케이스들이 있었어서, 이건 서브태스크 데이터가 약했던 것 같다. 꽤 긴 시간이 소요되었지만, 스코어보드를 보니 B를 푼 사람이 그렇게 많지는 않아서 나만 어려운 건 아니구나 느꼈다.

 

solved.ac 기준 난이도는 P5를 기여할 것 같다. $a_N$ 식을 물론 작은 $N$에 대해 몇 개 구해보고 찍는 것도 쉽지만, 저 식을 얻는 과정뿐 아니라 중복되는 값을 세는 부분도 그렇게 쉽지는 않았다고 생각한다. 그래도 문제는 굉장히 좋았다.

---

[0:40 - 0:56] D. Grilled Bottle (AC, 300)

B를 풀고 나서 스코어보드를 보니 D가 C보다 훨씬 많이 풀려 있어서 C 대신 D로 넘어갔다. 아마 어떤 분이 13분만에 D 퍼솔을 드셔서 그랬던 것 다들 D로 가셨던 것 같긴 하지만, 그래도 D가 쉬울 거라고 생각해서 일단 넘어갔다.

 

문제를 읽고 나니 우큐 그리디의 느낌이 물씬 났다. 느낌 그대로 파라매트릭 서치를 통해서 구울 수 있는 병의 개수를 구하고, 개수가 정해지면 병들을 필요한 최소 화력이 큰 순서대로 정렬하고 사용 가능한 마법 중에서 만족도가 큰 것을 하나씩 배정하는 그리디로 풀 수 있었다. 이것도 $N$과 $M$을 착각해서 한 번 WA를 받았는데, RTE라 금방 오류를 찾을 수 있었다.

 

이러한 류의 우선순위 큐 그리디 문제들이 P5 정도에 배치되어 있는데, 여기에 파라매트릭 서치를 얹어야 하는 문제라 P4 정도 난이도인 것 같다.

---

[0:56 - 1:24] C. Dubai Chewy Cookie (AC, 400)

이 문제는 그래프에서 확률을 계산하는 쿼리가 있는 문제인데, 다행히 제일 처음 떠올린 dp의 시간복잡도가 $O(N^2 + NQ)$로 문제의 제한이 너무 잘 맞아떨어져서 어렵지 않게 풀 수 있었다. 모든 쿼리에서 1, 2번 가게에 대해서만 생각하므로 나머지 가게들은 1번과만 연결된 가게, 2번과만 연결된 가게, 그리고 둘 다와 연결된 가게로 나누고, 1 - 2 간선이 있는지 없는지에 따라서 나눠서 생각하면 어렵지 않게 풀 수 있다.

 

그리고 세 그룹으로 가게를 나눈 후 각 그룹에서 dp[i]를 $i$개 가게가 두쫀쿠를 만들 확률로 하여 냅색 dp를 돌리면 확률을 구할 수 있으므로 각 쿼리는 1번 가게와 2번 가게 각각에서 두쫀쿠 재료를 구했는지 여부와 1, 2번과 모두 연결된 가게에서 몇 개의 두쫀쿠를 만들었는지로 구분하면 최대 $4N$개 케이스로 구분되므로 $O(N)$에 각 쿼리를 처리할 수 있게 된다.

 

이 문제 역시 P5 정도 되는 것 같다.

---

[1:24 - 1:53] E. Kirameki of Revue (AC, 500)

4솔을 하고 나니 10위권 근처에 있어 꽤 괜찮은 성적이라는 생각을 하면서 5번을 봤다. 문제를 읽고 예제를 제대로 이해한 게 맞는지 확인하기 위해 $O(N^2)$ 나이브를 짜서 예제를 돌려보았다. 그래서 문제를 잘 이해했음을 확인했고, 그 김에 그냥 바로 제출해서 1:27 시점에 5점을 획득했다.

 

일반적으로 $K$번째 값을 구하는 문제는 $X$ 이하인 값의 개수를 세는 이분 탐색을 통해서 해결하는 경우가 많으므로 여기서도 비슷한 방식으로 생각했고, 최상위 비트부터 정하면서 fenwick tree에서 $k$번째 값을 찾는 쿼리처럼 비슷하게 진행하려고 했다. 그랬더니 주어진 수들로 Binary Trie를 구성하고, 여기서 적당히 값을 계산하면 전체 계산량이 Trie 전체 노드 수이므로 충분히 풀 수 있다는 판단이 들었다.

 

그런데 Binary Trie 구현을 팀노트에 가져오긴 했지만, trie가 내게 여전히 익숙하지 않은 자료구조라서 조금 더 쉽게 구현할 수 있는 방법을 고민했다. 어차피 이 문제에서는 Trie를 따라서 상하 노드로 움직일 필요가 없고, Level 단위로 순회하게 된다는 것에 착안해서 그냥 dict를 30개 만들어서 각 층에 대한 정보를 저장시켰다. 그랬더니 구현이 훨씬 깔끔해지고 코드도 짧아진 것 같다. 그래서 자랑 겸 코드도 한 번 올려본다. 처음에는 dict 대신 set만 있으면 되는 줄 알았어서 변수명이 setlst이다

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
arr = [*map(int, input().split())]
setlst = [dict() for _ in range(30)]
for i in range(n):
    v = arr[i]
    for j in range(29, -1, -1):
        if v in setlst[j]: setlst[j][v] += 1
        else: setlst[j][v] = 1
        v >>= 1
ans = 0
for j in range(30):
    ans <<= 1
    tmp1, tmp2 = 0, 0
    for key, val in setlst[j].items():
        if ans > 0 and key ^ ans in setlst[j]:
            tmp1 += val * setlst[j][key ^ ans]
        elif ans == 0:
            tmp2 += val * (val-1) // 2
    tmp = tmp1//2 + tmp2
    if tmp < k:
        ans += 1
        k -= tmp
print(ans)

 

 

난이도는 두 수 XOR 최댓값을 찾는 문제가 P3인데 이보다 분명히 상위호환 문제이므로 P2 정도라고 생각한다.

 

---

[1:53 - 2:56] F. Pragmatism (PAC, 510)

E번을 풀고 나면 F번을 푼 사람이 최소 너댓 명은 될 줄 알았는데, 아마 기억상 F번을 푼 사람이 1명뿐이었던 것 같다. 그래서 꽤 어려운 문제라는 생각을 했다. 하지만 내가 E를 dict를 사용하는 아이디어로 상당히 구현을 빨리 끝내서 그런 것일 수도 있겠다는 생각도 했다.

 

문제 자체는 마치 램지 수를 연상시키는 듯한 느낌이었다. $N, K$가 주어질 때 $N-2K+2$ 길이의 path를 찾거나, 둘 사이에 간선이 전혀 존재하지 않는 크기가 $K$인 정점 집합 2개를 찾아야 하고, 둘 중 하나 이상이 반드시 존재함은 보장된다고 문제에서 주어졌다. 마치 정점 수가 얼마 이상이면 m-clique이 존재하거나 n-independent set이 존재한다 뭐 이런 얘기를 하는 램지 이론과 비슷한 느낌이지 않을까 하고 램지 수의 상한 점화식 증명과 비슷한 방향으로 계속 생각했다. 하지만 잘 풀리지 않았고, 아 여기부터 다이아 이상의 문제들인가 하는 생각도 들면서 서브태스크를 긁는 쪽으로 방향을 틀어야겠다는 생각이 들었다.

 

그래서 일단 뒤쪽 문제를 읽으러 가기 전에 가장 쉬운 서브태스크인 $K = 1$만 후딱 구현해서 제출하고 10점을 챙긴 후 뒤 문제로 넘어갔다.

---

[2:56 - 3:23] H. Hawaiki (PAC, 540)

당연히 G번을 먼저 열어보았지만 G번 문제가 인터랙티브이고 수상할 정도로 복잡한 수식이 적혀 있는 것을 보고 H번으로 넘어왔다. 어차피 풀 태스크는 분명히 다이아 이상일 거라 서브태스크부터 봤다.

 

서브태스크 중 2번과 3번에 기울기 조건이 붙어 있었는데, 이 기울기 조건이 있으면 $u_i < u_j < v_i < v_j$인 $(i, j)$ 쌍이 없으므로 stack을 이용해서 예쁘게 처리할 수 있다. https://www.acmicpc.net/problem/33814 (비록 지금은 섭종으로 인해 볼 수 없지만)를 입부시험을 검수하면서 풀어본 적이 있는데, 이때 스택을 이용해서 활용했던 전략이 유효하게 먹혀서 28점을 얻을 수 있었다. 그리고 의도치 않았지만 서브태스크 1의 2점도 같이 획득해서 총 30점을 획득했다.

---

[3:23 - 3:32] I. Wizdomiot (PAC, 582)

스코어보드를 봤더니 마지막 문제에 42점이 굉장히 많길래 마지막 문제의 서브태스크를 긁으러 마지막 문제로 이동했다. 42점을 계산해보니 $N \le 2^{10}$ 서브태스크까지 해결해야 했는데, 가장 직관적으로 떠오르는 풀이는 $O(N^3)$이었다. 아무리 4초긴 해도 파이썬이라 $N \le 1024$에서 $O(N^3)$을 4초 안에 돌릴 수 있을지 걱정이 조금 들었는데, 코드를 짜고 제출해보니 42점이 받아졌다. 그래서 재빠르게 9분만에 42점을 긁고 다른 문제로 이동했다.

---

[3:32 - 3:47] F. Pragmatism (PAC, 602)

스코어보드에서 F 30점이 많길래 F 30점 코드를 구현하러 갔다. 30점을 받기 위해서는 $N \le 10$ 서브태스크를 해결해야 하는데, $N$이 매우 작으므로 그냥 열심히 빛의 신전으로 가능한 모든 조합과 대립의 신전으로 가능한 모든 조합을 구하면 해결할 수 있으므로 구현 자체에 시간이 엄청 오래 걸리진 않았다. 아까부터 계속 고민하던 아이디어가 있기도 했고 남은 문제 중 가장 앞쪽에 배치되어 있으니 난이도가 그나마 제일 낮을 거라는 기대가 있었지만 서브태스크 3조차 가능성이 없어 보여서 그냥 이 문제를 버리기로 했다.

---

[3:47 - 4:20] H. Hawaiki (PAC, 602)

H에서 최대 유량을 잘 활용하면 $N \le 300$을 풀 수 있을 것 같아서 이것을 풀려고 갔다. 최대 유량은 최소 컷의 값을 구하는 게 핵심이지만, 이 문제에서는 최대 컷 위치를 찾고 그 값에 맞추어서 나머지 위치에 항해사 수를 배정해야 하므로 이걸 음수로 돌려서 생각하려고 했다. 그러기 위해서는 모든 경로에 엄청나게 많은 수의 항해사를 배치해놓고 (배치된 항해사 수) - (요구하는 항해사 수)를 capacity로 잡고 최대 유량을 돌린 후, 구해진 유량 값만큼 배치된 항해사 수를 다시 줄이는 방향으로 풀려고 시도했다.

 

하지만 무엇이 문제인지 모르는 채로 계속 서브태스크 4가 풀리지 않아서 결국 아직 손을 대지 못했던 G번을 보기로 했다. 올라온 해설을 보니 내 접근 방향이 올바른 방향이었는데, 왜 틀렸는지는 아직도 전혀 미지수이다.

---

[4:20 - 4:45] G. AiScReam (PAC, 632)

문제를 보고 서브태스크를 읽으니 일단 $k \le 5$ 서브태스크까지 풀 수 있으면 아주 좋을 것 같아서 $k \le 5$인 경우에 대한 풀이를 떠올려봤는데 전혀 감이 오지 않았다.

 

그래서 그냥 깔끔하게 포기하고 위쪽 서브태스크 3개만 맞자는 심정으로 코드를 구현했다. 서브태스크 2와 3은 사람에 따른 아이스크림 맛의 선호도 차이가 없으므로 그냥 1 2 3 ... N 순서대로 배치해도 된다. 따라서 필요한 분할 위치만 1번 쿼리로 찾아주는 코드를 짜서 4:42 시점에 24점을 획득했다. 처음에 $2^30$과 $2^40$ 등 각종 지수를 잘못 봐서 스케일링이 잘못되어 계속 1번째 테스트케이스에서 틀리는 참사가 있었는데, 다행히 고쳤다.

 

그리고 $k = 1$인 경우는 1, 2 순서와 2, 1 순서만 고려하면 되므로 어렵지 않게 짤 수 있었다. 그래서 4:45 시점에 30점을 획득했다.

---

[4:45 - 5:00] I. Wizdomiot

원래는 더 이상 점수를 획득할 수 있는 시간이 안 될 것 같아 내 제출 기록을 보면서 제출 시각을 기록하고 간식을 먹으면서 쉬고 있었는데, 스코어보드에 I 50점을 받으신 분들이 몇 분 보이길래 $O(N^3)$을 잘 깎으면 $N \le 2048$까지 풀 수 있나 싶어서 C++로 코드를 변환해서 제출해보려고 했다. 최대한 빠른 속도로 Python 코드를 C++로 변환하고 마지막 2초인가를 남기고 코드를 제출했는데 아쉽게 C++ 코드가 컴파일이 안 되어서 점수를 얻지는 못하였다.

 

이렇게 대회가 마무리가 되었고, 최종 결과는 632점으로 전체 10등이었다. 지난 Semi-Game Cup보다 인원수도 많고, 그 당시 14등이고 P1이었던 E번을 못 풀어서 플래 올솔을 달성하지 못해 약간 아쉬움이 남았었는데, 이번에는 플래티넘 문제까지 모두 풀어냈고 서브태스크도 알차게 긁으면서 꽤 높은 점수를 받은 것 같아 만족스러웠다.

 

물론 순위상도 받지 못했고, 특별상도 받지 못했지만 레드만 10명 가까이 참가한 것으로 알고 있는데 그 사이에서 10등을 차지했고, 나보다 코드포스 레이팅이 높은데 이번에 나보다 못 보신 분들도 보여서 나름대로 잘 친 대회라고 생각한다. 그리고 모든 문제에서 꽤 서브태스크를 긁어서 점수를 벌었기 때문에 이 점도 뿌듯하다.

 

대회가 모두 끝나고 나서 풀이 세션과 시상 세션이 진행되었다. 백준에서 진행된 것이 아니라서 스코어보드를 아래에서부터 한 명씩 공개하면서 위로 올라가는 방식으로 스코어보드 공개를 할 수 없었다. 그래서 그냥 스크롤을 이용해서 수동으로 스코어보드 공개를 했다.

 

 풀이 세션에서 운영진 분들이 문제에 대해 열성적으로 해설하시느라 시간이 꽤 많이 지체되었는데, 시상 때에 가중치 랜덤 상과 랜덤 특별상을 추첨하려고 하는데 스크린 미러링?이 잘 안 되어서 운영진들이 결국 이걸 Zoom 화면 공유를 이용해서 해결한 것으로 보인다. 이 과정에서 예상 종료 시각이었던 7시보다 30분 넘게 늦어져서 하마터면 열차 시각 때문에 저녁을 못 먹을 뻔했다...ㅋㅋ (다행히 카이스트를 다니는 친구의 도움으로 다 식은 치킨을 먹을 수 있었다)

혹시 내가 나중에 오프라인 대회를 운영할 일이 있다면 계획표를 조금 여유 있게 짜놓는 게 좋을 것 같다.

 

이번 대회 성적이 꽤 만족스러웠는데, 다음 주에 있을 KOI 1차와 다다음 주에 있을 SCSC에서도 좋은 성적 거둘 수 있었으면 좋겠다.