2022 SUAPC Summer 출제 후기

이번 여름 4연속으로 있는 대회 운영의 2번째 타자인 SUAPC가 종료되었다. 저번 DKSH 대회 후기에는 3연속이라고 썼었는데, 그 사이 하나가 늘었다. 꽤 긴 시간동안 준비했기에, 후기를 좀 더 상세히 써 보려 한다.

 

대회 링크 : https://www.acmicpc.net/category/detail/3180

 

발단

이후 더 자세히 말하겠지만, PPC와 다른 대회들 준비를 위해 2월부터 만들어 둔 문제들이 조금 있었다. 하지만 교내대회에 쓰기 부적합하거나, 비슷한 문제가 큐에 있어 기각된 문제들이 꽤 생겨버렸다. 이를 어디 쓸지 고민하던 중, 내가 알기로는 유이하게 Call for Task를 받는 대회인 SUAPC에 문제들을 냈다. 총 6개 정도를 냈는데, 3개는 전형적이라는 이유로, 1개는 풀이가 틀렸다는 이유로, 1개는 비슷한 유형의 문제가 출제될 예정이라 거절되고 1개만이 출제되게 되었다. 해당 문제도 솔직히 좀 노잼이라 안뽑힐 줄 알았는데, 특정 알고리즘의 튜토리얼 문제 개념으로 합격한 것 같다. 막차를 잘 탔다고 생각한다.

 

과정

어찌됐던 출제진으로 선정되었으니 대회 운영용 Discord에 들어갔다. 어디서 많이 본 핸들의 출제 & 운영 & 검수진 분들이 있어서 신기했다. 이 시점에서는 PPC 운영을 본격적으로 시작하기 전이었기 때문에, 여기서의 경험이 PPC 운영에도 큰 도움이 되었다. 이후 약 2달간 데이터 제작 & 검수가 이루어졌던 것 같다. 순탄하게 준비된 문제들도 있고, 크고 작은 사건을 거친 문제들도 있었다. 자세한 내용은 아래 문제별 후기에서 다루도록 하겠다.

 

문제별 후기

대회 준비 기간이 길기도 했고, 할 것도 없었기 때문에 전 문제를 검수했다. 

 

A. 수 맞히기 게임 / 출제자 : tlsdydaud1

 

기댓값을 이용해 점화식을 잘 세운 후, 여러 DP 문제에서 등장하는 테크닉들을 조금 이용하면 해결할 수 있는 문제이다. 큰 틀은 바뀌지 않았지만, 메모이제이션을 하지 않는 풀이를 막기 위해 제한과 세팅이 몇 번 바뀌었던 것으로 기억한다. 검수진들 사이에서는 티어가 평균 G3 정도로 매겨졌는데 막상 본 대회에 들어가니 솔브 팀 수가 J, L, M보다 현저히 작고 H와 비슷한 4팀이라는 결과라서 모두 약간 당황했다. 그래도 오픈 컨테스트에서는 J, L, M보다 확실히 많이 풀렸다. 스코어보드의 중요성을 다시 한 번 체감할 수 있었다. 티어는 예상보다 살짝 높은 G2에 박혔다.

 

B. 내비게이션 / 출제자 : lky7674

 

출제 의도가 후원사용 브론즈 구현 문제였고, 그에 알맞은 문제가 나왔다. 출제와 검수 모두 무난하게 이루어져서 크게 할 말이 없다..

 

C. 패스 / 출제자 : tlsdydaud1

 

창의력과 꼼꼼함을 요구하는 애드혹 문제이다. 창의력을 통해 구성법을 찾고, 꼼꼼함을 통해 불가능한 경우를 잘 쳐내면 된다. 두 부분의 난이도는 비슷한 것 같다. 대회 중에는 N=1인 경우를 처리하지 않아 100%에서 틀리는 분들이 꽤 보였다.

 

D. 포탈 / 출제자 : tlsdydaud1

 

이 셋의 대장 문제를 당당히 차지한 D번이다. 원래 표에는 P1~2정도로 적혀 있었고 대장 문제도 따로 있었지만, 이 문제가 생각보다 어렵다는 점이 밝혀지고 + 기존의 대장 문제가 없어지면서 자연히 그 자리를 차지하였다. 이 셋의 다른 Challenging 난이도 문제들과는 다르게, 요구하는 알고리즘은 쉬운 편에 속한다. 하지만 경우를 분석하는 것과 그 정당성을 증명하는 과정이 매우 길고 귀찮고 복잡하다. 그래서 나도 검수를 끝까지 미루다 대회 전날 겨우 이를 악물고 풀었다. 예상대로, 본 대회에서는 0솔이었고 오픈 컨테스트에서도 아쉽게 0솔로 마쳤다. 사실 딱 켰을때 풀고 싶어지는 문제 유형은 아니라.. 이대로 고립되는 것이 아닐지 살짝 걱정이긴 하다ㅜㅜ 많이 풀어주세요..

 

E. 1-3 트리 / 출제자 : tlsdydaud1

 

이 셋에서 tlsdydaud1님이 출제하신 4번째 문제이다. tlsdydaud1님의 문제가 전체적으로 코포같다는 생각을 많이 했는데, 특히 이 문제가 정말 코포스럽다고 생각했다. 대충 Div. 2 D쯤에 있을 것 같이 생긴 문제였다. D라고 한 만큼 난이도는 쉽지 않다. "대충 이런 식"으로 될 것 같다는 과정을 정확히 정의한 후 구현하는 것이 중요한 문제라고 생각한다. YES / NO 문제다보니 뚫릴 가능성이 꽤 있어 중간에 멀티테케 문제로 바뀌었는데, 덕분에 데이터가 굉장히 강해진 것 같았다.

 

F. 차의 개수 / 출제자 : heeda0528

 

재밌고 쉬운 구성적 문제이다. 구성적 문제가 쉽기 쉽지 않은데, 나름 유니크한 위치의 문제라고 생각한다. 답을 떠올리는 것은 어렵지 않고, 정당성 증명도 재밌어서 이런 유형을 연습하기 좋은 문제인 것 같다. 여담으로, 내가 만든 별해가 있는데 이게 문제 범위 안에서는 Proof by AC가 되지만 증명을 하지 못했다. 이 풀이는 현재의 N 범위에서 X의 범위를 \(10^6\) 정도로 줄일 수 있다. 증명이 된다면 차의 개수 2로 출제하는 것도 재밌을 것 같다. 궁금하신 분들은 풀고 제 코드를 읽어주세요~

 

G. AND, OR, XOR / 출제자 : leo020630

 

내가 낸 문제이다. PPC 큐에 들어있던 원본 버전은 이름도 '양산형 수열 문제'이고, AND밖에 없는 버전이었는데 너무 성의가 없어보여서 일단 OR, XOR을 추가한 후 풀이를 만들어서 냈다. 문제는 요즘 여러 대회에 등장하며 핫하다면 핫한 SOS DP 문제이다. 재미있는 문제는 아니고, 튜토리얼 용으로는 괜찮은 문제인 것 같다. SOS DP를 조금 변형하면 되는데, 끝나고 찾아보니 이걸 Fast Mobius Transform이라고 부르는 것 같다. 또한, AC 코드들 중에서는 AND, OR, XOR Convolution을 이용한 코드도 있었다. 검수 중에 나오지 않았던 풀이라 신기했다. 공부할 게 늘었다.. 여담으로, 문제가 만만하게 생겨서인지 \(O(N^2)\) 코드들이 대회중에 꽤 제출되었다. 마음이 아팠다ㅜ

 

H. 역삼역 / 출제자 : shjohw12

 

원래 지문은 그냥 문제 설명만 있었는데, 출제 기간 중 팰린드롬이 주요 소재로 쓰이는 드라마가 흥하면서 이 문제와 J번이 관련 내용으로 지문이 수정되었다. 풀이는 팰린드롬이 없는 버전의 문제를 해결하는 법을 알고, 팰린드롬이니까 우선 매내처를 박고 잘 비비다보면 찾을 수 있다. 여담으로, H번 자리는 원래 대장 문제가 있었으나, 쉬운 풀이가 발견되면서 + 유사한 문제가 다른 대회 기출에 있어서 삭제되었다. 해당 문제도 검수하려고 공부를 꽤 했었기 때문에 삭제된 것이 살짝 아쉬웠다..

 

I. 딸기와 토마토 / 출제자 : heeda0528

 

이 문제도 원래는 '타일 교차'라는 제목의 밋밋한 제목이었는데, 출제자분이 스토리를 넣으면서 제목이 변경되었다. 그 과정에서 내 닉네임이 지문에 들어가게 되었다. 닉네임을 넣을지 실명을 넣을지 (어차피 별 차이도 없지만..) 고민했지만, 닉네임이 좀 더 컨셉에 맞는 것 같아 닉네임으로 결정하였다. 문제는 지문 이해를 잘 해야 하는 case work 문제이다. 유독 질문이 많이 들어왔던 것으로 기억하고, 억까를 당한 팀들도 많았다. 개인적으로 팀 대회에 이런 구현 문제가 하나쯤은 있는 것이 좋다고 생각해 관전자 입장에서는 재미있었다.

 

J. 김밥 / 출제자 : shjohw12

 

뭔가 스위핑처럼 생겼으니 이 문제를 풀기 유리한 조건이 무엇인지 생각한 후, 해당 조건으로 정렬해준 후 적절한 방법으로 문제를 해결하면 된다. 정해는 imos법으로 처리한다고 하는데, 나는 좌표압축 + 펜윅을 썼다. 어차피 시간 복잡도가 정렬에 지배적이니 세그 풀이를 막을 순 없었다. 출제자분은 약간 슬퍼하시는 것 같다..

 

K. 줄 세우기 / 출제자 : chansol

 

이번 대회에 출제된 문제들 중 풀이가 가장 다양한 문제이다. 오프라인 풀이는 연결 리스트 or (스몰 투 라지 and 덱)과 누적합을 잘 사용해주면 되고, UF를 잘 쓰면 온라인으로도 풀 수 있는 것 같다. 구현이 꽤 있어서인지 본 대회와 오픈 모두에서 솔브수는 적은 편에 속했다. 현재 솔브드 티어도 다이아 문제들 다음으로 어려운 P3이다.

 

L. 피라미드 / 출제자 : pjshwa

 

재미있는 애드혹 문제이다. 우선 피라미드의 구조에 대한 관찰을 했다면, https://www.acmicpc.net/problem/2450, https://www.acmicpc.net/problem/18179 등과 비슷한 방법으로 최소 횟수를 구해줄 수 있다. 전자의 과정이 후자보다는 쉬운 것 같다. 후자의 과정은 그래프와 간선 형태로 생각하면 보다 직관적으로 볼 수 있다. 티어는 G1~P5 사이에서 왔다갔다 하는 것 같다.

 

M. My뷰 꾸미기 / 출제자 : pjshwa

 

멋진 조합론 문제이다. Naive한 형태의 식은 금방 찾을 수 있는데, 이를 정리하는 것이 미리 알고 있지 않다면 꽤 어려운 것 같다. 나는 대충 nCr 성질을 열심히 구글링해 비슷하게 생긴 식을 찾을 수 있었다. 이 문제 역시 기존 지문은 다른 컨셉이었는데, 후원사 문제로 바뀌면서 지문과 제목이 변경되었다.

 

 

총평 및 소감

 

큰 대회에 출제진으로 참가하는 것은 처음이었는데, 여러 가지를 배워갈 수 있었고 개인적으로도 꽤 보람찼던 기억인 것 같다. SUAPC가 대부분 그렇지만, 셋의 난이도 커브나 퀄리티도 상당히 괜찮은 편인 것 같다. 특히, ad-hoc 성질의 문제와 educational한 문제들이 모두 있었던 점이 좋았다. 스코어보드도 거의 좌셋으로 굉장히 예쁘게 나왔다. 이제 두 개의 대회 + 연말에 있을 하나의 대회로 올해는 3개 대회에 더 관여를 하게 될 것 같다. 문제 열심히 내야지..