2026 KAIST Run Spring Contest 후기

2024 아챔 이후로 대회 후기를 첨 쓰는데요. 저번에는 잘 못 썼는데 이번에는 잘 적어보도록 하겠습니다.

이번 2026 KAIST Run Spring Contest에는 whyerano라는 닉네임으로 참가했습니다. (tmi. 제 롤 닉네임이기도 합니다.)

제 스스로 나름 만족스러운 결과를 이룬 것 같기도 하고, 군대 전역하기 전 마지막으로 나가는 오프라인 대회이기도 해서 후기를 작성해봅니다!

대회 전

10시 45분 정도에 대전역에서 dlguq0107랑 만나서 KAIST에 같이 갔습니다. 그리고 11시 정도에 starwh03과 songc 선생님이랑 KAIST 국가슈퍼컴퓨팅센터 근처에서 만나 같이 부대찌개 먹고 대회장에 갔습니다.

KAIST를 처음 가봤는데 캠퍼스가 좋다고 생각했습니다. 연대는 길쭉길쭉한 반면 KAIST는 동글동글하고 예쁜 호수도 있고. 거기서 귀여운 거위들도 봤습니다! ㅎㅎ 날씨만 좋았더면 캠퍼스 투어하기 딱 좋았을텐데 약간 아쉽다는 생각이 있긴 했습니다 ㅠㅠ (물론 바로 군대 복귀해야해서 투어할 시간도 없었을 것 같았지만요;;)

대회장에서는 아는 얼굴들이 좀 있었습니다. nflight11님 만나서 인사도 나눴고, SUAPC 때 처음 인사드렸던 kolorvxl님, SUAPC 때 인사드려야지 생각을 했는데 못하고 온라인상으로만 얘기를 했었던 trashmouse0524님, 간간이 ps대회 나갈 때마다 뵈었었던 gs22059님 (제가 군대 있을 때 그래도 SUAPC 덕분에 새로운 사람들도 많이 만나고 그랬네요 ㅎㅎ). 그리고 아챔 때부터 인연을 이어갔던 포스텍 leo020630님과 petamingks님. 그리고 UCPC 때 잠깐 인사했던 sedev57까지. 

참가자들 중에서 군인 분들도 꽤 계신 것 같았는데 군복을 입고 있는 사람은 저 밖에 없었어서 약간 뻘쭘했던 기억이 있습니다...

대회 중

A. Second Run (100점 - 09:04)

문제 보자마자 그냥 앞에서부터 차근차근 넣으면 된다는 풀이가 나왔습니다. 그대로 구현하니깐 맞았습니다! 

근데 그냥 random으로 넣고 이를 만족하는 의뢰인의 수가 [N/4] 이상일 때까지 반복하는 풀이가 존재한다는 것에 놀랐습니다. 그리고 후기 작성하면서 생각한 것이 "의뢰인들의 요구를 가장 많이 만족하도록 하는 배열을 만들어라." 라는 문제가 있다면 어떻게 풀 수 있을까요? 잘 모르겠네요. 

D. Grilled Bottle (100점 - 23:43)

A번을 풀고 스코어보드를 보니 D번이 풀려 있었습니다. 그래서 B번 말고 바로 D번을 봤습니다. 

이분 탐색을 생각하면 이후로는 그리디로 정렬 + 우선순위큐를 통해 1) 가능 여부 + 2) 최대 만족도를 구할 수 있습니다. 

C. Dubai Chewy Cookie (100점 - 54:36)

D번을 풀고서는 사실 B번을 먼저 봤습니다. B번은 a_n을 a_1과 a_2에 대해 수식도 다 세웠고, 인접한 피보나치의 수는 서로소라는 것도 알고 있었는데 마지막 수식을 못 세우고 "그래서 어떻게 풀지?"라는 생각과 함께 헤맸습니다. 결국에는 B번을 스킵하고 C번을 보기 시작했습니다.

N과 Q 제한이 작아서 각 쿼리가 주어질 때마다 O(N)에 해결하면 되겠다는 생각을 했습니다. 1번과 2번 정점을 연결하는 정점(들), 1번 정점만 연결하는 정점(들), 2번 정점만 연결하는 정점(들)로 분리해서 생각해보면 각 정점들 그룹마다 냅색으로 전처리를 하면 깔끔하게 풀리는 문제였습니다. 

물론 구현 과정에서 사소한 실수는 있었지만 (e.g. 1 - p_i + MOD라고 안 하고 MOD - p_i라고 한다던지 등등) 그래도 다행히 빠르게 수정해서 바로 맞을 수 있었습니다! 

B. RUN Sequence (100점 - 1:03:47)

다시 생각해보니 아주 간단한 식이 나왔습니다: result -= (u - fib[n-3]) * (r - fib[n-2]);

예제가 맞는 거 확인한 후 믿음을 가지고 제출해봤는데 맞았습니다! 

E. Kirameki of Revue (100점 (-1) - 1:20:18)

D번에서도 이분 탐색이 나왔어서 E번도 관찰이 빠르게 나왔습니다. 이분탐색 + Trie! 

이분탐색 범위를 0부터 2^31 - 1까지 해야하는 것을 처음에 10^9까지로 해서 55점을 맞고, 바로 바꿔서 100점을 맞았습니다!

E번까지 풀고서는 등수가 3등? 정도로 매우 높았었던 기억이 있네요.  

F. Pragmatism (30점 - 2:18:09)

이때부터 부분점수 긁기에 열중했던 것 같습니다. 문제를 봤을 때 bfs혹은 dfs로 트리를 만들어서 어떻게 잘하면 되지 않을까? 라는 생각을 먼저 했던 것 같은데... 어떠한 관찰도 보이지 않았고, 결국 부분점수 1, 2번을 긁어 30점을 얻었습니다. 

나중에 editorial을 봤는데 풀이가 너무 아름다웠습니다. 애드혹과 해구성하기를 (잘 못해서) 좋아하지 않는데도 이 문제는 너무 좋다고 생각합니다. ㄷㄷ 

I. Wizdomiot (42점 - 3:05:38)

F번 이후에 보니깐 I번 부분점수를 긁는게 보였고, 심지어 배점이 상당히 커서 I번을 먼저 봤습니다. 처음에는 금광세그로 해서 25점을 받았는데 생각해보니 더 간단하고 시간복잡도도 더 빠른 풀이가 보여서 42점을 받았습니다. 

G. AiScReam (58점 - 3:58:44)

이 문제를 보고서 CEOI 2023 Brought Down the Grading Server? 문제랑 매우 유사하다고 생각했습니다. (물론 어떤 알고리즘을 써야하는지만 알고 풀이는 몰랐습니다... 풀어볼 걸 그랬네요... ㅠㅠ 이것도 똑같이 분할정복 문제고, N이 2의 거듭제곱으로 주어진다는 점에서도 같은 문제입니다.) 

처음에는 모든 멤버들에 대해 a값이 같은 부분문제 2, 3을 풀어 24점을 얻었고, 이후에는 부분문제 1번까지 하여 30점을 얻었습니다. 

그리고 믿음을 가지고 랜덤을 이용하여 58점까지 얻는 데 성공하였습니다.

H. Hawaiki (2점 - 4:11:43)

처음 문제를 읽어보았을 때 이것은 평면 그래프다!! 이것은 기하다!! (제가 기하를 좋아합니다 ㅎㅎ;;) 하며 잘못된 희망을 품었습니다 ㅎ;; 아무리 생각을 해도 잘 모르겠어서... 부분문제 1만 긁었습니다...

대회 후

그렇게 632점으로 마무리했습니다. 프리즈 전에는 6등이었고, 이후에는 9등으로 마무리했습니다!  

그동안 나간 개인 대회들 중에서는 (연대 대회 제외하고서는) 가장 좋은 퍼포먼스를 낸 것 같아 기분이 좋은 것 같습니다! 제가 생각하는 제 강점은 나름 쉬운 (플래 하위까지의) 문제를 빨리 밀어내는 것인데 그대로 이번 대회에서도 잘 나타난 것 같습니다. 군대 있으면서 저점을 높이는 연습을 좀 많이 했는데 앞으로 icpc 준비하면서는 어려운 문제를 잘 풀 수 있는 연습을 해야겠다는 생각입니다. 

이번 대회에서 특별상이나 추첨상 중 하나는 얻고 싶었는데 아쉽네요 ㅠㅠ 마지막에 참가자 단체 사진을 찍었는데 저만 군복을 입고 있어서 약간 부끄러웠습니다 ㅋㅋㅋㅋㅋㅋㅋㅋ

마지막으로

후기 작성을 잘 했는지 모르겠네요... 그나마 찍은 위에 사진 한 장도 화질이 좋지 않아서 좀 아쉽다는 생각입니다 ㅠㅠ 

긴 글 읽어주셔서 감사합니다!