SUAPC 2026 Winter 후기

사건의 발단

SUAPC는 서강대, 숙명여대, 연세대, 이화여대, 홍익대의 재학/휴학생이 참가할 수 있는 대회이다.

 

그리고 나는 연세대 입학을 앞두고 있다. 그러나 아직 입학을 하지 않았기 때문에 재학생이라고 볼 수 없는 상태다.

 

따라서 나는 2026 Winter는 참가가 불가능하다고 생각하고 있었다.

 

 

그러나 어떤 연락이 오게 되는데...

 

 

팀 구성

Ice Cream Pizza Crust  /  Serendipity__, JYJin, kolorVXL

 

어쩌다가 ICPC에서 Endgame으로 활동하시는 두 분과 팀을 하게 되었다.

 

맥스 레이팅 기준 무려 3레드라는 어마무시한 고스펙 팀이 만들어졌기 때문에 사실 우승이 정배기는 했다.

 

 

대회 전

 

대회 운영진으로서 일하고 계신 rammma님, gs22059(annyeong1)님과 인사를 했고,

 

다른 팀의 참가자인 lindelof님, trashmouse0524(jkrt2)님, dong5995님과도 인사를 했다.

 

 

멀리서 오는 거다 보니 여유있게 일정을 짰다.

 

그러다가 밥 먹고 올 시간이 애매해져서 급하게 편의점에서 컵라면을 먹고 왔다.

 

그 외에는 ystaeyoon113(Serendipity__)님께 VSC 세팅에 대한 초스피드 강의를 들었다.

 

 

대회 시작

A 유림이와 하람이의 두쫀쿠 대작전 (0:01)

대회 시작과 동시에 playsworld16(JYJin)님이 A를 짜면서 AC를 받았다.

나는 무슨 문제인지 모른다.

 

J 지하철! 지하철! 몇호선? 몇호선? (0:08) +1

그러고 나서 ystaeyoon113(Serendipity__)님이 스코어보드를 따라 J를 읽고 바로 짰다.

그런데 한 번 WA를 받으셔서 다시 문제를 읽으시고 AC를 받았다.

나는 무슨 문제인지 모른다.

 

M 괄호 문자열 카드 (0:12)

이건 아마 playsworld16(JYJin)님이 푸신 걸로 알고, J랑 동시에 돌려가면서 AC를 받았다. 

나는 무슨 문제인지 모른다.

 

H 신촌 방수 계획 (0:19)

그러고 나서 내(kolorVXL)가 A, J, M이 풀릴 때까지 계속 읽고 있었던 문제의 풀이를 냈다.

나는 우산 보관소를 짓지 않는 경우부터 시작해서 필충 조건을 찾았고,

따라서 엣지 케이스를 간과하지 않고 빠르게 풀이를 찾았다.

 

사실 두 분을 팀으로 만난 건 처음이라 대회 초반에는 눈치를 조금 봤다.

이 정도 확신으로 머신을 잡고 코드를 제출해도 되는지 고민이었다.

그래서 검증을 조금 더 해보고, M이 나오자마자 코드를 짜겠다고 하고 바로 AC를 받았다.

 

E 가지가지 (0:37)

그러고 ystaeyoon113(Serendipity__)님이 E 풀이를 내고 구현까지 바로 잡고 AC를 받았다.

나도 초반에 E를 읽긴 했지만 가지를 최대한 많이 배치해야 하는 줄 알고 던져버렸다...

 

B 수열 정렬 수수께끼 (0:53)

이거는 아마 playsworld16(JYJin)님이 잡고 AC를 받았던 문제일거다.

나도 초반에 B를 읽긴 했지만 인접한 것끼리만 교환 가능한 줄 알고 던져버렸다...

 

C 숫자 놀이 (1:04)

이 문제는 ystaeyoon113(Serendipity__)님이 러프한 풀이를 냈고,

내가 이거를 우선순위 큐로 돌려가면서 풀면 되겠다고 했다.

 

풀이는 작은 날씬한 수에 2보다 크거나 같은 정수 c를 곱함으로써 큰 날씬한 수를 알아가는 건데,

문제는 c를 어디까지 증가시켜봐야 하는지를 알 수 없었다는 점이다.

 

그런데 이때 playsworld16(JYJin)님이 그냥 60까지만 돌려보면 된다고 했다.

그래서 내가 구현하고 AC를 받았다.

 

K MC 히페리온 (1:37) +2

이 문제는 ystaeyoon113(Serendipity__)님이 여러 문자열 알고리즘을 말하다가 잡고 푼 걸로 기억하고 있다.

구현이 끔찍했던 것인지 두 번 WA를 받았고, 디버깅을 어떻게 잘 해서 AC를 받으셨다.

나는 무슨 문제인지 모른다.

 

G 히스토그램에서의 거리와 가장 가까운 점 (1:58)

대체 무슨 이유로 그렇게 판단했는지는 모르겠는데 G가 너무 해볼만하게 생겨서 계속 도전했다.

 

먼저 생각한 건 각 막대의 맨 위를 정점으로 찍은 후 멀티소스 다익스트라를 돌리는 풀이였는데 돌아서 가는 경우는 커버가 되어도 돌아가지 않는 경우는 커버가 되지 않아 포기했다.

 

그 다음으로 생각한 건 위, 아래, 오른쪽으로만 움직일 수 있을 때의 거리를 구할 수 있다면 정방향 스위핑과 역방향 스위핑을 돌려서 답을 구할 수 있지 않겠는가 하는 생각을 했다.

 

이러면 스위핑을 할 때 각 위치마다 최소 거리를 나타내는 그래프가 소닉 웨이브 형태가 되고, 이 소닉 웨이브에 해야 하는 연산은 점을 추가하거나 전체 수위를 하나 올리는 것이었다.

 

이 소닉 웨이브를 대체 어떻게 관리할지 고민을 했다. 세그먼트 트리를 쓴다면 막대의 길이가 10억이었기 때문에 좌표 압축이나 다이나믹 세그먼트 트리를 써야 했는데, 둘 다 구현하다 주화입마가 올 게 분명했다. 그러다 생각한 똑붙 풀이가 트리셋질이었다.

 

그래서 그냥 열심히 짜서 AC를 받았다.

 

 

G 소닉 웨이브 관리법

 

집합 안에 (p, q)라는 점을 여러 개 넣을 수 있고, 이 집합을 가지고 만들 수 있는 f(x) = (모든 점 (p, q)에 대해 |x - p| + q의 최솟값) 이라고 하자. f(x)는 당연히 소닉 웨이브 형태일 것이고, 우리가 원하는 어떤 소닉 웨이브 형태든 만들 수 있다.

 

여기서 집합 안에 있는 어떤 점들은 제거해도 f(x)가 변하지 않을 수 있다. 예를 들어 (0, 0)과 (1, 1)이 있다고 하면 모든 실수 x에 대해 |x - 0| + 0이 |x - 1| + 1보다 작거나 같다. 이런 경우를 (1, 1)이 (0, 0)에 포함된다고 하자. 이러한 포함 관계에 해당하는 점이 없도록 집합을 관리해야 한다.

 

집합에 이러한 포함 관계에 해당하는 점이 없다면, 우리는 f(x)의 값을 알기 위해 x <= p이고 p가 제일 작은 (p, q)와 x >= p이고 p가 제일 큰 (p, q)에 대해서만 |x - p| + q를 봐주면 된다. 이게 가능한 이유는 대충 그래프 그려보면 감이 올건데 나는 수학자가 아니니까 증명은 생략한다.

 

만약 여기에 (r, s)와 같은 점을 추가해야 한다면 (r, s)에 포함되는 (p, q)를 전부 지우면 된다. r <= p이고 p가 제일 작은 (p, q)를 고른 뒤 (p, q)가 (r, s)에 포함된다면 지우고 처음으로 돌아가고, 아니면 작업을 종료한다. r >= p이고 p가 제일 큰 (p, q)에 대해서도 비슷하게 작업해주면 된다. 이러면 당연히 amortized O(log N)이 나올 수밖에 없고, 이렇게만 지워도 되는 이유에 대한 증명은 생략한다.

 

증명을 생략해서 화날 수 있긴 한데 그림 그려보면 대충 자명하다고 생각한다 (아님 말고)

 

D Yet Another Binary Problem (3:21)

이 문제는 playsworld16(JYJin)님이 다음과 같은 의견을 냈다: '모든 원소를 제거하는 해가 존재함'과 '01을 그리디하게 지웠을 때 N번 이상 지울 수 있으며 10을 그리디하게 지웠을 때 N번 이상 지울 있다'가 필요충분조건일 것이다.

 

어쨌든 필요충분조건이 맞을 것 같다는 생각으로 관찰을 시작했고, 여기서도 소닉 웨이브 산을 그려줌으로써 위에 있는 놈과 아래에 있는 놈 중 작은 놈을 먼저 없애주고 어떻게 잘 비비면 풀린다는 해 구성법을 내고 AC를 받았다.

 

F 트리와 쿼리 24 (4:41)

그 뒤로 남는 문제인 I, F, L을 돌려가면서 봤다. I는 두 분이서 계속 보고 계셔서 그냥 안 봤고, L은 대충 읽어봤을 때 절대 풀 수 없겠다는 판단을 내리고 F를 봤다.

 

사실 초반에 F를 읽고 입력 제한과 시간 제한을 보고, 그리고 또 출제진으로 mythofys가 참가한다는 사실을 알고 이 문제는 무조건 루트질이라고 생각했다. 물론 로그 제곱을 완전히 간과한 건 아니다. 그러나 이후 출제자를 확인했을 때 출제자는 다른 분이셨다... 어쨌든 루트질로 풀었으니 좋았쓰

 

이 문제는 처음부터 트리가 특정 형태가 나오지 않을까, 하는 이야기가 있었고 쿼리 연산도 상당히 의심스러웠기 때문에 꽤 여러가지 구성을 해봤다. 그 중에서 세그먼트 트리 혹은 스파스 테이블을 이용하여 O((NlogN)^1.5)에 관리하는 방법은 이미 찾았었지만, 상수 따위 신경쓰지 않고 구현하는 나의 특성상 무조건 터질 것이 분명해서 루트로그는 안중에도 없었다. 나중에 들어보니 오픈콘에서는 전부 루트로그를 상수 깎기로 풀었다더라...

 

LCA를 구하기 위해서 스파스 테이블을 많이 쓰지만, 모양이 수상하기 때문에 x, y 중 정점 번호가 큰 것을 부모 방향으로 움직이면서 x == y가 같아지면 그것을 LCA로 판정하는 방향을 생각했다. 이 때 v - a를 부모로 가지는 정점 v에 대해, a의 값이 같은 것들끼리 그룹으로 만들어주고, 한 그룹 안에서 정점에서 부모 방향으로 움직여서 다음 그룹으로 나가는 것을 간단한 나눗셈 연산으로 O(1)에 하게 만들었다. 만약 a의 값이 √N보다 크다면 점프 크기가 애초에 √N이기 때문에 최대 √N번 점프할 수 있고, a의 값이 √N보다 작아도 그룹마다 최대 한 번 점프할 수 있으므로 최대 √N번 점프할 수 있다. 따라서 점프의 횟수는 2√N에 바운드되고 성공적인 루트질을 할 수 있다.

 

I 별동대 -7

이 문제는 아쉽게도 풀지 못한 문제다. 사실 난 문제를 제대로 안 봤고, F를 푼 후 남은 시간 동안 풀이에 대해 들었다. 당초 JYJin님이 제안하신 풀이가 Max-flow min-cut인데, 플로우를 잘 모르는 내가 봐도 민컷이 맞다고 생각했다. 그러나 문제가 되는 것은 역시 경우의 수 세기인데, 이것을 어떻게 해결해야 할지 계속 생각하다 망했다. 정해는 민컷이 아니었지만 어차피 내가 풀 수 있는 문제도 아니었고 출제진/검수진 의도도 F나 G보다 약간 더 어려운 수준이었기 때문에 (적어도 나는) 후회가 없다.

 

 

대회 종료

 

아무튼 1등했다.

 

프리즈 이후 모든 문제에 제출한 팀이 모든 문제를 맞췄을거라고 보기는 어려웠고, 실질적으로 위협이 되는 팀이라고 하면 역시 lindelof님이 속한 placeholder팀이었다. placeholder팀은 프리즈 이후 D, I에 제출했고, 우리 팀에게는 최악의 상황인 D, I 솔브를 했을 거란 가정을 하고 솔브 수 차이를 내기 위해 열심히 문제를 풀었다.

 

우리 팀은 프리즈 이후 D, F, I에 제출했다. 모르는 사람 입장에서 Ice Cream Pizza Crust가 D, F, I를 셋 다 못 풀었고 placeholder 에서 D, I를 풀었다면 placeholder가 솔브 수 차이를 내며 우승하는 가능성을 상상해볼 수 있었다. 그런 긴장감을 해치고 싶지 않았다기보단 분탕을 치고 싶었기에 D, F를 풀었다는 사실을 프리즈 해제 전까지 말하지 않았는데, D, F를 못 풀었더라도 1등이었다니 뭔가 느낌이 이상했다.

 

D, F를 못 풀었더라도 패널티만으로 1등을 할 수 있었던 이유는 단연 ystaeyoon113(Serendipity__)님과 playsworld16(JYJin)님 덕분이다. 나는 애초에 패널티를 관리하는 스타일이 아니고 (계속 연습하다보니 패널티 관리가 압도적으로 잘 되는 경우가 종종 있지만, 저점 관리는 패널티가 망했을 때 솔브 수를 늘리는 식으로 관리한다) 초반 문제들도 잘못 읽고 풀기 싫다고 막 던지는 기행을 벌였다.

 

다만 F를 풀었던 건 잘한 일이라고 생각한다. D는 팀원 분들의 관찰에 도움을 많이 받았고... G는 그렇게 안 어려운데 하위호환 문제가 P1이라 이상하게 고평가된거고 F는 솔직히 좀 어려웠는데 어디서 지나가다 본 루트질 방법을 반죽을 해서 겨우 풀었다. 아무튼 솔브 수 차이 냈으니 좋은 거 아닐까?

 

 

대회가 끝난 후 ystaeyoon113님이 연세대 모르고리즘 카르텔을 모았고, 졸업 기념으로 밥을 사주셨다. 다음 날 졸업 사진?을 찍으신다는 것 같았는데, 아무튼 나를 SUAPC에 초대해주시고 밥도 사주시고 여러 조언도 듣고 해서 다음 날에도 찾아가고 싶었으나 아쉽게도 새터 일정으로 못 가게 되었다. ㄱ-

 

추가했으면 하는 SUAPC 도중의 재미있는 사건이 있다면 댓글이나 디스코드 DM으로 자유롭게 알려주시길 바랍니다. 빨리 올리고 자고 싶어서 대충 쓰고 갑니다.