2025 숭고한 연합대회 후기

https://youtu.be/2JThzlur7ME?si=bKCk2vr_x-drqtKW

오랜만에 쓰는 ps글이네요.

올해 무려 3년만에 숭고한(숭실대, 고려대, 한양대) 연합 대회가 열렸습니다. 저는 25학번 새내기이기 때문에 한양대 ALOHA 소속으로 Div.1 부문 대회에 참여하게 되었습니다. 

 

팀원 구성

Div.1은 최대 3인팀 대회이기 때문에 팀원을 구해야 했습니다. ICPC팀원 중 한명인 한양대 25학번 김누스(gmroh06)와 함께 2인팀으로 나가게 됐습니다. 팀명은 절대 군대로 도망간 누군가를 저격하기 위해서 정한건 아니고, "도피성 군휴학"으로 했습니다.

 

gubshig: 접니다. 자료구조, 그래프 등의 문제에 강하지만 처음 보는 문제를 잘 풀지 못하고 코딩 실수를 자주 하기 때문에 팀의 패널티 쌓기를 주로 담당합니다.

김누스: 코드포스 오렌지, 앳코더 옐로우입니다. 애드혹, 구성적, 많조분, dp, 그리디 등등 머리 쓰는 문제를 잘 풉니다.

 

팀원 구성에는 치명적인 문제가 있는데, 문자열과 기하를 할 줄 아는 사람이 없습니다. 문자열은 해싱 정도를 짤 수 있고 기하는 CCW는 짤 수 있나? 그래서 대회에 문자열과 기하가 나오지 않기를 기도했습니다.

https://gmroh.tistory.com/24

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

김누스의 후기도 같이 읽어보면 좋습니다.

 

대회 전

대회 하루전

대회 당일

팀노트의 존재를 대회 하루 전에 인지하였기 때문에, https://github.com/justiceHui/icpc-teamnote-for-newbie 를 그냥 가져가기로 했습니다. 제가 출력을 해가야 하는데, 대회 당일 오전 선린에서 강의가 있었기 때문에 시간이 굉장히 아슬아슬해서 팀노트 출력을 못했습니다. 

 

대회장에 시작 5분전인 1:55 정도에 도착했는데, 마침 대회가 30분 연기되었습니다. 나가서 출력하고올까 상의해봤는데 그냥 귀찮고 gggkik가 애드혹 10문제 냈을 것 같으니 필요없을거라는 결론이 나와서 팀노트 없이 참가하게 되었습니다.

 

대회장에 들어가니 맨 앞에 jhnah917선배가 보였습니다. 운영으로 참가했을 줄 알았는데 숭고한은 졸업 1년 이내도 참가 가능해서 참가로 왔다고 합니다. 팀원으론 월파팀 멤버가 온 것 같습니다. 우리팀이 1등은 절대 못하겠구나 싶었습니다. 이 선배가 운영하는 대회에만 참가했었는데 (천코대, KOI, NYPC 등등...) 같은 대회에 처음으로 참여하게 되어서 신기했습니다.

 

대회

김누스가 A, B, C, D, E
제가 F, G, H, I, J, K를 우선적으로 보기로 했습니다.

 

F를 읽어봤는데, 자명한 누적합 문제였습니다. 다만 정렬 후 누적합을 한 다음 원래의 인덱스를 복원하는 과정이 필요해서, 구현하는데 시간이 좀 걸렸습니다. 옆에서 누스가 E는 그냥 스투라 짜면 바로 풀린다고 합니다. 

00:08 F WA (-1)

틀렸습니다. 코드를 자세히 읽어보니 인덱스 복원 과정이 잘못되었습니다. 절대 하면 안되는 실순데 마음이 너무 급했나 봅니다. 이때부터 페널티가 점점 쌓이기 시작합니다.

 

00:10 F AC (1 solve)

2등

한줄을 고치고 적당히 검토 후 AC를 받을 수 있었습니다. 누스한테 컴퓨터를 넘겨주고 G부터 읽어봤습니다.

이때 문제를 읽고 느낀점은,

G: 나만 모르는 웰논 쿼리문제

H: 애드혹 수학 문제
I: 어려워보이는 게임이론 문제
J: 잡으면 풀면 안될 것 같은, 누가봐도 gggkik가 출제한 인터랙티브 문제

K: 제한이 DP같아보이는 문제

 

K가 제일 할만해보여서 누스가 E를 짤 동안 DP식을 이것저것 세워보고 있었습니다. 

 

00:28 E WA (-1)

6등

틀렸습니다. 슼보를 보니 A가 꽤 많이 풀렸습니다. 누스가 잘 모르겠다고 저한테 던져줬습니다. 디버깅 하는동안 A 풀이를 생각해봅니다. 우선 빠른 시점에 많은 솔브가 나왔으니, 풀이가 복잡하진 않을거라 예상했습니다. 트리에서 4-coloring 이상만 가능하게 해야하기 때문에, 우선 이분그래프면 안됩니다. 간선 하나 추가로 홀수사이클을 만들 수 있습니다. 잘 생각해보면 그냥 2, 3 coloring이 불가능한 부분그래프가 존재하기 때문에, 그래프를 넓게 볼 필요가 없습니다. 길이 3짜리 사이클을 만든 후, 3개의 정점과 인접한 아무 정점을 잡고 간선 2개 더 추가해주면 3개로 모든 경우에 가능합니다. 3보다 더 작은 케이스가 가능한지 생각해봤지만, 안될 것 같아서 코드 구체화에 들어갔습니다.

 

00:39 E WA (-2)

8등

A를 짜고 있었는데 누스가 E 조금만 고치면 된다고 해서 컴퓨터를 넘겨줬습니다. 틀렸습니다. 다시 컴퓨터를 넘겨받고 A를 짰습니다. 풀이는 간단하나 구현이 조금 귀찮아서 시간이 걸렸습니다.

 

00:55 A AC (2 solve)

9등

맞았습니다. 슬슬 등수가 많이 밀리기 시작해 조금 불안했습니다. I가 좀 재밌어보여 고민하고 있었습니다.

 

01:04 E WA (-3)

9등

틀렸습니다. 패널티가 슬슬 진짜 망했습니다. 저는 I가 재밌어보여 고민하고 있었습니다.

 

01:09 I WA (-1)

01:10 I WA (-2)

9등

틀렸습니다. 틀렸습니다. I 풀이는 대충 증명하고 대충 맞는 것 같아서 짰는데, 왜 틀리는지 모르겠습니다. 최종적으로는 전체 xor 합 $T$에서 어떤 두 $i, j$에 대해 $T \oplus A_i \oplus B_j$가 결과로 나올 것입니다. 어떤 $A_i$에 대해 최소화하는 $B_j$가 존재합니다. 선공이 어떤 방법을 쓰던, 후공은 항상 이러한 $B_j$를 게임에 존재하는 모든 $i$에 대해 남겨줄 수 있습니다. 그렇가면 선공은 그러한 것들 중 $T \oplus A_i \oplus B_j$가 최대화되는 $A_i$를 고를 것입니다. 이제 어떤 $A_i$에 대해 최소화하는 $B_j$를 각각 계산해주고, $T \oplus A_i \oplus B_j$중 최댓값이 답이 됩니다. 근데 틀렸습니다.

 

01:11 E AC (3 solve)

8등

옆에서 누스가 E 도움을 요청해 풀이를 들어봤습니다. 트리에서 어떤 경로의 간선 xor합이 0이 되는 경우의 수를 세야하는데, 리루팅 스투라 같은걸 짜고 있었습니다. xor연산의 특성상 그냥 루트부터 누적 xor만 계산해줘도 됩니다. LCA에 대해 루트부터 LCA까지의 xor합은 제거되기 때문에. 그래서 이걸 바탕으로 스투라를 다시 짜니 맞았습니다. 누스의 풀이도 대충 들어보면 맞는 것 같은데, 아마 구현이 조금 까다로워서 틀리고 있었던 것 같습니다. 대회 끝나고 들어보니 스투라를 할 필요도 없이 누적 xor합이 같은 애들끼리만 세주면 된다고 합니다. 

 

01:13 I WA (-3)

01:30 I WA (-4)

01:32 I AC (4 solve)

7등

I가 도저히 왜 틀리는지 모르겠어서 누스한테 도움을 요청했습니다. 풀이를 얘기하니 맞는 것 같다 해서 코드를 같이 봤는데...

누스가 대체 이게 왜 xor 최솟값을 구하는 코드냐고 물어봤습니다. 엥 이거 대충 되는거 아님? 했는데 1초만에 반례가 나왔습니다. xor 최소와 관련된 다른 문제의 풀이와 햇갈려 뻘짓을 하고 있었습니다. 운영진들이 이 코드 보고 로워바운드는 대체 어디서 처나왔냐고 개충격먹었다고 합니다... 트라이를 짜면 해결할 수 있지만 저는 트라이를 못짜기 때문에 누스한테 트라이 부분을 맡겼습니다. 그 후 AC를 받을 수 있었습니다. 슬슬 패널티가 진짜 개망해서 서로 어차피 망했으니까 걍 무지성 제출하자는 결론이 나왔습니다. 이런 짓을 하지 말아야 했는데...

 

01:41 H AC (5 solve)

4등

H가 많이 풀리길래 조금 고민해봤습니다. 홀짝성에 따라 $f(x) = f(x / 2)$ 또는$ f(x) = f((x+1) / 2) + 1$ 같은 결과가 나오는데, 잘 생각해보면 홀수가 그냥 ㅈ티멀입니다. 그래서 구간 $[a, b]$에 대해 끝점에 유의하며 범위를 반으로 나눌 수 있고, 그러면 쿼리당 대충 $\mathcal{O}(\log^2 X)$ 정도에 풀립니다.

 

02:03 D WA (-1)

02:09 D WA (-2)

02:11 D WA (-3)

02:15 D WA (-4)

02:17 D WA (-5)

02:17 D AC (5 solve)

5등, 당시엔 프리즈여서 등수 몰랐음

김누스가 D를 잡았습니다. 저는 그동안 G와 K를 번갈아 고민해보고 있었습니다. 패널티를 포기한 상태였기에, 그냥 D를 막 제출했습니다. 나중에 듣기론 누스의 거의 풀이는 맞았는데 6이라는 단 하나의 반례만 존재했습니다. 아무튼 저랑 같이 디버깅하면서 이것저것 해보다 5번의 WA 끝에 맞을 수 있었습니다.

 

02:36 K WA (-1)

02:38 K WA (-2)

02:45 K WA (-3)

02:48 K WA (-4)

02:49 K WA (-5)

02:59 K WA (-6)

5등, 당시에 프리즈여서 등수 몰랐음

틀렸습니다. 틀렸습니다. 틀렸습니다. 틀렸습니다. 틀렸습니다. 틀렸습니다. 망했습니다. 누스가 D를 풀 동안 저는 G를 버려야겠다는 판단 후 K DP식을 세우고 있었습니다. 적당히 세그꼴이 나와서 $\mathcal{O}(N^2 \log N)$ 정도에 풀릴 것 같습니다. 이걸 구현했는데... 엄청 틀렸습니다. 제가 대회 후반 가면 멘탈이 조금 많이 갈리는 성격인 것 같습니다. UCPC 본선때도 이랬던 것 같은데... 말도안되는 실수도 하고... 세그 구현을 틀린다던가 음수 인덱스를 넣는다던가 DP값 구해두고 갱신을 안한다던가...

 

02:59 K AC (7 solve)

3등, 당시에 프리즈여서 등수 몰랐음

김누스가 개똑붙 prefix, suffix max를 이용한 $\mathcal{O} (N^2)$ 최적화를 생각해냈습니다. 이건 구현도 훨씬 간단하고, $N = 5000$이기 때문에 제곱로그는 제한 상 조금 아슬아슬해보였는데 이건 확실히 돌 것 같았습니다. 나중에 들어보니 제곱로그는 TLE를 받을 것이라 합니다. 대회 종료 30초전? 정도에 맞아서 이때 진짜 심장이 엄청 빨리 뛰었습니다.

 

대회 종료 후

PS AGI팀이 8솔이라는 얘기를 들었고, 프리즈상 2등부터 6등까지 가능해보였기에, 긴장이 정말 많이 되었습니다. 순위상은 3등까지만 받을 수 있었습니다. 

기적적인 반등에 성공하여 3등에 성공했습니다! 순위상 20만원을 쌀먹했습니다. G를 못푼것이 조금 아쉽지만, 그걸 제외하면 풀어야 하는 문제는 다 푼 것 같아 만족스럽습니다. 

 

패널티 관리를 너무 못한 것이 조금 아쉬웠습니다. 두명 중 한명만 정신 차렸어도 괜찮았을 것 같은데 둘 중 한명은 밥을 안먹었고 한명은 잠을 안잤기 때문일까요? 2등과 패널티가 2배 차이 났습니다.

 

결과적으로 팀노트는 필요 없었습니다. 기하 문자열 이런게 안나와서 정말 다행입니다...

 

끝나고 뒷풀이 가서 jms020820님의 화려한 숟가락으로 맥주따기 쇼를 보고 재밌게 얘기하다 집으로 왔습니다.

 

대회 운영, 출제로 수고하신 운영진분들 정말 수고 많으셨고 재밌는 대회 개최해주셔서 감사합니다!