2022 PPC 개최 후기

이번 여름, 4연속으로 진행했던 대회 운영의 마지막을 장식한 PPC이다. 사실 시작은 제일 먼저 했다..ㅋㅋ 할 말이 무척 많으나, 글에서 하나씩 풀도록 하겠다.

 

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

에디토리얼 : https://www.acmicpc.net/board/view/100196

발단 및 출제 과정

PPC에는 몇 가지 대회 규정이 있는데, 그 중 하나가 "모든 참가자는 전년도에 수상한 상보다 높은 상만을 수상할 수 있다." 라는 규칙이다. 나는 작년 대회에서 1등을 했기에 출전을 할 수 없었고, 자연스럽게 출제진으로 빠지게 되었다. 사실 저 룰이 없었더라도 양심상 나가지 않았을 것이다. 여튼, 그렇게 21년도 출제진에서 hyperbolic 선배가 검수진으로 빠지고 내가 들어간 qjatn0120-slah007-leo020630으로 출제진이 확정되었다.

 

문제 출제는 엄청나게 이른 2월부터 시작했는데, 대회가 1학기에 열릴 가능성도 있었기 때문이었다. 그렇게 수십 개의 문제들이 만들어졌고, 그 중에서 뽑은 1차 셋 12문제는 2월 말쯤 확정되었다. 이때부터 지금까지 살아남은 문제들에는 A, D, G, I, J, L이 있다. 남은 6문제 중 2문제는 중복이 발견되어 폐기하였고, 4문제는 다 내가 낸 문제였던 것으로 기억하는데 개인적으로 다 별로라고 생각해 보류하였다. 1학기가 마친 후, 남아있던 6문제에 새로운 6문제를 더해 새 셋을 만들었다. 기존에 제일 쉬운 문제였던 G가 브론즈가 아니라는 의견이 있어 그 당시에는 확실히 브론즈라 생각했던 H (나는 B3정도를 의도했다 ㅋㅋ)를 추가하고, 다른 문제들은 대체적으로 1차 셋에서 다루지 않았던 부분들을 추가하는 방향으로 만들어졌다. 

 

그렇게 만들어진 2차 셋을 가지고 검수진분들께 갔다. 셋을 보시고 검수진 분들, 그 중에서도 특히 교내 사정을 잘 아시는 Hyperbolic님의 강력한 의견은 셋이 너무 어렵다는 점이었다. 아무래도 잘하는 사람들이 모두 출제로 빠졌고, 작년 스코어보드가 워낙 처참했기에 나온 의견인 듯 했다. B1, E1 버전이었는데도 이런 의견이 나왔기에, 여러 번의 회의를 거쳐 총 두 가지 너프를 가했다. 첫 번째는 A의 입력 제한을 너프한 것이었다. 원래는 \(O(NL)\) 풀이만 통과되는 제한이었는데, A번이기도 하고 셋에 실버가 너무 없었기에 이를 너프해 실버로 만들었다. 두 번째는 실버 난이도의 쉬운 문제 하나를 추가하는 것이었다. 어떤 문제를 추가할지 고민하다가 실버 문제의 단골 소재인 스택을 가져와서 학교 이름과 적절히 섞었더니 문제 하나가 나왔다. 다행히 검수진 분들 반응이 좋아 그대로 추가했다. 아쉽게도 실제 티어는 기획보다 살짝 높은 G5쯤에 찍혔다.

 

이렇게 본 대회 셋 13문제가 확정되었고, 의도적으로 너프했던 B와 개인적으로 내고 싶던 E의 Hard 버전을 추가해 오픈은 총 15문제로 나가게 되었다.

 

문제별 후기

각 문제의 출제 의도, 출제 및 준비 과정 등에 대해 써 보도록 하겠다. 내가 낸 문제는 B, C, E, G, H, J, M이다. 여담으로, 대회 문제를 내다 보면 '내야 하는 문제'와 '내고 싶은 문제'가 갈리는 것 같다. 이번 대회에서 '내고 싶어서' 낸 문제들은 C, E2, J이며, 나머지는 전자의 의도로 출제되었다.

 

A. 약속 장소 / 출제자 : slah007

 

셋에 거의 처음부터 있던 구현문제이다. 딱히 모난 부분이 없어 출제까지 함께하게 되었다. 현재의 버전은 앞서 말했듯 한 번 너프된 버전이다. 너프 전의 난이도는 골드 중위 정도인 것 같고, 너프 후는.. 난 쉽다고 생각했는데 처음 접근을 이상하게 하면 좀 꼬일 여지가 있는 것 같았다. 검수 중에 나온 재미있는 풀이로는 랜덤이 있는데, 맞을 확률이 1/e인가 그랬던 것 같다. 자세히 보진 않았다. 대회 시작 후 무수한 WA로 출제진을 공포에 빠뜨린 문제이기도 하다..ㅜㅜ 알고 보니 지문 서술에 애매한 부분이 있어 이를 잘못 이해한 팀들이 있는 것 같았다. 질문이 들어와 이를 수정해 준 뒤에는 꽤 많이 맞아서 다행이었다.

 

B1. B2. X 만들기 / 출제자 : leo020630

 

셋에 DP 문제가 웰노운과는 너무 거리가 먼 L밖에 없어 내가 만들어 추가한 전형적인 DP 문제이다. 대충 LIS 같이 생긴 것을 4방향에 대해 모두 구해주면 된다. Easy 버전은 구현을 비교적 쉽게 할 수 있는데, Hard는 겹치는 좌표를 좀 신경써주어야 한다. 원래는 \(N \leq 1000\)이었는데, 검수 중 \(O(N^3)\)이 뚫리는 것을 발견해 제한을 늘렸다. 검수 중에 제출된 \(O(N^2logN)\) 코드들은 다 맞길래 시간 제한을 그냥 1초로 두었는데, 상수가 크면 TLE를 받을 수 있는 것 같다. 후술하겠지만, 본 대회때 이거로 틀리신 분이 나와서 좀 안타까웠다.. 이런 식의 상수 최적화를 별로 좋아하진 않아 잠시 그냥 2초로 할걸.. 이라는 생각이 들었던 것 같다. SCPC때의 내 모습이 겹쳐 보여 그런게 아닐까?

 

C. MMST / 출제자 : leo020630

 

B와 마찬가지로, I 말고 그래프 문제가 하나는 더 있어야 한다고 생각했다. SCC, 플로우 등 그래프 심화는 플레 이상이 대부분이기 때문에 골드에서는 MST 정도 말고는 낼 게 보이지 않아 MST를 가지고 한 10분 생각하다 나온 문제이다. 많은 고인물 분들과 마찬가지로, 나 역시 이 문제가 가장 먼저 떠올랐으나, 제한을 좀 추가하면 더 쉽게도 풀 수 있다는 것을 깨닫고 큐에 넣었다. 여담으로, 모든 간선의 가중치가 다르다는 제한이 없으면 어떻게 풀지 아직도 잘 모르겠다.. 검수 중 랜덤 풀이가 발견되었고, 막는 것이 불가능함을 보인 후 그냥 허용하기로 했다. 의외로 본 대회+오픈컨에서 랜덤으로 푸신 분이 나오진 않았다. 원래 뭔가 이상한 제한을 가지고 장난치는 문제를 별로 좋아하진 않으나, 이 문제는 제한이 자연스럽게 녹아들어 있어 괜찮은 것 같다. MST를 공부할 때 풀어보면 좋은 문제라고 생각한다. 많이 풀어주세요ㅎㅎ

 

D. 가채점 / 출제자 : slah007

 

역시 셋에 거의 처음부터 있던 대장 문제이다. 작년부터인지 그 전부터인지는 모르겠지만, PPC에는 매년 "풀지 말라고" 내는 대장 문제가 있는 것 같았다. 올해는 이 문제가 그 자리를 차지했다. 사용 알고리즘부터 뉴비에게는 너무 가혹한 아호코라식 또는 Suffix Array이다. 정해는 후자 쪽이고, 전자는 검수하며 나왔다. 난 후자로 풀었는데, 특정 테크닉 한 2개 정도만 알면 후자가 더 쉬운 것 같다. 검수 중 KMP랑 아호코라식이랑 루트를 섞어서 푸는 풀이가 나왔던 것으로 기억하는데, 출제자분이 이걸 용납하지 못해 \(N\)을 모두 \(10^6\)으로 늘리고 대신 시간제한을 8초까지 늘렸다. 스택에서 모두 다른 크기의 버킷 코드를 보고 감탄을 금치 못했다.. 문제 자체는 문자열 알고리즘을 다 배운 후 풀 Hard 연습 문제 정도로 적절한 것 같다. 

 

E1. E2. 신기한 숫자 / 출제자 : leo020630

 

셋에 수학 문제가 없길래 10초만에 만들어서 큐에 넣은 문제이다. 풀어보니 생각보다 구색이 잘 갖추어져 있어 그대로 출제하게 되었다. E2는 E1을 만들고 끄적이다 만든 문제인데, 푸는 데에는 꽤 오랜 시간이 걸렸다. 저거 풀려고 Mertens Trick 같은 것도 열심히 공부했는데, 막상 배우고 나니 이 문제는 저걸로는 풀기 힘들었다. 여담으로, 이 과정에서 snowflake님의 정수론 시리즈가 큰 도움이 되었다. 그렇게 E2를 대충 풀긴 했는데, 시간복잡도 증명을 하지 못하던 중 slah007 선배가 대충 이유를 설명해주어서 납득하고 출제할 수 있었다. 검수 중에는 여러 검수진 분들이 더 재미있고 빠른 풀이 또한 찾아주셨다. E1은 유일하게 대회 중 데이터 이슈가 터진 문제이기도 하다. 상상도 못한 예외처리를 한 코드들이 맞았는데, 이게 꽤 많아서 대회 끝나고 데이터를 바로 추가했다..ㅜㅜ

 

F. 트리의 MEX / 출제자 : qjatn0120

 

qjatn0120선배가 출제하신 문제이다. 어디 있을 것 같이 생겼는데, 검수진 분들이 지적하지 않으신 걸 보면 그런 건 아닌 것 같다. 문제는 전형적인 small to large 연습문제이다. ETT, mo's 등의 다른 풀이로도 해결 가능한데, 이를 굳이 막지는 않았다. 웰노운이라 그런지 오픈에서는 꽤 많은 분들이 풀어주셨다.

 

G. 택배 색칠 / 출제자 : leo020630

 

어릴 적 교과서에서 본 것 같은 쌓기나무 문제이다. 대충 우리 학교 기숙사에 비유해서 지문을 썼다. 쉬운데, 또 바로 풀릴 정도는 아닌 적당한 난이도의 문제라고 생각한다. 쉬운 문제 포지션이라 처음에는 답의 상한을 int 범위로 제한하려 했지만 그러면 시간으로 뚫릴 가능성이 높아져 그냥 큰 예제를 주고 범위를 늘렸다. 다행히 int 이슈로 틀린 팀들은 크게 없어 보였다.

 

H. 멋쟁이 포닉스 / 출제자 : leo020630

 

원래 가장 쉬운 문제가 G였는데, 더 쉬울 필요가 있어서 출제한 문제이다. 난 분명히 B3정도를 예상했는데, 대부분 B1, 심지어는 S5로 주신 분도 있어서 좀 쫄렸다.. 본 대회에서는 난이도 순 배치가 아니라 퍼솔도 다른 문제에서 나오고 중간까지 이 문제를 찾지 못한 팀도 좀 있었는데, 다행히 스코어보드가 안정화되자 잘 찾아서 모든 팀이 풀어주었다. 한 가지 아쉬운 점은, 예제를 조금만 더 친절하게 줬으면 좋겠다는 생각이 있다.

 

I. 잔디 예측하기 / 출제자 : slah007

 

멀티 소스 BFS 문제이다. 딱히 특별한 점은 없다.. 나도 처음 듣는 M 뭐시기 알고리즘을 쓰면 D가 더 큰 경우에도 해결 가능하다고 한다. 

J. 단짠단짠 피자 / 출제자 : leo020630

 

이번 대회에서 출제한 문제 중 가장 마음에 드는 문제이다. 이 블로그를 열심히 보신 분들이라면 본인이 케이스 워크 문제를 싫어한다는 것을, 더 열심히 보셨다면 원형 문제도 싫어한다는 것을 아실 것이다. 그런 사람이 만든 원형 케이스 워크 문제이다. 문제는 되게 좋다고 생각했는데, 내가 싫어하는 것은 남도 싫어하는 것인지 귀찮아서인지.. 푸는 사람은 아직 많이 없다. ㅜㅜ 여담으로, 3번 쿼리마다 \(K\)가 새로 주어지는 버전을 풀고 Hard로 꼭 내고 싶었는데 진짜 1달을 넘게 생각해도 못 풀겠어서 포기했다. 푸시는 분 꼭 알려주세요.

 

K. 포닉스의 신비한 분자 보고서 / 출제자 : slah007

 

재미있는 기하 문제이다. 이상한 풀이를 막기 위해 검수진 분들과 출제자분이 데이터를 굉장히 열심히 만들었다. 그 결과, 실수를 쓰는 거의 대부분의 풀이가 시간초과 또는 실수 오차로 틀린다ㅎㅎ 풀이는 생각보다 깔끔하니 겁먹지 말고 많이 풀어주셨으면 좋겠다. 물론, 출력 형식에 관해서는 할 말이 없다.. ㅎㅎ

 

L. 포커 / 출제자 : qjatn0120

 

출제 큐에 초기부터 있었던 DP 문제이다. 솔직히 처음에 넣으면서 풀이를 들었을 때는 이해 못했는데, 검수하면서 비로소 이해하였다. 여러모로 특이한 유형이라 꽤 어렵다는 평가를 받았던 것 같다. 

 

M. 포스택 / 출제자 : leo020630, qjatn0120

 

문제 이름은 qjatn0120 선배와 실버 양산 놀이를 하다 만들었다. 문제 내용은 그냥 제목에 맞춰 나올 수 있는 뻔한 내용 중 하나로 골랐다. 이렇게 대충 만들었는데도 꽤 평가가 좋아 좀 놀랐다.. ㅋㅋ

 

셋에 대한 총평

솔직히, 셋에 대한 만족도는 매우 좋다. 약간 과장하자면 내년에는 거의 확실히 올해보다 퀄리티가 떨어질 것 같아 걱정일 정도이다. 2월부터 준비했는데 퀄리티가 별로면 그거도 그거대로 슬프기도 하고.. 검수진분들이 문제 셋이 어렵다며 평가하실 때에도, 문제 퀄리티는 좋게 평가해 주셨던 것으로 기억한다.

좋은 셋이란 어떤 셋일까? 흔히 통용되는 기준 몇 가지를 적어보자면 다음과 같다.

 

• 참여 대상에 알맞은 난이도 분포
• 새롭고, 교육적이며, 재미있는 문제들
• 문제 별로 겹치지 않는 분야

정도가 있을 것이다. 1번 기준은 출제를 마친 후 검수진 분들과 함께 맞춰나갔고, 출제 과정에서는 2번과 3번을 만족하기 위해서 무척 노력하였다. 우선, 2번 기준의 경우 최대한 '웰노운' 문제를 내지 않으려 노력했다. (적어도 나는) 물론, '웰노운' 문제가 있는 셋이 나쁜 셋은 아니다. 하지만, 셋을 충분히 많이 돌다 보면 이 문제가 그냥 '웰노운'인지 '웨ㅔㅔㅔㅔㄹ노운' 인지 느낄 수 있다. 나는 후자의 경우를 최대한 지양하고자 하였다. 그래서 쉬운 문제라도 10초 안에 풀이 구상이 끝나는 문제가 아니라, 아무리 고인물이 잡아도 몇 분은 생각해야 하는 문제를 내고자 했다. 물론 문제 수가 많기도 했지만, 다른 대회 오픈컨에 비해 랭커분들이 오픈컨을 미시는 데에 시간이 조금이나마 더 걸린 것도 이런 이유가 아닐까.. 하고 감히 추측해본다.

 

3번 기준의 경우, 대놓고 의도하진 않았지만 굉장히 잘 지켜져서 만족스럽다. solved.ac에는 프로필 그래프를 그려주는 8대 태그 (수학, 구현, 그리디, 문자열, 자료구조, 그래프, DP, 기하) 가 있는데, 이번 PPC에 출제된 13문제는 가장 쉬운 두 문제 (G, H) + 8대 태그 각각 하나씩, DP와 그래프는 두 개씩 (수학 - E, 구현 - A, 그리디 - M, 문자열 - D, 자료구조 - F, 그래프 - C, I, DP - B, L, 기하 - K) + 애드-혹 성질의 케이스 워크 문제인 J로 구성되어 있다. 원래 그리디가 없었는데, 스택 문제로 출제한 M을 순수 그리디 문제로 보시는 분들이 많아 자연스럽게 그리디 문제가 되었다.

 

출제+검수진들 사이에서는 셋에 대해 좋은 평가를 들었지만, 오픈컨 전까지만 해도 과연 좋게 봐주실지 좀 떨렸다. 다행히도, 셋에 대한 평가는 나쁘지 않은 것 같다. 특히, 문제 기여에 추천! 이 박혀 있으면 그거만큼 기분 좋은 일도 없는 것 같다 ㅎㅎ

 

 

대회 진행

대회는 본 대회와 오픈컨이 동시에 진행되었다. 본 대회는 오프라인으로 진행되었다. 시작 전 우승 후보로 예측한 팀이 2팀 정도 있었는데, 한 팀은 코포 퍼플~블루 정도의 학부생 팀이었고 한 팀은 코포 오렌지였다가 잠시 블루까지 오신 대학원생 팀이었다. 학부생 팀이 프리즈 전까지 신들린 페널티 관리를 보여주며 치고 나갔고, 대학원생 팀은 F를 푸는 선전 등을 보여주며 바로 뒤까지 따라잡았으나 B를 상수 이슈로 계속 틀려 학부생 팀이 우승을 차지하였다.

오픈컨은 숭실대의 edenooo, aeren, jhnah917님이 상위권을 치열하게 경쟁하셨고, edenooo, aeren님이 올솔브를 달성하시며 1~2등을 차지하셨다. 신기한 코드들이 많아서 보는 맛이 있었던 것 같다ㅋㅋ 축하합니다!

소감

오프라인 대회를 운영하다 보니 신경 써야 할 부분도 많았지만, 그만큼 보람찬 부분도 컸던 것 같다. 무엇보다도, 내가 낸 문제를 사람들이 재밌게 풀어주는 점이 참 좋았다. 또, 연이은 대회 운영 참여로 인해 이제는 어느 대회 운영에 투입되어도 1인분 못하고 나올 걱정은 좀 줄어든 것 같다. 남은 문제들이 좀 있는데, 우선 겨울에 열리는 고등학교 교내대회에 조금 쓰고.. 만약 남는다면 이번 스탭 경험이 참 재미있었기에 만약 그때까지 ICPC 팀을 구하지 못한다면 내년 UCPC Call for Task에 내볼 예정이다. 

 

함께 해주신 출제/검수진 분들, 본 대회/오픈컨 참가자 여러분, 아니더라도 PPC 문제에 큰 관심 가져주신 분들 모두 감사합니다!