2025 숭고한 연합 알고리즘 경진대회 후기

ICPC 팀에서 팀원 1명은 운영진으로 참여했기 때문에 3인팀 대회지만 남은 1명인 준호(gubshig)와 참여했다. 어려운 자료구조나 웰노운 트릭들에 능통하다. 대회 중에 솔브 수가 적은 다이아 문제의 풀이를 다수 낸 적이 있고, 실제로 맞는 풀이였지만 항상 2% 모자란 구현 때문에 고생한다. 내가 DP나 애드혹, 구성적 같은 문제들을 주로 담당하고 준호가 자료구조, 웰노운, 그래프 같은 문제들을 주로 담당한다. 다만 문자열이나 기하학 문제들은 둘 다 싫어해서 팀노트 없이는 코딩도 못하는 수준이다. 팀명은 도피성 군휴학인데, 누구를 저격한다거나 하는 건 당연히 아니다. 다만 개인 닉네임을 제출했는데 스코어보드에 반영되지 않아서 아쉬웠다.

 

대회 전날, 당장 작성된 팀노트가 없어서 팀노트를 어떡할 거냐고 물어봤더니 그냥 인터넷에 있는 것을 그대로 출력해 오겠다고 했다. 대회 당일, 전날 잠도 많이 못잔 상태로 SCPC 본선을 쳤기 때문인지 무려 13시간 숙면을 취하고 대회 1시간 전에 일어났다. 밥먹을 시간이 없을 것 같아 천천히 씻고 학교로 향했다. 와중에 준호는 고등학교에서 뭘 하고 오느라 팀노트 출력을 못할 것 같다고 했다. 마침 대회가 30분 연기되긴 했지만 나오지 않을 것이라 기도하고 팀노트 없이 참여했다. 대회 직전 숭실대 월파 팀이 왔다는 것을 알게 되어서 2위 경쟁이나 하자는 얘기를 했다. 나는 A부터 E까지, 준호는 나머지 뒤쪽을 보기로 하고 대회가 시작되었다.

 

https://gubshig.tistory.com/86

준호의 후기이니 함께 읽어도 좋을 것 같다.

 

~ 00:10 (F AC +1)

거의 대회 시작하자마자 F가 풀렸고, 준호가 실버라면서 제출했고, 1번 틀리고 맞았다. 나는 E를 보고 있었는데, 내가 자신 있는 XOR, 트리를 합친 문제였고 빠른 솔브가 나와서 자신있게 잡고 있었다. Small to Large를 쓰면 풀릴 것 같아서 고민하고 있었다.

 

~ 00:39 (E WA +2)

결국 나는 Small to Large에 Rerooting을 결합한 요상한 풀이를 완성하고야 말았고, 이론상 맞을 것 같지만 구현에서 실수했는지 2번 틀렸다. E가 빠른 시간에 풀렸다는 것을 눈치채고 더 간단한 풀이를 생각했어야 했는데 벌써 패널티가 꽤 쌓여 버렸다. A가 풀리고 있었기 때문에 내가 E를 디버깅할 동안 준호한테 A를 던져줬다.

 

~ 00:55 (A AC)

다행히 내가 이상한 짓을 하고 있는 동안 준호는 풀어야 할 문제들을 풀어 주었다. A 풀이를 바로 내더니 1번에 맞았다.

 

~ 01:10 (E AC +3, I WA +2)

나는 E에서 계속 헤매고 있었고, 준호가 I를 보더니 풀이가 나왔다며 제출했지만 2번 틀리고 말았다. 벌써 패널티가 망해버렸다. 

스코어보드 상에서 E가 매우 많이 풀렸기 때문에 준호에게 도움을 요청했고, 준호가 바로 다른 풀이를 찾아냈다. 루트부터 정점들 까지의 모든 가중치를 XOR한 값만 있으면 풀리는 문제였다. 어차피 공통 조상들의 가중치는 XOR하면 사라지기 때문에 루트부터 정점까지 같은 값들의 개수를 세면 된다. 기존 코드에서 조금만 고치면 됐기 때문에 빠르게 구현해서 정답을 받았다.

골드 문제에 이렇게 오래 걸린 것도 모자라 패널티를 쌓아버렸다. 심지어 나는 이 아이디어를 쓰는 문제를 전에 푼 적이 있었지만 한 번 말리니까 이런 생각도 잘 나지 않았다. Local Minima에 빠지면 잘 빠져나오지 못하는 내 단점이 드러난 경우라고 생각한다.

 

~ 01:32 (I AC +4)

나는 H를 읽어 보고 있었는데 옆에서 준호가 계속 맞왜틀을 외치고 있었다. 풀이를 들어 보니 풀이는 맞는 것 같아서 구현을 살펴봤더니 XOR 최소를 구하는 코드를 이분탐색으로 짜고 있었다.... 바로 반례가 나왔고 트라이를 이용하는 풀이로 선회했다. 준호가 트라이를 못짠다고 해서 보고 있던 H를 준호에게 주고 내가 구현했다. 트라이를 오랜만에 구현해서 좀 시간이 걸리긴 했지만 정답을 받았다. 나중에 들어보니 집합 내에서 모든 쌍의 XOR 최소를 구하는 문제가 있었는데, 이 문제의 풀이와 헷갈렸다고 한다.

 

~ 01:41 (H AC)

내가 트라이를 짤 동안 준호가 H 풀이를 내왔고 바로 구현해서 정답을 받았다. 

둘 다 부진했다고는 하지만 준호는 그래도 풀어야할 문제들을 바로 풀어 주었고 골드 잡고 리루팅 스투라 짜다가 1시간만에 폭사한 내가 더 심했다고 생각한다.

 

~ 02:17 (D AC +5)

초반의 부진을 만회하기 위해 D를 잡았고, 풀이가 바로 나와서 제출해 봤더니 틀렸다. 스코어보드에서 다른 팀들도 많이 틀렸던 문제였기 때문에 제출에 신중했어야 했지만 이미 패널티를 포기했기 때문에 편하게 제출했다. 옆에서 준호가 G랑 K를 보고 있었고, 내 풀이를 들어 보더니 홀수일 때는 $N \over 2$와 ${{N} \over {2}} + 1$이 서로소이기 때문에 최적이지만, 짝수일 때는 $N \over 2$와 ${N \over 2} - 1$이 최적일 수도 있다는 아이디어를 내서 이를 반영해서 제출했지만 또 틀렸다. 좀 더 고민하다 짝수일 때 홀수로 바꿔버리면 하나가 남는데 이를 시작점으로 세팅하면 1이 늘어날 수 있다는 사실을 생각해냈고 구현해서 제출했더니 드디어 정답을 받을 수 있었다. 자잘한 실수 때문에 패널티를 조금 더 받았다.

 

~ 02:59 (K AC +6)

준호가 K 풀이가 나왔다고 해서 풀이를 들어봤다. 풀이 자체는 맞는 것 같았지만 예제도 안 나오는 상황이라 같이 코드를 디버깅해 봤다. 세그먼트 트리에 $N^2$까지 써서 $O(N^2logN)$ 풀이였다. 열심히 디버깅하던 중 세그먼트 트리 구현에서 치명적인 실수를 찾았고, 예제가 나오는 것을 확인하고 제출했으나 틀렸다. 준호가 세그먼트 트리를 제한에 딱 맞게 구현해서 인덱싱에서 나오는 실수인 것 같다고 크기를 늘려서 제출해 봤으나 이번에는 시간 초과를 받았다. 나는 $N$이 5000이라 로그가 있으면 안될 것 같다고 했지만 첫 제출에서 시간초과가 아니라 틀렸습니다를 받았기 때문에 준호 의견대로 틀린 부분을 찾아 보기로 했다. 코드를 살펴 보던 와중 세그먼트 트리의 구간 쿼리가 suffix 또는 prefix밖에 없다는 것을 관찰하고 prefix min, suffix min을 이용하자는 의견을 냈고, 준호가 듣고 맞는 것 같다며 급하게 구현하기 시작했다. 결국 마감 30초 쯤을 남기고 정답을 받는 데 성공했다.

 

대회 최종 스코어보드

대회 중 순위 변화

 

패널티를 2등과 2배 차이가 날 정도로 쌓기는 했지만 솔브 수가 많았기 때문에 수상권에 드는 것은 성공했다. 풀어야 할 문제는 다 풀었다고 할 수 있지만 쌍으로 신들린 퍼포먼스를 보여주다 페널티를 미친듯이 쌓아버리고 말았다. 나는 E에서 이상한 풀이를 생각하고 빠져나오지 못한 점이, 준호는 I에서 어이없는 풀이를 낸 점이 아쉬웠다. 3시간 대회라 한 번의 실수가 치명적인데 두 명 모두 번갈아서 대형 사고를 쳐버렸다. 게다가 G가 Mo's 알고리즘을 이용하는 문제였는데, 내가 Mo's 문제를 꽤 많이 풀어봐서 E를 빨리 해결하고 G에 시간을 투자했으면 풀 가능성이 있었을 것 같다. 그래도 후반에는 둘 다 뒷심을 발휘해서 꽤 성공적으로 복구한 것 같다. 

 

결과적으로 둘 다 부진하긴 했지만 굳이 따지자면 내가 더 못한 것 같다. 나는 초반에 풀어야 할 문제를 1시간 동안 3번 틀리며 잡고 있어서 후반까지 누적되는 치명적인 실수를 했지만 준호는 초반에 풀어야 했을 문제는 아니기 때문이다. 그래도 긍정적인 점은 서로 실수를 하는 동안 다른 한 명이 빠르게 피드백해 주었다는 것이다. 다른 문제들을 푸는 과정에서도 내가 K에서 낸 아이디어나 준호가 D에서 낸 아이디어 등을 보면 의견 교환이나 합 자체는 잘 맞는 것 같다. 앞으로 실수만 좀 줄일 수 있다면 매우 좋은 퍼포먼스가 나올 수도 있을 것 같다.