SUAPC 2026 Winter 출제/검수 후기

0. 들어가며

출제한 문제인 SUAPC E번 가지가지

 

한창 문제 출제/검수 조건을 달성하고 여러가지 문제를 구상하고 있을 때, SUAPC 2026 Winter의 콜포테가 열렸습니다. 3문제 정도 지원했고, 감사하게도 가장 출제하고 싶던 1문제가 선정되어 출제진으로 활동할 수 있었습니다. 동시에 출제 자격 B도 달성하고 있는 상태였기 때문에, 몇몇 문제들은 검수도 했습니다. 

 

1. '가지가지'에 대하여

이전에 룩 vs 폰 문제를 출제했을 때 많은 피드백을 받았었습니다.. 그래서 좋은 문제를 구성하기 위해 더 많이 노력했던 것 같습니다.

가지가지는 PS를 시작하고 처음으로 구상한 문제였습니다. 구상할 당시에는 해구성 없이 배치 가능 여부만 출력하는 문제였는데, N*N + N*(M-N) 으로 나누어 해구성하는 방법을 발견해내서 지금의 가지가지가 되었습니다. 하지만 에디토리얼은 다른 해구성 방법으로 설명했습니다. 검수진 분들이 더 쉬운 풀이로 풀어주셨기 때문입니다. 검수의 중요성을 다시한번 느꼈습니다. 문제가 더 잘 다듬어지고 완성되어가는 모습을 보는게 뿌듯했습니다.

 

에디토리얼 마지막 페이지

아쉽게도 온사이트에 직접 가진 못해서, Challenge까지 해설할 수는 없었습니다. 혹시 궁금한 분이 계실까봐 짧게 정리해보았습니다:

$N \times M \times K$ 격자 공간에서 모든 slice에 꼭지가 홀수개 존재해야하므로, 2차원일때와 같은 논리로 N,M,K의 parity가 모두 같아야 해구성이 가능함을 알 수 있습니다. 이는 차수가 늘어나도 항상 적용됩니다.

해구성 방법 또한 비슷합니다. $N \times N \times N$을 먼저 구성합니다. $(1,1,1),(2,2,2),(3,3,3) ... (N,N,N)$에 꼭지가 오도록 구성하면, 남은 공간에서 고려해야할 부분은 $(M-N) \times (K-N)$ 크기의 격자판이 됩니다. 이후에는 기존 풀이처럼 진행하면 됩니다. 예외적으로 $3 \times 3 \times 3$은 직접 구성해야합니다.

2. 문제 검수에 대하여

대회 기준으로 A, C, D, J, K, M, PA, PB, PC, PD번을 검수했습니다. 나머지는 풀지 못했습니다. ㅠㅠ

A. 유림이와 하람이의 두쫀쿠 대작전

간단한 사칙연산 문제입니다. 두쫀쿠 원가가 2000원밖에 안된다는 진실을 알게 해줬습니다... 그리고 일러스트가 귀여워요.

C. 숫자 놀이 3

진법에 익숙치 않아서 살짝 고민했던 문제입니다. 1부터 역으로 추적해서 적당한 조건의 dfs를 돌며 가능한 수를 모두 찾고, 이후 정렬을 하고 앞에서부터 k개를 출력하면 됩니다. 정해는 pq로 k개 까지 관리하는거지만, dfs로 전부 찾아도 시간내에 든다는걸 증명하는 난이도를 생각하면 난이도는 비슷합니다.

D. Yet Another Binary Problem

마음에 드는 문제입니다. 수열에서 1을 +1, 0을 -1로 생각하고 누적합을 해봅시다. 이후 Suffix min/max도 구해놓으면, 지금 이 쿼리를 썼을 때 남은 쿼리 개수로 이후에 나올 0/1을 모두 지울 수 있는가?를 판단할 수 있게 됩니다. 1번 쿼리는 사용시 이후 Suffix min을 1 증가시키고, 2번 쿼리는 사용시 이후 Suffix max를 1 감소 시키기 때문에 그렇습니다. 산 깎기

이후에 누적합 안쓰고 이상한 그리디로 뚫을 수 있지 않을까 해서 여러개를 내봤는데, 전부 막혀버렸습니다.

J. 지하철! 지하철! 몇호선? 몇호선?

뭔가 선공 필승법이 있을거 같아서 오래 고민했는데, 결국은 홀짝인 문제였습니다. n이 짝수라면 (1,2),(3,4),...(n-1,n) 이렇게 묶고 나서, 후공은 선공이 말한 수와 같은 묶음의 수를 말하기만 하면 항상 짝수개씩 소모되기 때문에 후공이 이깁니다. n이 홀수라면 선공이 1을 말하고, 선후공이 바뀐 상황에서 n이 짝수인 게임을 하게 되어 선공이 이깁니다.

K. MC 히페리온

좋은 문제입니다. 문제를 처음 풀때는 제약 조건을 잘못 읽어서 1번 쿼리를 루트부터 타고 들어가서 $O(|S|)$에 처리하는 풀이를 냈었습니다. 근데 이후 검수노트를 보니, 정해가 트라이+ett+세그로 되어있어서 뭔가 잘못됨을 느꼈습니다. 데이터를 보니 문자열 길이를 최대로 하고 1번 쿼리 개수도 최대로 하는 데이터가 없었어서 추가했습니다. 별해로 정렬 + 이탐 레전드 똑붙 풀이가 있는데 어떻게 이런 생각을 하지

M. 괄호 문자열 카드

만만하게 봤다가 큰 코 다친 문제입니다. ()는 그 자체로 올바른 괄호 문자열이라 항상 배치가 가능합니다. ((, ))를 먼저 배치하고, 이후에 남은건 (, )으로 짝지어줍시다. 열고 닫는 괄호가 1쌍이라도 있다면 )(도 모두 사용할 수 있습니다. 진짜 깐깐하게 케웍을 해야해서 틀리기 너무 좋은 문제에요.

PA. SUAPC 2025 Summer

SUAPC의 유서깊은 스코어보드 문제입니다. 원래는 23팀 전부에 대해 구해야했었는데, 내부 조정을 거쳐 상위 10팀에 대해서만 구하는걸로 제한이 줄어들었습니다. OCR이 도입되면 편할거 같다는 생각을 했습니다.

PB. 선물 게임

식정리를 간단하게 못해서 어렵게 푼 문제입니다. 우선 단순히 생각해봐도 선공이 후공보다 유리하기 때문에, 일부러 턴을 상대에게 넘기는 변칙적인 플레이는 손해임을 알 수 있습니다. i번째 열까지 진행했을 때 B가 선물을 찾을 확률을 $\frac{a_{i}}{b_{i}}$ 라고 합시다. i번째 열을 기준으로 선공이 선물을 찾을 확률은 $\frac{n- \lfloor\frac{n}{2}\rfloor}{n}$ 이란걸 이용해서 식을 정리하면, $a_{m} = a_{1} + \lfloor\frac{n}{2}\rfloor (n + n^{2} + \cdots + n^{m-1})$ 이고 $b_{m} = n^{m}$ 이 됩니다. 유클리드 호제법으로 $a_{m}$과 $b_{m}$이 서로소임을 증명할 수 있으므로, 유일하게 문제가 되는 $n + n^{2} + \cdots + n^{m-1}$ 부분만 분할정복으로 해결하면 됩니다.

정해는 이 풀이보다 더 깔끔합니다.

PC. 괴수의 꽃노래

쉽고 재밌는 문제입니다. "매 구역에서 이전까지 본 모든 꽃 보다 꽃잎의 수가 적거나, 이전까지 본 모든 꽃 보다 꽃잎의 수가 많도록 씨앗을 심었다." 라는 조건은, 1번 구역의 번호 $A_{1}$을 기준으로 수가 커지는 경로와 작아지는 경로만 존재한다는걸 의미합니다. 즉 N번 구역에서 1번 구역을 찍고 왕복해서 돌아오면서 1부터 N까지(혹은 N부터 1까지) 차례대로 만날 수 있게 됩니다. 성대의 구조를 바꿀때 드는 비용을 최소화하려면 오름차순 or 내림차순으로 방문하는게 최적이기 때문에 이 두가지 관찰을 합치면 넉넉하게 문제를 해결할 수 있게 됩니다.

PD. 멘헤라

제한이 $10^{16}$이여야만 하는 문제입니다! N이 충분히 크면 순하리 레몬진 9도를 계속 마쳐서 취기를 빠르게 올리는게 최선임을 짐작할 수 있습니다. 적당히 작은 N은 bfs로 찾아주면 됩니다. '적당히'의 정확한 boundary를 증명하려면 어렵지만, bfs가 안터지는 선에서 최대한 많은 N을 bfs로 커버쳐주면 되겠습니다. 참고로 정확한 boundary는 60.5입니다.

이 문제가 제한이 $10^{16}$이여야만 하는 이유는, 검수할 때 파이썬으로 풀었다가 float 정밀도 이슈로 맞왜틀을 당한게 괘씸교육적이기 때문입니다. 큰 수라고 해서 조심하지 않고 무작정 파이썬을 쓰는것에 대한 고찰을 제공하는 좋은 문제입니다.

3. 마치며

평소에도 대학에서의 PS생활을 동경하고 있었는데, 대회 이후로 더욱 동경하게 될 것 같습니다. SUAPC 흥해라~