UCPC 2026 운영 후기

이번에 UCPC 2026의 출제 총괄을 맡게 되어서 대회 운영에 참여하게 되었다. 어떠한 생각으로 문제들을 뽑았을지 알아보자. 문제 풀이에 대한 스포가 좀 있을 수 있다.

 

Call for tasks

이번에 UCPC call for tasks에는 100문제 가량이 들어왔다. 안 좋은 문제들이 조금 섞여있다고 해도 정말 많은 양의 문제들이 들어왔기 때문에, 문제들을 정렬하고 뽑는데 어려움을 느꼈다. 이때 다음과 같은 생각을 했다

• 좋은 문자열/기하/플로우가 있으면 일단 뽑음
• 각 난이도 별로 적당한 양의 문제를 뽑음
• 구현이 너무 어렵지 않게 함
• 좋은 문제들이 그냥 많으니까 14문제를 뽑자

그리고 이와 더불어 내가 ad-hoc한 수학맛 문제들을 좋아하는 것이 영향을 주었다. 그래서 일단 처음에는 아래와 같은 문제들을 뽑았다.

• New Game Start: OI 자료구조 문제인데, dp값의 차이가 convex하다는 하늘에서 떨어지는 관찰을 한 후에 segment tree에 잘 섞어서 비비는 것이 인상적이다
• Yet another binary Problem: 매칭 문제가 하늘에서 떨어지는 환원으로 그리디 문제가 된다. 환원이 말이 안 된다. 뽑지 않을 수가 없음...
• Pandastic: 사실 처음에 call for tasks를 받을 때에는, 필요충분조건을 귀납법으로 증명했는데, 귀납법이 홀의 정리와 관련된 식으로 적혀있어서 직관을 이해하지 못했다. 사실 식정리는 필요 없고, 스틱을 끝까지 넘겨서 게임을 끝내는 대신 아무것도 못 먹는 판다를 먹는다는 발상의 전환만 하면 인생이 편해지는 문제이다. 쉬운 것 같은데 내가 오래 절었으니 조금은 어려운 문제라고 평가했다.

그 외에 국밥 문제들도 뽑았다.

• 악령 퇴치: 처음에는 dnc를 비비는 D3으로 들어왔지만, 그냥 min/max segment tree를 잘 사용하면 된다는 결론에 도달했다. 원래는 실제 위치까지 찾는 문제였지만, 구현량만 늘리는 것 같아서 제거를 요청했고, 감사하게도 출제자인 functionx님이 받아들여주셨다.
• 지그재그: 간단한 관찰을 하나만 해주면 예쁜 식으로 변하고, 자료구조를 잘 비벼주면 풀린다

기하와 문자열 문제도 뽑았다.

• vector rails: 처음에 문제를 풀 때 몇 개의 벡터만 사용해서 도달할 것이다 같은 가설들을 세우면서 생각했는데, 잘 생각해보니까 비용 1로 이동할 수 있는 최대 거리를 생각해보니 convex hull만 사용해서 깔끔하게 풀렸다.
• 무한 문자열: 내가 만든 문제이다. 나중에 출제 글로 따로 이야기하겠지만, AB < BA와 A^inf < B^inf가 동치인 것이 생각보다 재미있는 아이디어라고 생각했다. SA + LCP는 국밥이니까 조금 얹어도 괜찮을 것 같다고 생각했다.

나머지 문제들에 대한 인상은 다음과 같았다.

• Shift: 애드혹 문제로, 관찰을 차근차근 해주면 쉽게 풀 수 있는 문제이다. 다만, 관찰을 차근차근 하는 것이 쉽지 않아서, 나도 선제할 때 풀이를 까고 풀었다. 하지만 각 관찰들이 하늘에서 떨어지는 수준은 아니라서, 많은 사람들은 아니더라도 최상위권은 무난하게 풀 수 있을 것으로 예상했다.
• 배수: 구간들이 laminar하다는 것의 증명이 꽤 어려웠던 것으로 기억한다. 그래서 정말 어려운 문제라고 생각했고, 후반부 문제로 선정했다.
• 갑천 자전거길: binary search에 약간의 변형을 준 재미있는 문제이다. 모두가 풀 수 있을 것으로 예상했다.
• 11 싫어 수: 문제는 쉽지만 소재가 흔하지는 않다. 좋은 쉬운 문제라는 생각을 했다.
• 아침약: DP 문제인데, 단순히 구간을 DP로 잡는게 아니라 길이가 정해지면 구간의 종류가 3가지 이하라는 사실을 이용한다. 흔한 DP가 아니라서 좋다고 생각했다. 나중에 알아보니 양끝에 있는 약봉지가 같으면 그 다음 약봉지를 보면 어떤 약봉지를 뗄지 결정할 수 있다는 사실을 깨달았다. 풀이도 여러 가지이고 좋은 것 같다.
• C4ESAR: 괄호문자열 국밥 문제이다. 같이 선제에 참여한 hibye1217님의 문제이다. 내가 못 풀어서 좋은 문제라고 생각하고 냈다. (정확히는 괄호문자열 매칭까지는 생각했는데 트리 dp는 생각을 못 했다... 왜 못함?) 실제로도 좋은 문제같다.
• 비상 물자 보급: 앳코더맛 문제인데, 복잡해보이는 값을 기댓값의 선형성으로 잘 쪼개는 문제이다. 원래는 시작점도 N가지로 주어졌는데, 아이디어는 변하지 않고 구현만 늘어나는 것 같아서 시작점을 고정했다.

다 좋은 문제들이었고, 예상 난이도는 아래와 같았다.

D5 = 21이다

상인은 원래 본선 문제로 뽑았지만, 작은 treewidth를 가진 그래프에서 dp를 하는 풀이가 너무 자명하고 구현이 복잡하다는 이유와 뽑고 보니까 문제들의 난이도가 너무 어려운 것 같다는 이유로 예선의 갑천 자전거길 문제와 swap되었다.

난이도 예측에 실패한 문제들로는 Multiple, 무한문자열이 있다.

• 무한문자열: 그냥 내가 출제해서 (...) 그런 거 같다. A^inf < B^inf -> AB < BA 부분이 어렵기는 하지만, 예전에 큰 수 만들기 문제를 풀 때 AB < BA에서 A^inf < B^inf를 떠올려놓고 증명을 못했던 기억이 있어서 쉽다고 느꼈던 것 같다.
• Multiple: 그냥 사람들이 고능하다. Laminar하다는 관찰이 쉽나...? 사람들이 찍어 맞추는 것을 생각보다 잘하는 것 같다.

아무튼 그래서 14문제 셋이 되었다.

검수 및 테스팅

예상 난이도

만들고 보니까 너무 대회가 쉬운 것 같았다... 최상위권이 다이아 4까지 적당히 푼다는 것을 생각하면, 올솔 - 1 정도는 여러 팀 나올 줄 알았다. 실제로 테스팅 중에 박상훈님과 윤교준님의 2인팀이 4시간 안에 13솔을 했다. 어려워서 아무도 못 푸는 대회보다는 쉬운 대회가 낫고, 올솔이 여럿 나오지는 않을테니 괜찮을 거라고 생각했다.

실제 대회

아쉬운 일들이 여럿 벌어졌다.

• 지그재그, 악령 퇴치가 생각보다 너무 국밥이어서 다들 티어에 비해 잘 풀었다. 적당히 어려운 P1 정도의 국밥 포지션일 것이라는 나의 예상을 좀 빗나갔다.
• Vector Rails는 구현이 어려워서 잘 안 풀렸다. 다시 생각해보니까 convex hull을 잡기만 하면 되는게 아니라, convex hull이 직선인지, 점인지, 2차원 도형인지 등등을 따져야 되는 것 같다. 내가 판단을 잘못했던 부분 중 하나인 것 같다.
• 갑천 자전거길 문제가 너무 안 풀렸다. 이건 좀 아쉬운데, Pandastic과 Multiple이 빠르게 풀리기 시작하면서 참가자들이 쉬운 문제인 갑천 자전거길을 안 보고 Pandastic과 Multiple을 보기 시작했다. 실제로 UCPC 후기들을 읽어보면, 갑천 자전거길의 풀이가 매우 쉬운데 왜 아무도 안 풀었지? 같은 말들이 적혀있다. 좀 아쉽게 생각하고, 운이 안 따라줬던 것 같다.
• 무한 문자열은 AB < BA 와 A^inf < B^inf가 동치인 것이 well-known이라고 주장되었다. 테스터들 3팀 중 무려 2팀이 알고 있었기 때문이다. 그래서 대회중에서도 많이 풀릴 줄 알았는데, 그냥 고인물들이 테스팅을 해서 그랬던 것 같다. 그리고 Q 범위 100만을 줘서 로그제곱을 생각조차 하지 못하게 하고 싶었지만, TL을 6초나 주는 바람에 여러 팀이 로그제곱 풀이에 빠져버렸다. 6초가 로그와 로그제곱 풀이를 정확하게 가르는 선이었는데, 로그 풀이를 조금 희생하더라도 TL을 4초로 줄여야 했나 생각이 든다...

이러한 일들로 가운데 난이도가 비어버렸고, 참가자들은 6솔을 한 이후에 문제를 푸는 속도가 급격하게 느려졌다. 동시에 G번은 기하라서 WA가 많이 나오고, H와 F번의 문제 특성상 잘못된 풀이로 쉽게 빠질 수 있다는 점, J번에서 로그제곱을 짜는 참가자들이 많다는 이유로 스코어보드가 빨갛게 물들어버렸다. 세팅을 조금 더 잘할 수 있었을 것 같다는 후회가 들었다.

스코어보드

반성할 점

• 풀이의 복잡도와 구현의 복잡도는 별개인 것 같다. vector rails를 직접 구현해봤으면 구현이 어렵다는 것을 알 수 있었을텐데, 직접 구현을 하지 않으니 크게 경각심을 못 느꼈다. "모든 점에 도달할 수 있다" 같은 조건을 주면 convex hull이 항상 2차원 도형이 되면서 구현이 쉬워졌을 것 같은데, 아쉬움이 든다.
• TL 세팅의 면에서 참가자들에게 보이는 것도 중요하다는 생각이 든다. J번에 Q를 백만을 줬으면 괜찮을 줄 알았지만, 사실 그러지 않았다. 백만에 로그제곱이면 정해라는 생각은 안 들지만 뚫을만하다는 생각을 할 수 있는 것 같다.

잘한 점

• 각각의 문제들이 좋았다. 사실 UCPC는 대회의 성격도 있지만, 좋은 문제를 두고두고 풀 수 있는 좋은 문제 창고라는 점도 있다. New game start, Yet another binary problem 등의 어썸한 문제를 보면서 사람들이 재미있게 풀 수 있을 것이다.
• 최상위권에게는 재미있는 대회였다는 생각이 든다. 실제로 11~12솔을 한 팀들은 문제를 재미있게 푼 것 같다.
• 6솔을 못 하는 하위권에게도 재미있는 대회였을 것 같다. 실제로 쉬운 문제들이 꽤 많았다고, 0솔팀이 없었다.

출제 총괄 후기

좋은 문제들을 많이 볼 수 있어서 재미있었다. 여러 문제들의 검수 현황을 관리하는 것과 대회를 조화롭게 만드는 것은 나에게 어려운 일인 것 같다. (준비하다 보면 뭔가 하나씩 까먹는 것 같다...) 대회를 준비해주신 출제자/검수자들, 그리고 오프라인 대회가 굴러갈 수 있게 해주신 전대프연 임원진들에게 감사하다. 앞으로는 대회 세팅보다는 문제 출제자로서 재미있는 문제들을 만드려고 노력할 것이다.

 

그리고 내년에는 UCPC에 참가해서 상품을 날먹할 예정이다. UCPC 2027 let's go!