$\prod_{i=1}^N(R_i-L_i+1)$개의 트리 출제 후기

이번에는 UCPC에 문제를 성공적으로 출제했다. 문제가 만들어진 과정을 알아보자.

 

문제 출제

처음에는 쉬운 플래티넘 문제를 만드려고 했다. 플래티넘 문제는 대회중에 많은 사람들이 풀고, 대회가 끝나고도 많은 사람들이 풀어서 좋다. 세팅하기도 쉽고, (기하 문제나 실수 문제를 내지 않는 이상) 검수하기도 쉽다. 단점은 대회의 승패를 가르는 문제가 아니라는 것과, 나중에 문제를 돌아봤을 때 문제 출제에 대한 뿌듯함이 줄어든다는 것이다. 하지만 나는 문제를 만들 당시에 2개의 어려운 문제가 있었기 때문에 무난한 문제를 만들고 싶었다. (2문제는 런 봄대회에 출제되었다)

 

처음에 생각한 문제는 LFIS 와 같이 exponential하게 증가하는 조건을 주고 특정 수열의 길이가 logN 이하라는 성질을 이용해서 푸는 문제였다. 그래서 다음과 같은 문제가 만들어졌다.

 

정점 $N$개의 트리의 각 정점에 가중치 $a_i$를 부여한다. $S_i$를 $i$번 서브트리에서 $i$번을 제외한 정점들의 $a$ 합이라고 할 때, $a_i \geq S_i$와 $L_i \leq a_i \leq R_i$를 만족해야 한다. 이때 가중치를 부여하는 방법의 가짓수를 구하여라.

 

 

 

하지만 별로 마음에 들지 않았다. 길이가 logN 이하라는 성질을 사용해서 더 나아갈 수가 없었다. 새로운 관찰을 찾으려고 하면 FFT, small to large technique 같은 것만 생각이 났고 이렇게 문제를 어렵게 만들어 놓아도 "문제로 만들 수 있다" 정도의 문제가 될 뿐, 재미있는 문제가 되지 않았다.

 

문제 조건을 조금 바꾸어보았다. $S_i$를 $i$번 서브트리의 정점들의 $a$ 합이라고 했을 때, $S_i \geq p_i$, $a_i \leq q_i$의 조건을 만족하도록 바꿨다. 그리고 대부분의 문제가 그렇듯이, 각 정점의 $a$ 값을 늘릴 때 가중치 $c_i$를 뒀다. 그랬더니 그리디 문제가 되었다. 

 

쉬운 문제를 어렵게 내는 방법으로는 가능한 모든 경우에 대해서 문제를 푸는 것이 있다. 코드포스나 앳코더에서 적당히 뇌 굴리면서 더블카운팅하면 슥슥 풀리는 문제들이 있는다.(문제1 문제2, 대부분의 앳코더 문제들) 분명 쉬운 문제인데 이런 문제를 만들려고 하면 너무 자명하거나 못 푸는 문제가 되어버린다. 이 문제에도 적용을 해보았더니 순식간에 멋지게 풀렸다.

 

핵심은 스포를 위해서 가렸다. 풀이가 궁금하면 보자.

핵심은 이분화에 있었다. 문제를 쉽게 풀기 위해서 $c_i$를 0 또는 1, 2개의 경우로만 나누면 문제를 관리하기가 쉬워지는 것이다.

왜 문제가 순식간에 풀렸을까? 바로 내가 바보 자물쇠를 풀었기 때문이다. 형식만 다르고 풀이의 핵심 라인이 똑같다. 좋은 문제들을 잘 풀어 놓아서 사고방식을 머릿속에 심어놓으면 나중에 문제 출제는 아니더라도 써먹게 되는 것 같다. OI 문제들은 각 나라의 고인물들이 머리를 맞대고 만든 결과물이라서 챙겨먹는 편이다. 대학생이 되어서 OI판을 떠났더라도 풀어보자!

 

문제를 날먹해서 기분이 좋아져버린 나는 다항시간에 문제가 풀린다는 것만 확인하고 그대로 ucpc에 call for task를 했다. 문제를 풀기 위해 몇시간, 며칠씩 고민한 것이 아니라 문제를 만들고 얼마 안 있어서 푼 거 보면 운이 좋았다. 

 

여담으로 FFT를 적용해서 더 어려운 문제가 될 것 같기는 했다. 하지만 다항시간 풀이가 예쁜 문제에 FFT를 써야 할까? 라는 생각을 해서 심플하게 문제를 마무리지었다.

문제 승인

ucpc에 call for task를 했는데 결과는 보류였다. 선정이 안 될 줄 알고 서브태스크 대회에 $L_i=R_i$ 조건, $1 \leq L_i \leq R_i \leq 2$ 조건, 선형 트리 조건, 성게형 트리 조건 의 서브태스크들을 매겨서 사람들에게 즐거움을 줄 생각을 했다. 그런데 예상을 깨고 문제가 선정되었다! 서브태스크에 대한 상상은 그냥 던져버리고 ucpc에 내 문제를 내서 많은 사람들에게 신선하고 맛있는 앳코더 스타일 문제를 먹일 생각에 신이 났다.

문제 세팅

세팅은 쉬웠다. 평범한 문제고 코너케이스도 없고 어차피 가장 어려운 포인트가 다항시간에 있는 문제라서 순식간에 세팅했다. 답이 mod 998244353으로 0인 데이터도 만들까 했는데, 어떻게 만들지 모르겠어서 패스했다.

 

처음에는 $N$ 범위가 400이었다. $N^3$이 생각보다 느리다는 의견이 검수진들 중에 나와서 $N$ 범위를 250으로 줄였다. 수정된 제한을 보고 어떤 검수진이 "FFT 문제네"라고 해서 무척 슬펐다. $N^3logN$처럼 생긴 제한과 $998244353$ 때문이 아닐까 싶다.

 

검수 과정에서 검수진 분들이 내 문제를 열심히 풀어줘서 좋았다. 출제가 편해서 좋았던 것 말고, 누가 내 문제를 풀면 좋다. 실제로 ucpc의 어려운 문제들을 보면 문제를 푼 사람들의 집합이 (구사과님+출제/검수진)을 벗어나지 않는다. 구사과님은 그냥 모든 문제를 다 푼다.

본 대회

이 문제가 몇 명에게 풀릴지 생각을 했다. 이 문제가 제일 어려운 문제로 선정되었는데, 난이도 순서대로 보면

• 감옥의 예외케이스들을 꼼꼼하게 체크하면서 빠르게 풀어야 한다.
• 4색 정리에서 이상한 dp에 빠져서 200줄을 짜지 않아야 한다. (내가 검수할 때 그랬다)
• 러시안 회전초밥 문제를 풀기 위해서 sa와 lcp를 마스터해야 한다. 나처럼 문자열을 편식하지 않아야 한다.
• Distance sum maximization 문제를 푸는 과정에서 자구 뇌절을 하지 않아야 한다. (구사과님 팀은 자구 박았는데 뚝딱 풀긴 했다...)
• 스레드를 풀기 위해서 dp 식을 뚝딱 만들고 바로 FFT를 떠올려야 한다.

등등 앞의 문제들을 수월하게 지나가기가 너무너무 어렵다. 풀이를 작성하는 과정에서 이 문제가 단순히 핵심 아이디어만 떠올리면 되는 것이 아니라, 몇 개의 스텝을 밟아야 된다는 것을 보고 그냥 안 풀릴 줄 알았다. 약간의 희망은 이 문제의 구현이 (난이도에 비해) 간단하다는 것이다. 아무도 못 푸는 0솔브 문제가 될 운명이라는 것을 깨닫고 슬펐다.

 

완성된 문제지를 보니까 내 문제에 수식이 잔뜩잔뜩 적혀있었다. 그 이유는 내가 짧은 지문을 좋아하기 때문이다. 문제 읽는데 오래 걸리면 출제자도 힘들고, 지문 검수자도 힘들고, 참가자도 힘들다. 수식만 있어서 그런지 멋있는 문제처럼 보였다. 하지만 참가자들이 문제 제목을 읽고, 본문의 수식을 읽고, 버릴 문제처럼 생기기도 했다.

 

대회 내내 사람들이 내 문제를 안 푼다고 말하고 다니면서 슬퍼하고 있었는데, 구사과님이 풀어줬다! 바보 자물쇠 출제자인 구사과를 믿고 있었다. 내가 만든 문제인 One Two Three가 런 봄대회에서 안 풀려서 안타까웠는데, 누구 한 명이라도 내 풀어줘서 너무 좋았다. 구사과 팀이 2등으로 마무리 해서 킹메이커가 되지는 못했지만, 내 문제를 통해 흥미진진한 대회를 만들었기 때문에 아주 만족스러웠다.

 

대회가 끝나고 풀이를 진행했다. 내 풀이 슬라이드에 그림을 열심히 그려서 그런지 설명하기가 편했다. 풀이하기 전에는 200명 앞에 선다고 생각하니까  떨렸는데, 내가 열심히 만든 문제를 설명해서 그런지 별로 안 떨렸다. 

 

최종 후기

ucpc 문제를 푸는 사람들이 앞으로 한 번씩 내 문제를 구경할 것이라고 생각하니 뿌듯하다. 앞으로도 재미있는 대회에 내 문제들을 투척해서 사람들이 내 문제를 많이많이 풀게 해야겠다!