2026 숭고한 연합 알고리즘 경진대회 우승 후기

이번에 결성된 카이스트 icpc팀 kokiri is cute의 첫 오프라인 대회이다. 팀 구성은 다음과 같다.

• 장근영(azberjibiou): 애드혹을 잘 푼다. 저점이 높은 편이다.
• 이온조(Onjo): 국밥 문제들을 잘 푼다.
• 오태인(octane): 기하 고슈이다. 구현을 잘한다.

요즘 팀연습도 열심히 돌고 있고 (여기 참고) 폼도 나쁘지 않은 것 같아서 이번 대회는 1등(!)을 목표로 하고 갔다.

 

대회 초반

대회가 시작하고 온조가 ABCD, 내가 EFGH, 태인이가 IJKL을 봤다. 나는 F번을 보고 쉽다고 주장했고, 온조는 B번이 쉽다고 주장했다. 같이 풀이를 짜고 사이좋게 WA를 받았다.

 

0:13 (B WA), 0:15 (F WA)

 

F번의 지문을 잘못 읽었다는 것을 깨달았다. S K H를 순서대로 잇는 경로의 개수를 세는 문제인데, 순서와 상관없이 배치되어도 되는 줄 알았다. 제대로 읽고 새로운 풀이를 내서 제출을 했는데 또 WA가 나왔다. 온조는 B번을 고쳐서 맞았다. 태인이는 I번이 쉽다고 주장하고 짰는데 WA를 받았다.

 

0:19 (B AC), 0:21 (F WA), 0:24 (I WA)

 

F번의 지문을 다시 잘못 읽었다는 것을 깨달았다. 만든 수열에서 S, K, H의 개수가 모두 같아야 한다는 것을 안 읽었다! 한숨을 푹푹 쉬면서 문제를 다시 풀었다. 다행히 이번에는 AC를 받았다. 그 사이에 온조는 내가 읽자마자 쉽다고 하고 던진 H번을 맞아서 왔다. 태인이의 I번은 그냥 문제를 잘못 읽은 것으로 판명났다.

 

0:35 (H AC), 0:40 (F AC)

대회 초반을 시원하게 말아먹으니까 정신이 바짝 들었다!!! 이때 순간 저점이 12등이었다. 페널티 관리를 말아먹어서 속이 바짝바짝 타들어갔다.

대회 중반

스코어보드를 보니 인터랙티브 문제여서 유기했던 E번이 28분에 풀렸다. 관상학적으로 플래티넘 상위권 문제여서 놀랐다. 천천히 생각해보니 예전에 풀었던 문제랑 비슷하게 풀면 되어서 바로 풀이같이 생긴 무언가를 만들고 20분만에 구현을 했다. 굉장히 구현을 급하고 더럽게 해서 맞을지 의문이었지만, 한 번에 맞았다! 동시에 태인이가 L번이 쉽다고 주장하고 짰는데 WA를 받았다.

 

1:00 (E AC), 1:09 (L WA)

 

이후 온조가 키보드를 잡고 D번의 구현을 이어나갔다. 스코어보드에서 L번이 주르륵 풀리길래, 태인이에게 "이게 어렵나"라고 드립을 친 후 문제를 읽었다. 근데 오랜 시간을 생각했는데도 안 풀려서 당황했다. D번의 구현을 마치고 올 미래의 온조에게 L번을 유기하고 C번을 봤다. C번은 놀랍게도 이 문제에 이 문제를 섞으면 비빔밥처럼 풀 수 있다. 내가 2번째 문제의 풀이를 까먹어서 (...) 조금 당황을 했었는데, 2번째 문제보다 C번의 제한이 훨씬 널널해서 그냥 쉽게 풀 수 있었다. D번의 구현을 기다리는 사이에 태인이가 np-hard를 특수한 class에서 푸는 문제라고 주장한 J번을 읽었다. 지문을 읽어봤는데 그냥 하면 되는 쉬운 기하 문제라서 태인이에게 풀이를 설명줬다. 알고보니 태인이가 지문에서 경로가 증가해야 된다는 부분을 안 읽은 것이었다. 기하 구현은 귀찮으니까 (그리고 태인이는 기하 고슈니까) 태인이에게 구현을 유기했다. J번의 토론을 하는 사이에 온조가 D번을 맞아왔고, 빠르게 C번을 구현을 해서 AC를 받았다.

 

1:31 (D WA), 1:40 (D AC), 1:50 (C AC)

 

중간 난이도 문제들을 빠르게 풀어내서 그래도 어느 정도 순위를 회복했다. 한 가지 문제가 있는데, 태인이와 내가 유기한 L번을 온조도 풀지 못했다는 것이다. 스코어보드 상으로 모두가 푸는 문제를 3명 모두 봤는데 풀지 못했다는 것이 초비상이었다.

비상!

 

L번을 풀어내겠다고 선언을 한 후 오랜 시간 L을 잡았다. 오랜 시간 끝에 스코어보드에 풀린 양에 비해 어려운 풀이가 나왔다. 우선 짜서 맞았는데 다들 어떻게 푼건지 의아했다. 알고 보니 다들 잘 찍어서 맞췄다고 한다... L번을 푸는 사이에 태인이는 J번을 풀었다.

 

2:31 (L AC), 2:38 (J AC)

잠깐 1등을 했다. 이후 페널티에 밀려서 순위가 떨어졌다.

대회 후반

이쯤에서 남은 문제가 A G I K이다. 각각의 인상은 다음과 같았다.

• A번: 풀이는 아주 쉽지만 구현이 매우 귀찮은 문자열 문제
• G번: 이상한 lp-dual 문제
• I번: 자료구조 비빔밥
• K번: 지문이 길고 뭔소리인지 모르겠어서 안 읽음

내가 L번에서 고통받고 태인이가 J번에서 고통받고 있었을 때 온조가 I번을 풀었다. 2차원 좌표평면 위에서 스위핑을 하는데 dnc opt + dnc를 박는 자료구조 고봉밥 풀이였다. 풀이가 매우 무거워서 구현을 빨리 끝낼 수 있을지 의문이었다.

나는 A번 문제가 문자열 문제이지만, 풀이가 쉬우니 많은 상위권 팀들이 풀거라고 판단을 했다. A번의 구현이 자신이 없어 온조가 먼저 I번을 짜고, 그 시간 동안 A번의 구현을 구체화하는 방향으로 진행했다.

온조는 금방 I번의 구현을 마쳤다! 제출을 했지만 아쉽게도 WA를 받았다.

 

3:23 (I WA)

 

온조가 I번을 짜는 사이에 A번의 구현 구체화가 끝났다. 키보드를 잡고 구현을 했다. 6000B 가량의 길고 더러운 구현 끝에 예제가 나왔지만, 예제가 약함 + 코드가 더러움 이슈로 맞을지 의문이었다. 게다가 강한 데이터를 만들기도 쉽지 않아서 스트레스를 짜기도 어려워보였다. 다행히 한 번에 AC가 나왔다!

 

4:18 (A AC)

 

나와 온조가 각각 A/I번을 푸는 동안 태인이는 G/K번에서 고통을 받고 있었다. 도중에 4문제만 푼 팀이 K번을 풀었다는 것을 관측하고 태인이는 K번을 풀기 시작했다. 처음에는 "li chao tree를 사용하면 되지만 나는 구현할 수 없다"를 외치다가, "사실 cht만 짜면 된지만 나는 구현할 수 없다"로 바뀌었고, 마지막에는 "팀노트의 line container를 사용하면 구현할 수 있다"로 바뀌었다. 태인이가 K번을 구현하고 AC를 받았다!

 

4:33 (K AC)

 

태인이가 K번을 구현하는 사이 나는 온조의 터진 I번 풀이에 대해 논의하고 있었다. 도중에 굉장히 자명한 관찰을 놓쳤다는 것을 깨달았고, 이것을 사용하면 굉장히 쉬운 루트로그 풀이를 낼 수 있다는 것을 깨달았다. 태인이가 자리에서 나오자마자 온조의 풀이를 모두 갈아엎고 구현을 시작했는데. 빠른 구현 후에 제출을 했는데, 아쉽게도 TLE가 났다!!

 

4:41 (I TLE)

 

N 범위 10만에 시간제한 3초라면 루트로그가 정해일 것이라고 생각하면서 별의별 최적화를 다 했다. pragma도 박아보고, 데이터가 약할 때 효과적일 수 있는 최적화도 해보고 심지어 set을 segment tree로 바꾸려는 노력도 했다! (결과적으로 세그먼트 트리 위에서 이분탐색을 못해서 실패했다) 나의 노력에도 불구하고 TLE는 AC로 바뀌지 않았다.

 

(I TLE * 3)

 

대회 이후

I번 정해의 시간복잡도가 루트로그가 아니었다고 한다. 알고 보니 로그를 떼는 것은 정말 쉬웠다. 시간만 조금 더 많았으면 풀 수 있었을 것 같아서 아쉬웠다. 스코어보드에서 아무도 시도조차 하지 않은 G번도 사실 쉬운 문제였다. 서울대 팀이 왔으면 올솔을 하고 딩가딩가 놀았을 것 같다. 후반에 A를 1번에 맞고, K번도 아슬아슬하게 맞았음에도 아쉬움이 남았다.

스코어보드

 

Reboot Ssal Game이랑 페널티 10분 차이로 간발의 차이로 1등을 했다!

 

A번과 I번이 많은 팀에게 풀릴 줄 알았는데, 의외로 다들 못 풀어서 1등을 할 수 있었다.

 

여담으로 A번은 후원사 문제인데, 우리 팀만 풀었다. 후원사 문제가 안 풀렸으면 조금 참사였을 것 같은데, 그래도 풀려서 다행이다. 후원사 문제를 가장 처음으로 푼 팀에게 자동차 모형을 줬다. 푼 팀이 우리 팀 밖에 없어서 우리가 받았다.

문제별 분석

내가 본 문제들은 다음과 같다.

• A: 풀이는 자명한데, 구현은 길었다. ICPC에서 나올 법한 문제이지만, 좋은 문제인지는 모르겠다.
• C: 비빔밥에 비빔밥을 비비면 되는 문제. 적당히 쉬운 비빔밥이었다.
• E: 이게 28분에 풀릴 만큼 쉬운지 모르겠지만, 좋은 인터랙티브 문제인 것 같다. 아이디어도 꽤나 재미있다.
• F: 그냥 쉬운 문제인데 내가 절었다.
• H: 적당히 쉬운 문제.
• I: 자료구조 비빔밥으로 위장을 한 적당히 좋은 애드혹 문제이다. 로그를 떼는 관찰을 못해서 아쉽다.
• J: 기하 구현을 잘 하는지 시험하는 문제이다.
• L: 어려운 문제인데, 대부분의 팀이 찍어서 맞추거나 적당한 휴리스틱으로 풀었다. 나는 휴리스틱을 잘 못해서 어떻게 한건지 잘 모르겠다. 휴리스틱으로 풀리는 문제는 ps에 적합하지 않다고 생각한다. 정해는 깔끔한데, 휴리스틱을 막을 수 없는 문제의 구조가 아쉽다.
  • 고등학생 때 비슷하게 휴리스틱으로 풀리는 구성적 수학 문제를 낸 적이 있다. 1부터 N까지의 정수로 이루어진 수열 중 자연수 i는 phi(i)번 등장하고, 인접한 두 수가 서로소인 수열을 찾는 문제였다. 의도하지 않은 그리디 풀이로 많이 뚫려서 아쉬워했던 기억이 있다. 아래는 예쁜 구성적 풀이이다.

분모가 N 이하인 0 이상 1 이하의 기약분수들을 정렬한 후 순서대로 분모를 출력한다. farey sequence를 공부하면 인접한 두 기약분수의 분모가 서로소라는 것을 알 수 있다.

대회 후기

초반에 문제를 급하게 풀다가 말렸다. 오랜 고민 끝에 초반 문제들은 제출하기 전에 1분씩 검토를 하면 좋겠다는 결론에 도달했다. 중반전과 후반전에서 각성해서 E번을 20분만에 풀고 A번을 1번에 맞은 것은 잘한 것 같다. 

태인이가 I, J번의 문제를 잘못 읽고 나는 F번의 문제를 잘못 읽었다. 지문을 잘못 읽는 것은 어떻게 고칠지 잘 모르겠다.

I번도 풀고 G번도 풀었으면 좋았겠지만, 그래도 1등을 했으니 만족한다. 팀연습을 열심히 해서 더 잘해지고 싶다.