카이스트 알고리즘 문제해결 동아리 RUN에서 주최한 봄 대회인 2026 KAIST RUN Spring Contest에 참가했다.
참가 신청
사실 런 대회가 문제 셋의 퀄리티로 유명한 대회이다 보니, 좋은 문제를 풀어보고자 하는 마음이 컸다. 오프라인 PS 대회가 잘 없다 보니 솔브드 디코에서만 보던 사람들이랑 같이 한 자리에 모여 문제 풀고 밥 먹고... 그러고 싶기도 했고.
그리고 지난 겨울방학 때 몰입캠프 하면서 카이스트에서 한 달 동안 살았었는데, 그때 만난 사람들이랑 겸사겸사 점심도 먹고 싶었어서 대회 공지가 뜨자마자 바로 신청했었다.
작년에도 런 대회에 외부 참가자를 받았었지만, 봄 대회 땐 해외여행과 겹쳤고, 가을 대회 땐 대회 2일 후에 컴파일러 중간고사가 있었다. 작년 가을엔 시험에 집중하는 게 맞다고 생각해 대전에 가지 않았었다가 시험을 시원하게 말아먹고 "그냥 대전 내려갔다 올걸..." 하는 후회를 했었고, 올해는 그 후회를 뒤풀이하지 않고자 다음날 아침 10시에 그래픽스 시험 있는데 그냥 내려갔다 오기로 결정했다.
스코어보드에 표시될 이름은 "내일아침10시중간고사"로 정했다. 백준이 섭종해서 BIKO에서 대회를 진행했다보니 CMS Scoreboard를 썼는데, 그걸 미리 알았으면 닉네임을 더 길게 적을 걸 그랬다.
대회 시작 이전
대회 전날에 일찍 일어나기 위해 평소보다 일찍 오전 1시에 침대에 누웠는데, 일찍 자려니까 잠이 안 왔다. 뒤척이다가, 폰 보다가 새벽 3시 넘어서 잠이 들었다. 그래서 4시간을 자고 출발하는 대참사가 발생했다...
기숙사 뒤 프린트카페에서 작년 UCPC 때 만들었던 팀노트를 뽑아, 수서역으로 출발했다.
수서역에서 SRT를 타고 내려와선 택시를 타고 어은동으로 이동했고, 몰입캠프 때 만난 친구랑 같이 회덮밥을 먹었다. 아소부라는 식당이었는데, 대전에 한달동안 있으면서 안 가본 맛있는 식당을 새로 알게 되어 좋았다.
같이 밥 먹고 대회장이 있는 N1 방향으로 걸어가면서 중앙기계실 뒤에 있는 샛길의 존재를 전수받아 그쪽을 통해 갔는데, 샛길을 나오니 눈 앞에 N1이 보였다. 지도에도 없는 길이던데 신기했다...
12시쯤 등록을 마치고, 바로 자리로 가서 노트북 충전기를 꽂았다. 노트북이 만 나이로 5살을 먹은 게이밍 노트북이라서 충전기 없이는 1시간도 버틸 수 없어서 걱정을 했는데, 다행히 대회장 멀티탭 길이와 딱 맞게 충전기를 꽃을 수 있었다.
등록 이후엔 기숙사에서 들고 온 아루 쵸코푸니, 오는 길에 샀던 넙죽이 키링을 세팅하고, N1 안에 있는 탐앤탐스 가서 (상시 50% 할인되는) 아메리카노를 사 오고, 이번 대회 온 한양대 알로하 사람들이랑 이야기하며 시간을 보냈었다. 스낵바에서 과자 하나 집어먹기도 했고.
백준이 갑작스레 섭종을 하면서 대회를 BIKO에서 진행을 했는데, 참가자 시점 대회 UI가 깔끔했던 게 기억난다.
대회 타임라인
대회 문제는 https://oj.uz/problems/source/kaist2026runspring?locale=ko 에서 볼 수 있다.
0:00 ~ 1:32
A번을 관찰해본 결과 x, y, z, w를 모두 합쳐서 4M개가 입력으로 들어오고, 문제에서 구하는 것에 floor(M / 4)가 있는 것을 보고 "이거 비둘기집 원리 쓰면 증명되겠다" 생각을 했다. 근데 증명은 전혀 쉽지 않았고 막힐 때마다 B번을 중간중간 접근해가면서 A번을 접근했다. 한 40분쯤 지났을 때쯤엔 A번 문제 AC가 많이 나오는 걸 보고 그냥 무지성 그리디하게 접근해도 될 거 같단 생각이 들어서, w_i 값이 같은 것끼리 묶어두고 1부터 N까지 순차적으로 봐 주며 제일 많은 의뢰인들을 만족시킬 수 있게 A_{w_i}를 고르는 풀이를 구성했다. 풀이를 완성하고 예제 통과하는 거 보고 제출했는데 WA가 나왔고, 20분 가까이 디버깅을 하다가 상당히 기초적인 실수를 한 걸 확인했다.
for(int j=0; j < 4; j++){
if(req[j] > mxval){
mxval = req[i]; // 왜 j가 아니라 i가...
mxidx = j;
}
}
"내가 요새 PS를 안 하긴 했구나..." 하는 생각을 하며 수정을 했고, AC를 받았다.
(0:54 A - WA)
(1:11 A - 100/100)
A번에서 막히고 B번을 처음 읽고 나서 든 생각은 "A번 말고 B번을 먼저 봤었어야 했다" 였다. 백준에서 피보나치 수열 관련해서 여러 문제를 풀었다 보니, $a_n = a_{1} F_{n-2} + a_{2} F_{n-1}$, $\gcd(F_{n-2}, F_{n-1})=1$인 건 이미 잘 알고 있었다.
근데 하나의 a_n에 대해 여러 경우가 겹치는 걸 어떻게 해결해야 할지 감을 못 잡고 있다가, 예전에 동아리 디코에서 그림까지 그려가면서 왜 틀리는지 물어봤던 문제가 하나 떠올랐다. 그때 기억에서 착안해서 값이 이동하는 걸 좌표평면에 표시를 해 보았더니, 신기한 결과를 얻을 수 있었다.
답이 상당히 깔끔한 closed form으로 나온다는 걸 그림을 통해 파악할 수 있었고, 바로 구현에 들어가 AC를 받았다.
(1:32 B - 100/100)
1:32 ~ 4:14
B번을 풀고 나선 C번을 읽기 시작했다. 문제 조건을 보고 이게 가능한건가 싶었지만, 체인점 번호가 1번이랑 2번만 중요하단 걸 파악하고 나니, 기댓값의 선형성을 이용해야 하는 제곱DP라는 건 바로 확인하고 문제 풀이를 구상하기 시작했다. 처음에는 1번이랑 2번이 서로 연결되어 있는지 아닌지에 따라 풀이가 달라진다 생각을 했고, 1번/2번 체인점에 재료가 들어올/들어오지 않는 경우인 4개의 경우에 맞추어 4개의 DP 테이블을 초기화하는 4개의 함수를 만들었다. 근데 비슷한 일을 하는 함수가 4개씩이나 있으니 디버깅이 쉬울 리 없었고... 그렇게 구현&디버깅을 하다 보니 대회 남은 시간이 1시간 반 정도만 남게 되었었다.
그런데 1번 체인점과 연결됨 / 2번 체인점과 연결됨 / 두 체인점 모두와 연결됨 3가지 경우로 나누는 게 맞다는 걸 2번 예제를 디버깅해보다가 깨달아버리고, 코드를 전부 지우고 처음부터 코드를 20분에 걸쳐 다시 짜고 나니, 예제를 멀쩡히 통과했다.
A번 풀었을 때와 마찬가지로, "내가 요새 PS를 안 하긴 했구나" 하는 생각을 또 했다.
(4:14 C - 100/100)
4:14 ~
C번 푸는 사이 중간중간 D번을 슬쩍 봤는데, 섭테 1번도 어떻게 풀지 감이 안 잡혀서 E번으로 넘어가기로 결정했다.
지문을 보고 든 첫 인상은 "이거 99.99% 확률로 gubshig이 낸 문제구나" 였고, 생각보다 60점까지 긁는 게 상당히 쉬울 것 같단 확신을 했다.
섭태 1번은 N <= 2000인데, 그냥 O(N^2)으로 모든 경우를 다 봐주면 되니, 반복문을 짜서 제출했다. (4:24 E - 5/100)
섭태 2번은 K=1인데, XOR 연산의 결과가 가장 작은 것만 찾으면 된다. XOR Trie를 통해 최대 XOR을 구하는 원리를 생각해보면 A에서 인접한 두 수를 비교하면 된다. (4:32 E - 25/100)
섭테 3번은 A_i <= 1024이니 나올 수 있는 값이 1025가지 뿐이다. Counting Sort의 원리를 생각하면 쉽게 풀 수 있다. (4:38 E - 60/100)
서브태스크를 모두 긁으니 20분이 남았고, (수상권과는 거리가 멀었기에) 남은 시간 동안 다른 서브태스크를 긁으려 노력하기보단 E번 풀태스크 풀이를 고민했었다. 아마 Trie 위에서 각 depth마다 비트가 같은지 다른지 체크하면서 내려가는 분할 정복 풀이였을 거 같다는 생각을 하다가, 360점으로 대회를 마무리했다.
시상식 + 스코어보드 공개
25 UCPC 본선 이후 처음 경험한 5시간 대회를 마치고 나서, 여러 사람들을 만났다.
E번을 출제(했을 것이라 확신)한 gubshig에게 "트라이 쓰는 거 맞냐"고 묻기도 했고, 신촌연합 관련해서 한번 만났었던 gs22059도 다시 만나고, 중학교 때 같이 영재고 준비했다가 이후 연락이 끊겼었던 친구도 보고, 많은 사람들을 만났다.
문제 에디토리얼 발표를 보며 느낀 점도 많았는데, ibm2006님이 5문제를 출제한 걸 보고 많이 놀랐고, A번은 랜덤 풀이가 가능했으며, E번은 (예상대로) gubshig이 출제한 게 맞았고, gmroh06이 낸 H번의 풀이의 길이와 깊이와 그림판으로 그린 듯한 그림을 보고 감탄했었다. 추가로 F번을 전혀 읽지 않아서 문제가 뭔지 몰랐는데, 풀이 설명이 끝나자 박수가 쏟아지는 걸 보고 좋은 문젠가보다 싶었다. 나중에 한번 풀어봐야지
안타깝게도 특별상을 타지는 못했고 스코어보드 공개 시간이 되었다. CMS Scoreboard는 어워드 모드가 없어서 스코어보드를 한 칸 한 칸 스크롤해가며 올라가는 전통?적인 기법을 사용했고, 이상한 팀명을 읽으며 사회자님이 고통받는 일은 이번에도 있었다.
내 슼보 상 이름인 "내일아침10시중간고사"를 보고서는 "내일 중간고사 잘 보시길 바랍니다"라는 덕담을 해 주셨음 ㅎ
전체 참가자 83명 중 53등을 했다.
전국의 고수들이 모이는 대회에서 상위 70% 안에 들었다는 점에서 만족스럽긴 하면서도, 코드포스 퍼플 찍으려면 D번이랑 E번도 대회 중에 풀었어야 할 거 같다는 생각이 들어 씁쓸했다. 퍼플 갈 수 있겠지?
뒤풀이 + 후기
뒤풀이 장소로는 예전에 몰입캠프 때 갔던 적 있는 어은동 훌랄라치킨을 갔다. 예전에 한양대에서 뵌 적 있는 leo020630님 옆자리에 앉았었는데, man_of_learning님의 취업 준비 이야기를 들을 수 있던 좋은 시간이었다. 옆 테이블에 앉아 있던 kolorvxl님은 실시간으로 ARC를 rated로 치고 계시더라... 코포 레드는 나와 보법부터 다르단 걸 느낌
이후에는 nflight11, ai4youej님을 따라 싸이뮤직에 갔다.(두 분 더 있었는데 까먹음)
프렌드 모드로 같이 사볼 몇 판 했었는데 3~4코인 쯤 하고 나니 손톱이 깨지는 사고가 나면서, 츄니즘을 처음으로 해 봤다. 게키츄마이 노래들이 디맥이나 아르케아에 수록이 많이 되어 있어서 아는 노래가 생각보다 많았고, 아는 노래 몇 곡 해봤는데 생각보다 재미있었다. 아마 기회가 되면 계속 할 거 같은데, 요즘 오락실 갈 시간이 잘 안 나서 슬프다...
대전에서 서울 올라가는 SRT 막차를 타고 1시 20분쯤 수서역으로 왔고, 택시비 절감을 위해 버스 타고 기숙사로 가느라 새벽 3시에 학교에 도착했다. 그리고 나선 밤을 새고 시험을 보러 갔는데, 너무 졸려서 검토도 안하고 제출했다 보니 잘 봤는지는 모르겠다.
별 일이 없으면 아마 오프라인 PS 대회 참가는 올해가 마지막일 거 같아서, 최대한 많은 대회에 가 보고 싶다. 교내 대회는 내가 동아리 회장이라 참가 못 하고, UCPC ICPC SCPC LGCPC 본선에 가보고 싶은데 잘 될지는 모르겠다. 그래도 마지막 해인데 서울리저널 본선은 가 봐야 하지 않을까? 16일에 있을 서울대 SCSC에서 여는 대회도 갈 생각이 있었는데, 소마와 학교생활을 병행하고 있는지라 가지 못해 아쉽다.