제2회 피갤컵 출제 후기

3월 16일 일요일에 제2회 피갤컵이 개최되었다. 이는 대회가 있기 전 미리 써두는 글로, 아마 읽는 사람은 16일 5시 이후에 읽게 될 것이다. 따라서 대회 후 글의 내용이 일부 바뀔 수도 있다. 이 글에선 내가 출제한 문제에 대한 이야기만 할 것으로, 전체적인 프로세스와 후기에 대해선 다음 글에 모아서 쓸 듯 하다.

 

나는 이번 피갤컵 콜포테에 문제를 총 5개 제출하였다. 그 중 2개가 선발되어 출제진으로 참여하게 되었다. 콜포테에 낸 문제는 애매한 것 2개, 꽤 좋았던 것 2개, 아 이건 좀 싶은 것 1개를 냈는데, 딱 꽤 좋았던 것 2개가 뽑혔다. 출제한 문제는 C(2^3은?)와 G(내 맘대로 정렬)이다. 놀랍게도 나는 이번에 구성적 문제를 내지 않았다! 구성적을 출제했을 거라고 생각하신 choyj님을 이겼다. 구성적 출제를 안한 사유는, 창의력이 부족해서.. 괜찮은 수열 아이디어가 없기 때문이다. 몇 개 만들어 본 건 있는데 다 랜덤한테 털려서 폐기됐다. 그리고 낸 5개 문제 중 3개가 카운팅 문제였고, 뽑힌 문제는 모두 카운팅 문제이다.

---

C - 2^3은? (출제자 예상 티어 : S1)    

  #math #case_work

이 문제는 5개 중 마지막으로 낸 문제이다. 과학 학원 시험 공부를 하다가 갑자기 생각난 문제로, 사람들의 대화 중 2^3=1이라는 유머 글을 바탕으로 만든 문제이다. 실제로 XOR로 생각할 때와 지수로 생각할 때가 같을려면 어떨지 궁금했고, 그걸 3개로 늘려서 출제했다. 원래는 $N$개의 수에 대해 구하는 게 처음 생각한 문제였으나, fwht를 사용해야 하는 이슈로 절대로 그 수준의 문제는 아니라고 생각했기 때문에 $N=3$으로 바꿨다. 그랬더니 적당한 케웍 문제가 되었고, 생각보다 꽤 긴 시간을 걸쳐 답을 증명을 했다. 당연히 $p>1,q>1,r>1$에 대해서 가능한 것이 없다는 걸 PBA한 사람이 많을 것이라고 예상한다. 실제로 콜포테에 제출한 해설에는 다음과 같은 문구가 있다.

나도 그럴거라고 생각하고 문제를 풀어갔기 때문이다..

저 케이스가 불가능하다는 건 돌고 돌아서 증명한 느낌인데, 더 쉬운 증명이 있을거라고 생각한다.

의도한 증명은 다음과 같다. a=1, a=1 && b=1인 경우의 증명도 약간의 케웍으로 풀리는 문제이다. 검수때는 생각보다 의견이 다양했는데 S3에서 G4까지 있었다. 검수 때 알았는데 o3가 꽤 똑똑하다.. 어렵진 않은 문제였지만 AI한테 뚫려서 슬프다.

 

---

G - 내 맘대로 정렬 (출제자 예상 티어 : P4)

  #math #combinatorics #number_theory #tree #dp #dp_tree #flt

이 문제는 피갤컵 콜포테를 하기로 마음 먹었을 때의 첫 문제로, 어떤 문제집에서 아이디어를 얻어왔다. 사실 저런 문제를 풀 때면 부등호 관계가 나오면 나는 항상 이를 트리로 만들어보는 버릇이 있었는데, 이 버릇때문에 접근이 쉬웠다. 콜포테에 처음 제출할 때는 $[l,r]$에서 $l$ 이전 범위를 고려를 안한 상태로 해설을 써서 냈는데, 이에 대한 오류를 문제가 선정된 후 발견해서 상당히 당황했다. 다행히 이를 고려했을 때에도 적당히 중복되는 부등호를 쳐내면 트리가 됨을 알았고, 수정하였다. 트리로 만들었다면 적당한 tree dp 혹은 조합론 등의 지식으로 $\frac{N!}{\prod _{i=1}^{N}size[i]}$가 답이라는 걸 알 수 있다. 다만 이 문제에는 모든 테스트케이스에서 $N$의 총합에 제한이 없어서 트리를 직접 구현하고 dfs를 돌려 size 배열을 채워서 풀면 모듈러 역원이나 $N!$을 $O(NlogN)$ 혹은 $O(N)$에 전처리 한다고 해도 $O(TN)$이 되어 시간 초과를 받을 것이다. 이는 트리의 개형을 좀 살펴보면 해결할 수 있는데, 서브트리의 크기 (size[i])가 1인 경우가 상당히 많음을 알 수 있다. 실제로 대충 Q개의 정점만 서브트리의 크기가 2 이상일 수 있다. (정확히는 2Q인가 3Q에 bound된다.) 이를 이용해 서브트리의 크기가 2 이상인 애들의 서브트리 크기만 적당한 관찰로 구해줘서 나눠주면 된다. 원래 이 부분은 문제에 없었는데, 콜포테에 처음 낸 $N<=5\times {10}^6$ 제한이 잘 안돌아간다는 걸 알고 이를 해결할 방법을 찾다가 구현도 짧고 꽤 괜찮은 풀이라 생각하여 개최자분께 말씀을 드려 저 과정을 추가하였다. Q의 합에 제한이 있으므로 이를 다 수행하면 최대 $O(N+QlogQ)$에 문제를 해결할 수 있다. $O(N)$은 전처리에 드는 시간이다. 사실 나는 모듈러 역원 1~N까지를 $O(N)$에 전처리하는 방법을 몰랐어서 정해 코드는 $O(N+Q(logQ+logMOD))$로 짜져 있다. boj stack 기준 132ms에 무난하게 돌았다. $logQ$는 쿼리 정렬때문에 붙었다. 나름 온정신을 갈아넣은 문제로, 엄청나게 신경 쓴 문제이다. 많이 풀어줬으면 좋겠다. 이 문제에 투자한 시간만 20시간이 넘을 듯 하다. 이를 계기로 플래티넘급 문제 출제는 엄청나게 힘들다는 걸 알게 되었다.. 다음부턴 하지 말도록 하자

(이 괄호 내용은 대회 후 추가한 내용이다. 생각보다 G가 많이 풀렸던 것 같다. 웰노운이라 그런 듯 해서 뭔가 아쉬웠다. 다음번엔 이거보다 더 좋은 문제를 내보고 싶다.)

 

BOJ에 직접 출제는 처음으로 해보는 경험이였지만 나름 신선하고 재밌던 것 같다. BOJ Stack 시스템이 엄청나게 깔끔해서 놀랐다. polygon도 처음으로 써봤다. 검수를 대부분이 다 처음이였지만 나름 열심히 하려고 노력한 듯 하다. 지능 이슈로 F번까지밖에 검수하지 못했다는 게 좀 아쉽다. 어쩌다보니 싫어했던 dp문제를 내가 직접 출제하게 됐다. 다만 대회 운영에 참여하는 건 매우 많은 에너지를 쏟아야 한다는 것도 알게 되었다. 나중에 출제할 시간이 된다면 콜포테에 언젠간 또 문제를 만들어 제출해보지 않을까. 정말 좋은 경험이였다. 전체적으로 느낀 느낌은 다음 글에 서술하도록 하겠다.