2026 ICPC Seoul Regional 예선 후기

멤버

지난 2026 Centroid Cup의 멤버 그대로 출전했습니다.

저희 팀은 수학이 강한 linminyang과 구현에 강한 저, 그리고 올라운더인 waaang으로 이루어진 팀입니다.

대회 이전

Centroid Cup때 제가 구현을 도맡아 했었는데, 생각보다 효율이 좋지 않다는 것을 느꼈습니다. 제가 구현을 전담하기보단 waaang과 제가 때에 따라 구현을 나눠 하는 방식이 더 나을 것이라 생각했고, 팀연습에 적용해 보았습니다.

linminyang은 수학과 직관, 발상이 강점이므로 적당히 어려운 문제를 잡고, 저와 waaang이 나머지 문제를 훑으면서 적당한 문제를 잡습니다.

제일 먼저 발상이 떠오른 문제에 나머지 둘 중 한명이 달라붙어 적당히 검증한 후 waaang이나 제가 구현하는 방식으로 진행했습니다.

대회 당일

전날부터 갑자기 김치찌개가 너무 땡겨서 11시에 정릉시장에 있는 청년밥상문간에서 다같이 김치찌개를 먹고 학교로 가서 세팅을 하기로 했습니다.

근데 대회 당일날 마노사바 콘테스트를 9시 50분에 레지해놓고 9시에 레지했다고 착각하는 바람에 조금 늦게 출발했습니다ㅠ

네이버 지도가 10분 늦는다길래 다들 천천히 나오라고 했는데 생각보다 버스가 빨리 가서 오히려 10분 일찍 도착했습니다.

waaang을 기다리는 동안 linminyang이 도착해서 같이 건물로 들어갔는데 벌써 3팀이나 줄을 서고 있었습니다.

도착한 waaang이 줄을 보고 기겁했고, 더 기다리기도 좀 애매한 것 같아서 그냥 학교로 돌아가서 학식을 먹었습니다. 내 김찌가ㅠㅠㅠㅠㅠ

밥을 먹고 나서 공학관으로 이동해서 컴퓨터를 켜고 VSCode와 clangd 등을 세팅했고, 별다른 문제는 없었습니다.

대회

쉬운 몇 개의 문제가 한국어로 나온다는 걸 들었기에 대회가 시작하자 마자 일단 한국어 문제를 빠르게 찾았습니다.

A, G, K번이 한국어였고, linminyang이 K를 보자마자 풀이를 발상해냈습니다.

linminyang: "이거 두 제곱수의 합인지 검사하면 됨"

skuru: "?그게왜됨"

linminyang: "?자명하잖아"

하지만 서로 소통에 이슈가 발생해서 일단 다음으로 넘겼습니다.

그동안 waaang이 G번 풀이를 떠올려서 제게 설명해 주었습니다.

어떻게 구현해야 할지 자세히 설명해줘서 파이썬으로 막힘없이 구현했고, 덕분에 G번 First Solve를 하게 되었습니다.

야호

그 다음 waaang은 A번을 보러 갔고, 저는 다시 linminyang의 K번 설명을 들었습니다.

그냥 $n$이 두 제곱수의 합이면 YES라길래 저는 아무 생각 없이 그대로 구현했고, WA를 받았습니다.

진짜 곧이곧대로 구현해서 $n$이 제곱수인 경우를 빠뜨린 것이었고, 고쳐서 AC를 받았습니다.

대회가 끝나고 나서야 기울어진 정사각형의 한 변을 직각삼각형의 빗변으로 보고 피타고라스 정리를 써서 해결할 수 있다는 걸 알았습니다.

마지막으로 남은 한국어 문제인 A번을 보고 제가 좌표 압축 + 세그먼트 트리 풀이를 떠올렸지만 너무 오버킬인 것 같고 오래 걸릴듯해서 waaang에게 넘겨두고 저는 C번을 보고 있었습니다.

깊고 깊은 고민 끝에 waaang이 발상한 아름다운 풀이를 소개해 드리겠습니다. 제가이거때문에후기쓰기로결정함ㄹㅇ

두 개의 트리 집합 $L$, $R$을 준비합니다.

h-index를 $H$라 합시다.

먼저 $c_i \leq H$인 경우 $c_i$를 $L$에, 아니면 $R$에 넣습니다.

쿼리에서 $c_k$가 $c_k + x$로 업데이트되는 경우 위 규칙에 맞게 집합에서 $c_k$를 제거하고 $c_k + x$를 다시 집어넣습니다.

이때 $|R| \geq H + 1$을 만족한다면 그렇지 않을 때 까지 $H = H + 1$로 업데이트하고 $R$에서 업데이트된 $H$보다 작거나 같은 원소를 모두 $L$로 옮기는 것을 반복합니다.

쿼리는 최대 $q$번 주어지므로 집합 $R$에 삽입은 최대 $n + q$번 일어납니다. 따라서 집합 $R$에서 $L$로의 이동은 최대 $n + q$번만 일어나므로 시간 복잡도 $O((n + q)\log n)$에 해결할 수 있습니다.

중간에 구현 이슈가 있었는지 TLE를 두 번 받고 AC를 받았습니다.

waaang이 A를 푸는 도중 저와 linminyang는 남은 문제 중 적당해보이는 문제를 살펴봤고, H번이 뭔가 좀 할만해 보여서 열심히 고민해 보았습니다.

특정 risk 이하가 되도록 보안 요원을 배치하는 것이 가능한지는 $O(n)$에 알 수 있으므로 이를 이용해 이분 탐색을 하는 풀이를 linminyang과 같이 떠올려 후다닥 구현하고 AC를 받았습니다.

중간에 long long을 안 써서 WA를 한 번 받았습니다. 얘들아미안해

H번을 풀고 나서 남은 문제 중 linminyang이 C번의 해석을 부탁해서 같이 지문을 읽었습니다.

볼록 껍질이랑 뭔 관련인지는 잘 모르겠고 와닿지 않는 정의라서 어떻게 풀어야 할지 감이 오지 않았습니다.

linminyang: "이거 그냥 $\mathcal H(S) = I(S)$ 아님?"

skuru: "어?"

그러던 도중 linminyang이 좋은 발상을 해냈고 $I(S) \in \mathcal H(S)$임이 자명하기에 답이라고 생각하고 열심히 구현해서 WA를 받았습니다.

생각해보니 최단거리에서 새로 추가된 $S$에 없던 정점의 경우도 생각해줘야 하기에 $I(I(I(I(\dots I(S)))))$를 구하면 된다는 것을 제가 빠르게 깨달았고, 그대로 구현해서 AC를 받았습니다.

대회 이후

대회가 끝나고 선배들이랑 같이 피자집으로 향했습니다.

며칠이 지나고 나서 디스코드에서 멘션을 받았습니다.

놀랍게도 저희 동아리 KPSC에서 출전한 세 팀 모두 본선에 진출하게 되었습니다! 야호

이번 대회는 정말 재밌게 즐겼던 것 같은데 결과도 좋아서 너무 행복했습니다.

본선에 진출해서는 더 재밌게 즐겨보고 싶습니다. 문제 풀면 풍선을 달아준다는 말을 어디서 들은 것 같은데 너무 기대되네용ㅎㅎㅎㅎㅎ