Call for Tasks를 통해 UCPC 2022 예선과 본선에 각각 한 문제씩 출제하게 되었다. 내년부터는 참가를 해야 되기에 올해가 마지막 출제 기회라는 생각을 가지고 있었고, 그 기회를 놓치지 않아 정말 다행이면서도 기쁘다. 시험기간을 포함한 몇 달 동안 대회를 준비해온 일들과 그 과정에서 하고 싶었던 이야기들을 풀어보겠다.
올해 크리스마스이브에 열릴 예정인 미적확통컵에 출제할 문제를 고민하다가 떠오른 문제다. 학교 수업을 듣다가 "일차식에 어떤 값을 대입한다면, 그리고 그 일차식이 여러 개라면...?" 대충 이런 생각을 했던 것 같다. 만들고 보니 풀이는 쉽지만 분수를 처리하는 과정이 순탄하지 않아서 난이도도 적당한 것 같고, 밑져야 본전이겠다 싶어 콜포태에 먼저 제출했다. 솔직히 문제가 너무 재미없어서 채택될 거라는 기대는 거의 하지 않았다.
그러나 후술할 다른 문제와 함께 이 문제도 채택되었다는 연락이 와서 적잖이 놀랐다. 더군다나 UCPC 예선 일정과 기말고사가 겹치는데, 대회 문제로 선정될 걸 예상 못했기에 세팅도 당연히 하지 않아서 많이 걱정되었다. 실제로 공부 시간을 많이 뺏긴 했지만 다행히 시험은 무난하게 봤다.
지문은 컨셉을 부여하기가 좀 힘든 세팅이어서 거의 손대지 않았다. 제목이 $f(x)$에서 functionx님의 허락을 받아 functionx로, 그리고 출력 형식이 doju님의 추천을 따라 $-1, 0, 1$에서 $-, 0, +$로 변경되긴 했다. 사실 구현 상으론 원래 버전이 더 편하긴 한데, $-1, 1$이 음수, 양수를 대표하지 못한다는 점에서 나도 바꿀까 고민하긴 했었다.
데이터는 대충 만들면 $ax+b=0$ 의 해가 거의 0 근처로 가버리는 현상이 발생하므로 신경 써서 만들어야 했다. 참가자가 분수 처리를 잘했나 확인하기 위해 일차식의 해와 가까운 쿼리도 적절히 들어와야 하고, double을 쓰는 날먹 풀이도 막아야 하고, 연산량이 가장 많은 데이터도 만들어야 하고... 참 고려할 게 많아서 제너레이터만 11개를 짰다. 완벽한 데이터 셋을 만드는 것은 정말정말 힘든 일이다.
우여곡절 끝에 세팅이 끝나고 많은 분들이 검수를 해주셨다. 우선 나는 굳이 분수를 다룰 필요가 없다는 것과 쿼리가 pbds로 쉽게 귀결된다는 점에서, 풀이를 잘 정리하고 들어간다면 조금 까다로울 수는 있어도 구현이 어렵진 않을 거라 생각했다. 그런데 아니었나 보더라. 분수 구조체를 이용해 좌표 압축과 세그 트리를 쓴 풀이가 많이 나왔고, 대부분 구현이 더러어려웠다는 평이었다.
예선은 기말이 끝난 지 얼마 안 된 때라 체력 이슈로 소멤에 가지 않고 집에서 혼자 관전했다. 대회 초반에 내 문제의 노트의 오타를 지적하는 질문이 올라왔는데, 소멤에 계신 운영진 분들이 빠르게 수정하신 것을 내가 파악하지 못하고 문제를 다시 읽어달라는 잘못된 답변을 달아버렸다. 작은 소란 후에 오타를 수정했다는 공지사항이 올라오고 답변도 수정하는 등 사건이 마무리되긴 했지만.., 대회 전에 꼼꼼히 검수했더라면 충분히 찾을 수 있었던 이슈였기에 너무 화가 나고 자책감이 들었다. 내가 대회라는 옥에 티를 낸 것 같아 속상했다. 그래서 대회가 성공적으로 끝났는데도 기분이 별로 좋지 않았다. 어찌 보면 별 거 아닌 일이지만, 잘한 것보다 못한 것에 민감한 내 성격상 다시는 겪고 싶지 않은 일이었다.
내 문제는 풀이가 전형적이어서 사전 지식을 아는 분들에게는 쉽고 빨리 풀릴 거라 예상했다. 결과를 보면 예상이 어느 정도 맞았던 것 같지만, 구현이 꼬여 고생하는 팀이 꽤 있었고 $O(Q^2)$ 풀이를 시도하는 팀도 많이 보였다. 그리고 pbds를 사용한 AC 코드가 꾸준히 나와 만족스러웠다. 대회 중에 구글링해서 배웠다는 사람도 있는 듯. 이 문제를 통해 pbds를 PS 판에 널리 알리겠다는 나만의 목표는 달성한 것 같다.
좋은 문제라고 생각하는데, 다른 분들은 어떻게 느끼셨을지 궁금하다. 나는 사실 제로부터 풀어보질 못해서 난이도가 가늠이 안 간다. 어려운 애드혹 문제를 출제해 보이겠다는 작은 소망을 생각보다 빨리 이루게 해준 고마운 문제다.
1학년 겨울방학에 GCC가 끝나고 다음 대회 때 출제할 문제를 고민하다가, 치환 암호의 규칙을 살짝 바꾸면 재밌겠다는 생각을 했다.
그래서 그때 작성한 문제의 초안은 다음과 같다.
- 길이가 $N$인 배열 $A$와 $B$가 주어진다. 각각의 원소는 $1$이상 $M$이하의 정수이며, 중복될 수 있다.
- 정의역과 치역이 $1$이상 $M$이하의 정수인 일대일 대응 함수 $f$가 주어진다.
- 한 동작마다 $1$이상 $M$이하의 정수 $x$를 임의로 정하고, 배열 $A$에서 $x$와 값이 같은 원소를 모두 $f(x)$로 바꾼다.
- 위의 동작을 최소로 사용해서 배열 $A$를 $B$와 같게 만들 수 있는지 판별하여라.
세팅은 현재 문제와 거의 비슷한데, 배열의 원소의 중복을 허용해줬다는 점과 원소를 변경하는 연산이 시계 방향으로 한 칸 옮기는 게 아니라 일대일대응 함수를 따라 진행한다는 것이 다르다. 잘 생각해보면 함수 $f$는 순열 사이클 분할을 하면 사실상 현재 문제와 같아지고(구현은 복잡해진다), 중복을 제거하는 방법은 꽤 까다롭다.
문제를 만들긴 했지만 풀이 정리가 잘 안 되어서 출제는 못하고 있다가, 이거 내가 어떻게든 풀어서 콜포태에 내면 뽑히겠다는 확신이 들었다. 그래서 기존의 아이디어를 바탕으로 케이스를 열심히 정리한 결과 맞는 것 같은 풀이를 얻어서 기한 내에 제출할 수 있었고, 예상대로(?) 채택되었다는 연락이 왔다. 그래도 떨어지면 어쩌나 엄청 걱정했었는데 좋은 결과를 받게 되어서 하늘에 날아갈 것 같이 기뻤다. 마침 연락을 받은 날이 5월 4일, 내 생일이어서 인생 최고의 생일 선물을 받은 것만 같았다.
전체적인 세팅은 선정되기 전에 미리 해놓았기에 스토리만 어떻게 잘 입히면 끝날 줄 알았다. 그런데 예선이 끝나고 본선 문제 검수가 시작되자마자 hyperbolic님이 정해가 틀렸다고(...) 알려주셨다. 지금과는 다르게 접근했던 당시의 풀이는 불가능한 케이스 하나를 잘못 생각하고 있었는데, 이게 풀이를 수습하지 못할 정도로 치명적이었다. 그래서 정해를 갈아엎어야 하는 상황이 왔고, 곧 수학여행을 갈 생각에 들떠 있던 나는 절망에 빠졌다. 다른 출제진 분들이 풀이를 고민해주시는 동안 나는 나대로 문제를 다시 풀어보았지만 그저 나의 무능함을 뼈저리게 느낄 뿐이었다. 그러다가 '원형상에서 순서가 같아야 한다'는 것을 관찰했는데, 출제진 분들은 이미 이 관찰을 토대로 풀이를 발전시켜 나가는 중이었다.
그렇게 완성된 풀이는 D3~2 수준의 어렵고 복잡한 애드혹이었다. 이는 애초에 의도한 난이도와 거리가 멀었기에 전체적인 난이도 커브에 크게 영향을 주었고, 따라서 이 문제의 난이도를 낮출 필요가 있었다. 출력을 최솟값 대신 Y/N으로 바꾸는 방안, 범위를 줄이는 방안 등이 나왔고 출제진들이 열심히 회의한 결과, 핵심 아이디어는 유지하면서 자잘한 처리를 피하기 위해 함수 $f$를 단순화시키고 중복을 없애는 방향으로 결론이 났다. 나는 이때 멘탈이 완전히 나가서 모든 걸 포기하고 PS 판을 은퇴하는 계획을 심각하게 고민하고 있었기 때문에 거의 참여하지 못했다. 농담 같겠지만 진짜로 힘들었다.
그래도 어찌저찌해서 문제의 기조는 잡혔고 정올 대비를 포기하면 기한 내에 세팅을 끝낼 각이 보여서 힘내서 세팅을 시작했다. 제주도로 간 수학여행에서는 장소를 이동하는 틈틈이 머리를 짜내서 지문을 작성했다. 코딩하는 사람들은 알 만한 말장난인 '라즈베리 파이'를 컨셉으로 잡은 것은 개인적으로 센스 있는 선택이었다고 본다. 내가 글솜씨가 좋지 않아, hyperbolic님과 doju님이 지문을 정말 많이 재작성하고 다듬어주셨다. 그리고 데이터 세팅이 다시 시작되었다...
문제가 약화되었지만 저격해야 할 코드가 달라져서 기존에 짠 여러 제너레이터가 거의 필요 없게 되었다. 그리고 문제 특성상 최솟값을 가지는 데이터를 만들기가 매우 까다롭기 때문에 이를 만족하는 제너레이터를 짜기가 만만치 않았다. 또한 풀이를 완벽하게 파악하고 있어야 틀린 코드를 저격하든 말든 할 텐데, 다른 분들의 AC 코드를 이해하는 것이 쉽지 않았다. 그래서 일부 데이터는 약간 특이한 규칙으로 만들어졌다. 뚫리는 게 겁나서 말은 아끼겠는데, 최솟값을 가지면서 분포가 완전히 랜덤한 데이터를 못 만들겠어서 대충 특정한 규칙을 가지면서 적당히 랜덤하게 생성되는 데이터를 넣었다. 물론 이렇게 해도 강할 거라는 믿음이 있었고, 아직까지 특별히 뚫은 것처럼 보이는 코드는 없는 걸 보면 괜찮은 듯.
대회 이틀 전 갑작스럽게 라즈베리 파이를 만드는 한별이 그림을 받았다! 그림이 있으면 좋겠다고 생각은 했었지만 이미 민폐를 많이 끼쳤던 터라 혼자 만의 상상으로 남겨뒀었는데, 정말 감사하게도 havana님이 멋진 그림을 그려주셨다.
온라인에서만 보던 분들을 실제로 만난다는 설레는 마음을 안고 아침 9시 20분쯤 삼성 코엑스 근처 대회장에 도착했다. 삼성역에서 functionx님을 만나서 다행히 헤매지 않고 올 수 있었다. 대회장은 생각보다 작았지만, 곧 있으면 이 공간이 실력 있는 PS러들로 꽉 채워질 거라는 생각에 가슴이 웅장해졌다. 이미 준비가 거의 끝난 상태라 내가 할 일은 별로 없었고 대회에 쓸 헬륨 풍선을 나르는 작업을 했다. 그리고 대회 시작 전까지는 출제진 분들과 수다를 떨거나 정말 이름만 알고 있던 분들을 찾아다니고 안면을 트며 시간을 보냈다. 내 명찰을 보고 먼저 말을 걸어주시는 분들도 계셨다. 감사합니다.
대회 시작 후 한두 시간은 풍선을 배달하느라 정말 정신없이 지나갔다. 라즈베리 파이는 제출이 드문드문하게 나왔으나 다들 맞왜틀에 시달리고 있었다. 67분에 퍼솔이 나왔고, 내가 직접 흰색 하트 풍선을 화석 팀에게 걸어주었다.
시간이 적당히 지나자 제출이 안정화되어 겨우 숨을 돌릴 수 있었다. 운영진분들과 스코어보드를 구경하며 수다를 떨고 참가자들이 제출한 코드를 읽다 보니 어느새 대회가 종료되었다. 사실 이때 많이 지쳐있어서 뭘 했는지 잘 기억이 나지 않는다. 스코어보드가 프리즈된 후 몇몇 팀에서 큰 반응이 나왔는데, 그 이유를 우리만 알고 있다 보니 되게 흥미진진했던 기억이 난다.
나는 대회 종료 후 일정이 스폰서 세션 → 스코어보드 오픈 → 문제 해설인 줄 알았는데 알고 보니 해설이 가장 먼저여서 많이 당황했다. 급하게 내 차례 직전까지 풀이 슬라이드를 몇 번 정독하고 올라갔지만 역부족이었다. 엄청 떨었던 탓에 시선 처리 & 여유롭게 말하기 등은 생각하지도 못했고 그냥 슬라이드를 읽는 데에 급급했던 것 같다. 그 와중에 말도 계속 절었다. 해설이 끝나니 긴장이 쫙 풀려서 스폰서 세션 시간에는 열심히 잤다.
대회의 하이라이트라고 할 수 있는 스코어보드 오픈과 수상 시간은 정말 즐거웠다. 46트 만에 나온 I번 AC, 중위권 팀의 B 퍼솔, 그리고 상위권의 순위 싸움은 아직도 생생하게 기억난다. 보신 분이 계실지 모르겠지만 정말 방방 뛰며 신나게 리액션을 했다. 너무 재밌었어요
모든 일정이 끝난 뒤에는 운영진들이 남아서 뒷정리를 하고 고깃집을 갔다. 아직 미성년자인 내가 끼어있어서 음주는 하지 않고 따로 2차를 가셨다. (이것 때문에 회식을 갈까 말까 많이 고민했었는데, 고기는 못 참아서 따라갔습니다. 배려 감사드립니다..) 나중에 고깃집에 백준님이 오셔서 UCPC 전통?에 따라 결제를 해주셨다. 백준님을 만나게 될 줄은 상상도 못 했는데... 영광이었다.
소감
이렇게 블로그에 박제까지 해놓았으니 정말 평생 잊지 못할 것 같다. 존경하는 분들과 협업하고 소통하며 많은 것을 배우고 느낄 수 있었고, 덕분에 내 멋없는 수험 생활에 큰 힘이 되었다. 내년부터는 이 멋진 경험을 다시 하기 위해, 절대 본선행 티켓을 놓치지 않도록 노력하고, 또 노력해야겠다. 끝
'Contest > UCPC' 카테고리의 다른 글
| UCPC 2023 본선 후기 (6) | 2023.07.22 |
|---|---|
| UCPC 2023 예선 후기 (12) | 2023.07.02 |
