2026 KAIST RUN Spring Contest 후기

올해 런 대회가 열렸다. 무려 런 가을 대회 이후에 처음 치는 오프라인 대회였기 때문에 기대가 되었다.

백준이 서버 종료를 한 이후에 대회가 어떻게 진행될지 궁금했다. 런대회는 biko에서 했는데, ui가 정말 깔끔하고 좋았다. 바로 본대회 타임라인을 알아보자.

대회 타임라인

0:00 ~ 1:22

자리 근처에 멀티탭이 없었고, 내 노트북은 2시간이면 죽는 병약 노트북이기 때문에 대회가 시작하기 직전에 자리를 옮겨도 되냐고 물어봤다. 다행히도 멀티탭 옆에 있는 자리로 이동할 수 있었다. 

 

A번을 봤는데, 풀이가 안 떠올랐다. 생각보다 자명하지 않은데, 적당히 그리디하게 해주면 된다. ibm2006이 출제한 문제들이 보통 그러한데, 기존 ps 문제들과 결이 달라서 쉬우면서 재미있었다. 빠르게 AC를 받았다.

 

0:07 (A AC)

 

B번을 봤는데, 생각보다 수학이 까다로웠다. 노트에 정리를 하는데, D번에서 AC가 나왔다. 하지만 어차피 D~E번까지는 모두 풀 생각이어서 B번을 열심히 정리했다. 제출을 했더니 놀랍게도 한 번에 AC가 나왔고, 이게 퍼스트 솔브였다.

 

0:18 (B AC)

 

D번이 많이 풀리길래 문제를 보러 갔다. 간단한 스위핑 문제였다. 그런데 로그제곱에 set으로 떡칠했다가 tle가 날 것 같아서 구현에 조금 시간을 썼다. 그리고 제출을 했는데 60점이 나왔다. 왜인지 열심히 디버깅을 한 끝에, multiset의 iterator it에 대해 set.erase(it)를 해야 하는데 set.erase(*it)를 한 것이 문제였다. 한 글자 지우고 AC를 받았다.

 

0:40 (D AC)

 

10분을 * 하나 찾겠다고 시간을 낭비한 후에 C번을 봤다. 양 끝점이 1번과 2번으로 고정되는 쿼리 문제인데, 끝점이 고정되는 줄 모르고 생각하다가 FFT로 발전하는 풀이를 생각을 했고, 팀노트를 펴기까지 했다. FFT를 짜기 직전에 지문을 제대로 읽고 풀었다. 지문만 잘 읽으면 쉬운 문제이다.

 

0:56 (C AC)

 

E번을 봤는데 정말 xor segment tree 비빔밥 슥슥 해먹는 문제였다. 열심히 dynamic segment tree를 구현하고 (다행히) 한 번에 AC를 받았다.

 

1:22 (E AC)

 

1:22 ~ 2:46

이제 무슨 문제를 풀어야 할까? F번을 봤는데 재미있는 그래프 문제처럼 생겼다. 자명한 서브태스크가 30점 밖에 없으니, 실질적으로 이 문제를 풀면 70점을 얻는 셈이다. 이 문제를 풀어야 상위권에 들 수 있을 것 같아서 F번을 한참을 쳐다보았다.

dfs tree를 구성하고 부모/자식이 아닌 정점들을 잘 모아서 풀면 될 것이라고 생각했는데, 풀이가 나오지 않았다. 무한한 시간을 박으면 풀 수 있을 것 같았는데, 점점 F번에서 AC가 나오고 나는 아무것도 한 것이 없어서 G번으로 넘어갔다.

 

사실 G번은 joi spring camp 2019년에 있는 Naan의 인터랙티브 형태의 문제이다. 58점까지는 풀이가 똑같아서 금방 구현을 해서 긁으려고 했다. 그렇지만 문제의 설명이 조금 난해했고 내가 그레이더를 powershell로 실행하는데 실패해서 시간을 날려먹는다. 그러면서 스코어보드에서 다들 30, 60점씩 긁어서 좀 불안했다. 2시간 39분에 겨우 6점을 긁는데 성공한 이후에 58점까지 빠르게 긁었다.

 

2:46 (G 58)

 

2:46 ~ 5:00

많은 시간을 날렸다고 생각해서 빠르게 많은 점수를 주고 적은 생각을 요구하는 서브태스크들을 긁기 시작했다. 대략적인 스캔으로 F번의 30점과 I번의 서브태스크가 빠르게 점수를 받기에 좋아보였다.

우선 빠르게 F의 30점 서브태스크를 긁었다.

 

2:58 (F 30)

 

I번은 정말 서브태스크가 russian 식으로 주어졌다. 8점짜리 서브태스크가 N범위로 갈라져서 주어졌고, 적당히 빠른 코드를 작성하면 잘 뚫어서 점수를 많이 받을 수 있지 않을까 기대했다. 다들 42점을 긁었는데 N범위가 1000쯤 되길래, 그것보다 한 15점쯤 더 긁으면 좋을 것 같다고 생각했다. 처음에 짤 때부터 제곱 로그가 아닌 제곱 풀이를 만들었고, 구현을 잘 정리한 이후에 110줄을 구현했다. 사실 코드가 길어서 AC가 나오지 않으면 슬플 것 같았는데, 75점이 나와버렸다! 이때 좀 안도가 되었다.

 

3:45 (I 75)

 

H번을 긁을지 G번의 풀태스크를 볼지 고민을 했다. H번이 스코어보드에서 유의미하게 긁히지 않았고, F번 풀이 생각과 G번의 구현에 너무 많은 시간을 써서 정작 G번의 full task의 풀이에 대해서는 생각을 안했다. G번의 풀이를 조금 생각해보니까 분할정복을 잘 하면 풀린다는 것을 깨달았다. 이전에 58점을 받아봐서 그런지 구현이 어렵지 않았다. 운좋게도 빠르게 AC가 나왔다.

 

4:04 (G AC)

 

풀 수 없는 F와 I의 full task를 제외하면 할 것이 H번 긁기 밖에 없었다. 우선 2점을 긁으려고 했는데, 안 긁혔다. 그냥 코딩 미스인데, 지문을 열심히열심히 보고 아예 코드를 갈아엎었다. 정말 어이x

 

4:21 (H 2)

 

28점짜리 서브태스크는 적당히 간선 2개를 contract 해주는 것을 반복하면 된다. 하지만 이게 구현이 쉬워야 말이지... 역추적까지 해야 해서 쉽지 않앗다. linked list를 구현하는 감성으로 열심히 100줄 가량의 sweeping을 했더니 30점이 떴다.

 

4:42 (H 30)

 

남는 시간에 lr flow를 팀노트에서 베꼈다. 사실 lr flow가 뭔지 까먹어서 관뒀다. I번에 pragma나 박으면서 놀다가 대회가 끝났다.

 

결과

풀어야 할 문제들은 A B C D E F30 G58(?) H56 I75 정도 되는 것 같다. H 26이 그냥 flow를 흘리면 되는 문제였는데 못 풀어서 슬펐다. 시간이 부족해서 그랬던 것 같기도 하다. 자명하지는 않은 G full task를 풀기는 했지만, 대단히 대단한 문제를 풀지는 않은 것 같았고, 순위가 높을지는 잘 모르겠었다. 하지만 그렇다고 풀 문제를 못 푼 것은 아니기도 해서, 적당히 만족하고 있었다.

 

그런데 예상 외로 G 26점의 flow subtask를 아무도 안 긁었고, 나 밑으로 I 75를 긁은 사람이 없었다. 덕분에 무려 4등을 할 수 있었다. 내 위로는 다 초고슈여서 꽤나 만족스러웠다.

 

마무리

H번 풀이를 듣고 나니 flow cut duality 방향으로 왜 생각을 못했지?라는 생각이 들었다. 좀 반성을 해야겠다... F번은 못 푸는 문제가 맞았다. 새삼 F번을 푼 SongC가 대단해보였다.

 

그리고 나는 이번 대회에서 시간을 꽤나 많이 날려먹었음에도 불구하고 (F번에 1시간 박기, G번에서 구현 절기) 서브태스크들을 알차게 긁었다. 나의 구현 실력이 조금 나아진 것 같아서 좋았다.

 

런에 문제를 낼 사람이 많이 없어서 대회가 열리나 걱정했는데 5문제를 내면서 대회를 슈퍼세이브한 ibm2006이 고맙다.

 

이제 ps 대회들이 얼마 남지 않았다. 어려운 문제들에 많은 시간을 박아서 풀기에는 그 시간에 하고 싶은 것들이 더 많은 것 같다. 그리고 여기에서 ps를 더 잘해진다고 나에게 돌아오는 것이 대단히 많아지지 않는다. (world final 제외, 이때는 좀 열심히 해야 된다) 여유롭게 qoj에서 문제들을 풀다가 가끔 재미있는 대회가 열리면 참가하면서 놀아야겠다.