UCPC 2022 출제 후기

안녕하세요, 하이퍼볼릭입니다.
블로그 자체가 처음이라 무엇을 어떻게 적어야 할지 모르겠네요.
출제 및 검수 시작으로부터 꽤 오랜 시간이 지났던지라 기억이 가물가물하지만 최대한 생각나는것을 적어봅니다.
$ \ $

1. 출제

작년까지는 석사과정이었지만, 올해부터 박사과정 학생이 되었기 때문에 저는 참가자 신분으로 UCPC를 참여하는게 불가능했습니다. 그래서 이번 UCPC 2022는 무조건 출제진을 해봐야겠다, 생각하고 여러 문제들을 고안하고 있었습니다. 지금까지 이런 대형 대회에 한번도 출제해본적 없고, 기껏해야 교내 프로그래밍 대회에 문제를 끄적이는 정도여서 제 출제 스타일을 모르시는 분들이 많을것이라 생각합니다. 저는 "지문은 굉장히 짧지만 문제는 결코 쉽지 않은" 그런 문제를 좋아합니다. 네, AtCoder 스타일의 문제들이죠. 그래서 이번에 문제 낼때도 AtCoder 문제들에서 아이디어 얻어서 문제를 만들었습니다. 제 문제들에서 AtCoder 냄새가 나는(?)것도 그런 이유 때문일지도 모르겠네요.
$ \ $

제가 콜포테에 제출한 문제는 총 3개였고, 그중 2개는 거의 같은 문제인데 어떤 세팅이 더 좋을지 몰라서 그냥 둘 다 제출했었습니다. 콜포테에 제출한 3문제중 2문제가 채택되었으니, 전부 채택되었다고 봐도 되겠네요. 채택된 문제들은 각각 예선 J와 본선 D에 위치하게 되었습니다.
$ \ $

예선 J - 수 정렬하기, 근데 이제 제곱수를 끼얹은

두 수의 곱이 제곱수가 되는 페어를 swap할 수 있다고 할때 어떤 수열을 정렬 가능한가를 묻는 문제입니다. 이 아이디어는 AtCoder Beginner Contest 에서 얻었던것 같습니다. 잘 기억은 안나는데, 그때 특정 문제가 이 문제처럼 "어떤 두 페어가 조건을 만족할때 스왑 가능한데, 전체 수열을 정렬 할 수 있는가?"를 묻는 문제였습니다. 꽤나 신선한 문제여서 이 문제유형에 제 나름대로 조건을 요리조리 끼얹어봤고, 그래서 나온게 이 문제입니다. 처음엔 세제곱이나 네제곱등도 고민해봤는데 쓸데없이 귀찮아지고 문제를 처음 봤을때 느껴지는 신선함을 해칠것 같아서 그냥 제곱수로 두었습니다.
$ \ $

처음에는 각 숫자의 square-free part를 직접 계산해야된다고 생각해서 정해를 $ \mathcal{O}(N\log N + N \text{MAX}^{1/3}) $라고 생각했습니다. 그런데 다른 문제 출제진분께서 $ A_i \times \text{sorted}(A)_i $가 제곱수가 되는지만 보면 된다고 하셨고, 또 실제로 그래서 정해의 시간복잡도는 $ \mathcal{O}(N\log N + N \log \text{MAX} ) $가 되었습니다.
$ \ $

간단한 문제라 문제 세팅이 쉬울것이라 생각했는데, 실제로는 예선에서 모든 출제진과 검수진들이 다 달려붙어서 검증한 최고로 세팅이 빡센 문제가 되었습니다. 이번 대회 준비로 뼈저리게 느낀것은, 문제 난이도와 출제 난이도는 절대 비례하지 않는다는 것입니다. 이 문제를 푸는데 나오는 오답만 해도
$$
\mathcal{O}(N^2 \log \text{MAX}) \\
\mathcal{O}(N\log N + N \text{MAX}^{1/2})\\
\mathcal{O}(N\log N + N \text{MAX}^{1/3})\\
\mathcal{O}(N\log N + N \text{MAX}^{1/4})\\
\mathcal{O}(N\log N + N \log^2 \text{MAX})\\
$$
등등이 있었고(...) 결국 $N$을 엄청나게 늘리고, $\text{MAX}$를 늘리고, 폴라드-로 방법을 저격하는 데이터를 만들어야 했습니다. 이 문제는 예선에 배치된게 상당히 다행이었는데, 본선에서 128bit 정수를 사용하는 문제를 내고 싶지는 않았기 때문입니다(실제로 64bit 정수범위 내에서 풀 수 있는 문제지만 대부분의 팀께서 128bit 정수를 사용하여 문제를 풀었습니다).
$ \ $

실제 예선에서는 스코어보드를 보면서 꽤 뒷목을 잡았던 문제였습니다. 전략을 생각하는게 굉장히 어렵고 정수론적 직관이 꽤 들어간다고 생각해서 높은 난이도를 줬는데, 정말, 정말 많은 팀이 풀더라고요....... 출제진들 전부 J가 많이 풀리는걸 보면서 "이게 많이 풀린다고?"라고 말하며 탄식(?)을 했었습니다. Proof by AC하기 쉬운 문제여서 그런걸까요?
$ \ $

본선 D - 수열과 쿼리의 부분합의 합

이 문제 역시 AtCoder 문제에서 따왔는데, 바로 이 문제였습니다. 간단하게 설명하면, 가능한 모든 쿼리의 개수가 $ \frac{N(N+1)}{2} (M+M+1)^Q $개인데, 그 $ \frac{N(N+1)}{2} (M+M+1)^Q $개의 쿼리의 결과값을 모두 더한 값을 출력하라는 문제였습니다. 이런 미친 문제가 다있나! 제가 이 문제를 처음 봤을때 정말 충격 그 자체였습니다. 그리고 이 충격을 다른 사람들에게도 알려주고 싶어서 이 문제와 비슷한 형태의 문제를 요리조리 떠올려봤습니다. 그 결과가 바로 이 문제입니다. 처음에는 Segment Tree with Lazy Propagation가 정해였고, Segment Tree를 쓰는 문제중 가중치가 있는 구간합을 계산해야하는 문제가 적어서 참가자들이 꽤 신선한 느낌을 받을 수 있을거라 생각했습니다. 하지만 queued_q님께서 Segment Tree를 안쓰고 스위핑으로 쓰는 풀이를 제시해주셨는데, 이 풀이가 훨씬 깔끔하고 스위핑 방법으로 푼 참가자가 더 많은것 같아서 조금 마음이 아팠습니다 :( 그래도 참가자분들이 이 문제를 보고 신선한 느낌을 받아줬다면 그걸로 충분히 만족합니다.
$ \ $

2. 검수
간단하게 검수한 문제들의 기억도 되살려봅니다.
$ \ $

예선 A. 코딩은 체육과목입니다
할말이 없네요(...) 그냥... 풀었습니다
$ \ $

예선 B. N수매화검법
CCW를 이용하여 두 선분이 교차하는지 잘 확인하고, 그리디를 써야하는 문제로 기억합니다. CCW가 어렵기도 해서 실제 대회에서 많이 못풀지 않을까 생각했는데, 인터넷 검색이 되서 그런지 두 선분 교차 알고리즘을 다들 잘 짜오셔서 잘 푸셨습니다.
$ \ $

예선 C. 수소철도 충전 시스템
AtCoder에서 지겹도록 많이 본 트리DP를 쓰는 문제입니다. 하도 대회에서 많이봐서 보자마자 그냥 슥슥 풀었는데 다른 분들은 검수를 꽤 어려워했던것 같습니다. 플레3정도로 난이도 의견을 줬는데, 실제로는 다이아5가 되었네요
$ \ $

예선 D. functionx
원래는 이런 제목이 아니었던걸로 기억하는데, 출제진에 functionx님이 계셔서 문제가 functionx가 되었습니다(...). 해야하는건 굉장히 간단하지만 구현은 굉장히 고달펐습니다. 출제자분께서 OSRank같은걸 노리셨다고 했는데 전 그런 자료구조를 싫어해서 모든 점들 좌표압축 + Segment Tree를 이용하여 풀었습니다(실제로 OSRank를 짜본건 SCPC 2017 본선이었나? 거기서 Treap을 짜본것 말고는 없네요)
처음에는 좌표압축을 분수값들 좌표압축을 하였는데, 실수를 사용하는 풀이를 저격하기 위하여 값을 키웠더니 풀이가 통과되지 않았습니다. 그래서 분수가 주어졌을때 그 분수 근처의 정수값들을 저장하여 좌표압축을 하였더니 통과하였습니다. 여러모로 귀찮았던 문제였네요.
$ \ $

예선 G. SCV 체인
굉장히 재밌었던 문제였습니다. 문제가 재밌고 쉬워서 많은 분들이 푸실줄 알았는데 꽤 안풀린게 의외였습니다.
$ \ $

본선 A. 니은숲 예술가
출제진분께서 골드1난이도를 의도하셨다고 해서 일단 눈을 의심했고(...) 문제 본 뒤 한참을 고민해도 풀이가 안떠올라서 다시 또 눈을 의심했습니다. $N^3$ DP를 떠올린다면 어떻게든 최적화해서 $N^2$으로 풀 수 있겠지만, $N=5000$이란 제약을 보고 $N^3$풀이를 먼저 생각해보는 사람이 얼마나 많을까요? 한참을 고민하다 $N^3$ DP를 최적화 가능하다는걸 깨닫고 결국 맞았습니다만, 절대 골드급 문제는 아니다 생각해서 다이아난이도를 주었습니다. 실제로도 다이아 문제가 되었네요.
$ \ $

본선 B. NPU 최적화
계속 검수를 미루다가 검수진이 필요하다는 요청을 계속 받아서 대회 당일 새벽에 겨우겨우 풀었습니다. 정확히 대회 당일날 자정에 시작해서, 새벽 6시에 풀었으니 밤을 꼬박샜네요(...) 아침일찍 대회 준비도 하러가야했기 때문에 약 2시간 쪽잠을 자고 바로 대회장으로 갔었습니다.
조금 더 문제에 관한 얘기를 해보면, 의외로 문자열 파싱은 힘들지 않았지만 문제 자체의 난이도, 즉 트리 탐색순서를 정해서 탐색하는것 자체가 굉장히 어려웠습니다. 노드를 탐색하는 순서를 나열하면 Euler Tour형태가 된다는건 바로 파악했지만, 어떤 노드를 우선해야하는지, 그리고 어떤 공간을 어느때에 비워줘야 하는지 등등에서 말려서 굉장히 끔찍한 문제였습니다. 어찌저찌 맞아서 검수를 하긴 했지만, 솔직히 말해서 다시 풀고싶지 않네요
$ \ $

본선 C. 라즈베리 파이
원래는 "수열 마법"이라는 제목의 문제였던걸로 기억합니다. 제가 이 문제를 처음 검수했을텐데, 정해가 틀린것을 찾았었고 출제자분 및 다른 검수진분들과 모여서 엄청나게 정해를 고민했었습니다. 출제자의 의도와 다르게 이 문제를 풀기 위해서는 굉장히 까다로운 케이스워크를 진행해야했고, 어떻게든 풀이를 찾아냈으나 너무나도 풀이가 고약해서 최소 다이아3급의 문제로 예상되었습니다. 이 문제가 그대로 다이아가 될 경우 중간난이도에 해당하는 문제가 너무 적어지는 문제가 있어서 어떻게든 이 문제의 난이도를 줄여야했습니다.
$N$을 줄이자던가, YES/NO 문제로 바꾸자는등 문제 난이도를 줄이기 위한 몇가지 제안들이 오고 갔었고, 그러던중 배열의 중복을 제거하면 복잡한 케이스 워크들이 많이 사라지는 것을 발견하였습니다. 정확히는, 기존 검수진들이 찾아낸 풀이를 요약하면 까다로운 케이스 워크를 진행하여서 배열의 중복을 제거한뒤 그리디 혹은 투포인터를 이용하여 답을 구하는 것이었기에, 배열의 중복을 없에는것 만으로 문제가 많이 쉬워졌었습니다. 이 제안은 바로 채택이 되었고, 그 상태에서 문제에 이야기를 덧붙여서 이 라즈베리 파이 문제가 탄생하게 되었습니다. 실제 대회에서도 많은 참가자분들이 이 문제의 까다로운 경우를 처리하기 위하여 고생했던걸로 기억하는데, 그게 최대한 문제를 간단하게 만든거였습니다....
출제자분께서 정말 고생한 문제였습니다. 정말 수고 많으셨다고 말씀드리고싶네요.
$ \ $

본선 E. 반도체 제작
문제를 읽었을때, 실수값이 가능하다는 것에서 LP-dual일것이란 확신을 20%정도 하였고, 문제가 요구하는게 LP형태가 되었기에 LP-dual이란 확신을 99.999999999999% 하였습니다. 그래서 바로 LP식정리 및 LP-dual을 시도하였고 거기까지는 좋았는데... 진짜 뒤집기가 끔찍하게 어려웠습니다(...) Transpose해야하는 배열의 크기가 $ (2N+2M) \times (M+4) $ 였기에 하나하나 손으로 적는것도 힘들었고, 퍼텐셜이 음수도 가능했기에 변수 $E$를 $E^{+} - E^{-}$ 형태로 작성하여 쪼개야했습니다. 정말, 정말로 섬세하고 꼼꼼한 식정리가 필요하였기에 이 배열을 뒤집을때마다 계속 다른 형태의 문제가 되어서 엄청난 곤혹을 겪었습니다. 까놓고 말해서 식정리만 4시간을 했던것 같네요. 문제를 풀고나서 한치의 망설임도 없이 최소 난이도 다이아1을 주었고, 실제로는 루비5가 되었습니다. 여담으로 출제자분께서 다이아3을 의도했다고 했던것 같은데, 문제 풀기 위한 최소 지식이 LP-dual에 flow with demands인데 다이아3이 웬말이냐!고 태클을 걸었었습니다
$ \ $

본선 F. 대충 카드로 몬스터 잡는 게임
정해가 Monotone Queue Optimization이여서 초기 의도가 다이아3으로 되어있었는데, 제가 풀어봤을때 단순 Segment Tree with Lazy Propagation으로 풀 수 있어보여서 그렇게 풀었습니다(겸사겸사 이 풀이를 살짝 다르게 써서 $ \mathcal{O}(N \sqrt{N} ) $ 버킷 풀이도 작성했습니다). 더이상 Monotone Queue Optimization을 의도할 필요는 없었기에 문제 난이도는 플레로 내려왔고, 위에서 말했듯 중간 난이도 문제가 갑자기 붕 떠버린 상태였기에 굉장히 다행이었습니다.
$ \ $

본선 G. Traveling Junkman Problem
$N \leq 18$을 볼때부터 Fast Zeta Transformation을 예상했었고, 실제로 그랬습니다. 다만 Fast Zeta Transformation을 눈치채도 거기까지 도달하기(예를 들어, 몇번 bit에 어떤 값을 주어야 하는가?)가 어려웠습니다.
$ \ $

본선 H. 특별상
그냥 풀었습니다
$ \ $

본선 I. 사건의 지평선
무언가 Segment Tree구조를 이용하여 간선 개수를 줄이는 고인물 테크닉이 있는것 같습니다. 다만 저는 그걸 몰랐었고, 그걸 모른 상태로 풀었습니다. 저는 옛날 AtCoder에서 자주 보였던 "SAT문제인데 간선 개수를 줄여야 하는 SAT문제"에서 아이디어를 따와서 풀었습니다. 이 방법을 쓰면 굳이 Segment Tree구조를 강제할 필요는 없어서, 간선개수 $N \sqrt{N}$개인 그래프를 만들어서 $ \mathcal{O}(N \sqrt{N} ) $시간에 문제를 푸는 저격 풀이를 만들었었습니다.
$ \ $

본선 J. 교집합 만들기
UCPC 본선에서 제가 가장 마음에 들었던 문제입니다. 작위적이지 않은 굉장히 깔끔한 문제상황에 꽤 흥미로운 관찰을 해야하고, 풀이는 굉장히 단순합니다. 저도 이런식의 문제를 만드려고 노력했는데, 이 문제보다 덜 깔끔하고 덜 단순한것 같아서 아쉽습니다 :( 그만큼 이 문제의 퀄리티가 마음에 듭니다.
$ \ $

본선 K. 전국 대학생 프로그래밍 대회 동아리 연합 토너먼트
패배자를 특정 짓는건 굉장히 쉽지만, 승자를 특정 짓는건 굉장히 어렵습니다. 무언가 쉽게 될듯말듯하면서 결국 케이스워크를 통하여 어렵고 까다롭게 풀어야 한다는게 푸는 사람을 더더욱 애태우게 만듭니다. 본선에서 많은 팀들이 이 문제의 늪에 빠져 허우적댈것이라 예상했었고, 실제로 이 문제의 평균 시도 횟수는 본선문제 최고가 되었네요 하하.
$ \ $

본선 L. 커넥티드 카 실험
그냥 풀었습니다
$ \ $

본선 M. ×+ +×
그냥 식 정리하여서 FFT를 시도했습니다. 식 정리가 조금만 침착해도 쉽게 할 수 있어서 그렇게 어렵지는 않은 문제인데, 본선에서 FFT를 직접 구현해야하기에 본선에 거의 모든 팀이 풀지 못할것이라 생각했습니다. 게다가 이 문제 정해는 FFT+분할정복으로 $ \mathcal{O}(N \log^2 N ) $ 이기 때문에, 느린 FFT를 짜면 시간초과를 받을것이기에 더더욱. 실제 대회에서도 딱 1팀이 풀었네요.
$ \ $

3. 대회 후기
정말 많은 분들은 오프라인으로 볼 수 있어서 좋았습니다. 저같은 경우 이제 PS 시작한지 9년째라 같이 PS했을때의 인맥들은 많이 PS를 접은 상태였는데, 다른 PS하는 분들을 친구로 사귈 수 있어서 정말 기뻤습니다. 출제, 검수진분들도 대부분이 처음보는 분들인데 굉장히 친절하시고 성격이 좋으셔서 대회를 준비하면서 정말 즐거웠습니다.
$ \ $

본선대회장에서는 운영진분들 이외의 참가자분들께서도 저에게 말을 자주 걸어주셔서 놀랐습니다. 지나가다가 하이퍼볼릭님 팬이에요 하고 지나가는 분들도 꽤 있었고(...왤까요? ICPC등 현역으로 뛸때도 그런 말 들어본적이 없는데 왜 이제와서.... 감사합니다 ㅠㅠ) Codeforces나 AtCoder같은거 항상 열심히 꾸준히 하시고 높은 순위에 자주 보인다고 대단하시다고 하는 분들도 계셨었고. 그중에서도 대회에서 만나신 분들중에서 가장 기억에 남으신 분은 역시 대회장에 러브라이브 티셔츠를 입고 나타나신분(...) 제가 러브라이브 중증 오따꾸여서 반가운 마음에 말을 걸고 즐거운 오따꾸 대화를 했었었네요(...) 취미가 일치하는 분들을 만나고 다닌다는건 언제나 즐거운일이죠.

$ \ $
두서없이 주저리주저리가 많았습니다만 종합하면 굉장히 즐겁고 보람찬 시간이었습니다. 다음 UCPC는 어떻게 될지 모르지만, 다시 출제진으로 참여할 수 있다면 참여하고 싶네요. 앞으로도 더 많이 재밌는 문제들을 만들고, 더 많이 PS 문제들을 풀고 열심히 살겠습니다! 모두 긴 글 읽어주셔서 감사합니다!

 

본선 D번 문제를 설명하는 제 사진. UCPC 사진은 UCPC 공식 홈페이지에서 찾아볼 수 있습니다.