서론
예선 5문제 중 4문제, 본선 10문제 중 6문제를 출제했습니다. 다양한 문제를 출제한 만큼, 다양한 비하인드 스토리가 있습니다. 어떻게 문제 아이디어를 냈는지, 문제 세팅은 어땠는지 이 글을 통해 풀어보려고 합니다.
문제 풀이는 여기에 있습니다.
출제 방향
제1회(2017)부터 제4회(2020) 천하제일 코딩대회까지 문제 난이도가 정말 가파르게 상승했습니다. 제가 그 당시 출제진은 아니었지만, 매년 최상위권 팀들의 실력이 빠르게 상승해서 그들이 2시간 안에 다 풀고 3시간 동안 누워있는 일을 방지하려는 목적일 것이라고 추측하고 있습니다.
작년에 COVID-19 때문에 대회 참가자 수가 크게 감소했고, 심지어 본선 문제 난이도가 아주 많이 어려웠기 때문에 많은 학생들이 참가를 꺼릴 것 같다는 생각이 들었습니다. 그래서 올해는 초창기 천하제일 코딩대회처럼, 알고리즘을 공부하지 않았더라도 모두가 재미있게 풀 수 있는 문제를 만들기 위해 노력했습니다. 특히, 어려운 사전지식을 요구하는 문제가 2019-2020년에 비해 많이 감소했습니다. 그럼에도 불구하고 적절한 난이도의 문제들이 여러 개 만들어져서 다행이었습니다.
예선
예선 문제는 난이도 순서로 정렬하기로 결정했고, 이왕이면 문제 컨셉을 통일하고 싶었습니다. 원래 4문제가 출제된다면 선린인터넷고등학교 4개 과의 예전 이름인 정보통신과, 웹운영과, 테크노경영과, 멀티미디어과를 제목으로 하려고 했는데, 5문제라서 학교 교가로 컨셉을 정했습니다.
문제의 난이도 분포는 solvedac 기준 브론즈 2개, 실버 2~3개, 골드 0~1개로 미리 정하고 출제를 시작했습니다.
예선 A - 선린인터넷고등학교 교가
출제 계기
가장 쉬운 문제를 생각하던 도중, 선린 학생이라면 누구나 아는 선린의 털을 소재로 문제를 만들었습니다.
데이터 제작
뒤에서 5글자를 반대로 출력하는 풀이만 틀리게 만들면 별로 신경쓸 것이 없습니다. 랜덤 데이터로 충분합니다.
예선 B - 드높은 남산 위에 우뚝 선
출제 계기
산과 관련된 쉬운 문제는 뭐가 있을까요? 수열이 증가하다가 감소하는지 판별하는 것이 있겠네요!
제1회 논산 코드 페스티벌 C - 부모님께 큰절 하고라는 문제를 검수한 적이 있는데, 여기에서 “큰절”의 정의를 그대로 가져와서 어떤 수열이 산 형태인지 판별하는 문제를 출제했습니다.
데이터 제작
데이터를 랜덤으로 찍으면 높은 확률로 NO이기 때문에 큰일납니다.
랜덤 데이터, $A_i$가 모두 동일한 데이터, 무조건 YES인 데이터, 산 꼭대기가 왼쪽 끝/오른쪽 끝인 데이터를 만들었습니다.
예선 C - 중략
출제 계기
사실 D를 먼저 만들었습니다. D를 만들고 나니, C번 문제의 제목을 송백은 흰 눈및에 푸르고 ... 울려라 삼천리의 힘차게로 할 수는 없어서 (중략)으로 결정했습니다.
제목을 중략으로 정했기 때문에 문자열 관련 문제를 만드는 것이 좋고, solvedac 기준 실버가 되어야 하기 때문에 적당히 복잡한 casework를 요구하는 문제를 만들어야 했습니다. 그렇게 해서 3가지 경우를 열심히 casework하는 문제가 탄생했습니다.
데이터 제작
랜덤으로 찍어도 별 상관 없을 것 같지만, 혹시 몰라서 전체가 한 문장인 데이터, a.a.a.a.가 반복되는 데이터, 콤마가 많이 나오는 데이터를 추가했습니다.
2번째 예제가 매우 섬세합니다. 2번째 예제를 줄지 말지 많이 고민했는데, 안 주면 대회가 망할 것 같아서 넣었습니다. 그래서 그런지 한 번에 맞춘 학생들이 많았습니다.
예선 D - 세워라 반석 위에
출제 계기
반석을 구글에 검색해보니 “넓고 펀펀한 큰 돌”이라고 하네요. 마침 실버 중위권 단골 소재로 투포인터가 있기 때문에, 투포인터를 사용해서 풀 수 있는 간단한 문제를 만들었습니다.
근데 검수진들이 더 멋진 풀이를 가져왔네요. 이제부터 그게 정해입니다.
데이터 제작
데이터를 대충 만들면 $O(N^3)$도 뚫리는 기적의 문제라서 데이터 만드는데 고생을 많이 했습니다. $A_i$가 항상 123 중 하나라서 정답이 $N$인 데이터, 입력의 0.0001%만 4이고 나머지는 123 중 하나인 데이터 등을 만들어서 넣었습니다.
Naive를 짜면 $O(N^3)$, Naive에 Segment Tree를 섞으면 $O(N^2 \log N)$, Parametric Search에 Segment Tree를 섞으면 $O(N \log^2 N)$, Parametric Search에 Sparse Table을 섞으면 $O(N \log N)$, 투포인터에 Segment Tree를 섞으면 $O(N \log N)$, 정해는 $O(NX)$입니다. 로그 제곱은 터뜨리고, $O(NX), O(N \log N)$은 통과시키도록 데이터를 만들었습니다.
대회 끝나고 SIMD로 $O(N^2/32)$를 테스트해봤는데 다행히(?) 잘 막혔습니다.
예선 E - 선린의 터를
wookje님이 문제를 들고 오셨고, 문제 세팅은 제가 했습니다.
데이터 제작
데이터는 대충 만들어도 됩니다. 혹시 몰라서 모든 수가 $2^{36}$ 이상인 데이터, 모든 수의 popcount가 34 이상인 데이터를 추가로 넣었습니다.
본선
지금까지 UniCon, UCPC, BOJ 연말 대회 등 여러 대회 출제에 참여하면서 다양한 이유로 대회에 내지 못한 문제가 여러 개 쌓여있는 상황이었습니다. 언제 다 비울까 고민하고 있었는데, 본선 대회에 6문제를 내면서 출제 큐(Queue)에 들어있는 문제들을 거의 다 비웠습니다. 아직 큐에 들어있는 문제 중 일부는 선린 정올에 나올 예정입니다. 많은 기대 부탁드립니다!
예선 상태를 보니 solvedac 기준 실버 문제를 겨우 푸는 학생이 대다수인 것 같아서, 작년에 비해 브론즈/실버 비율을 늘렸고, 다이아몬드 수준의 문제를 아예 출제하지 않았습니다.
구체적으로, 플래티넘 수준의 문제 1~2개 넣고, 나머지는 골드와 브론즈~실버를 비슷한 비율로 출제했습니다. 목표는 좌셋(모든 팀이 1솔브 이상, 모든 문제들이 한 번 이상 풀림, 모든 문제를 다 푼 팀이 없음)입니다.
본선 A - 3초 정렬
junie님이 출제하신 문제입니다.
본선 B - Conv1d
leejseo님이 출제하신 문제입니다.
본선 C - k개의 부분 배열
chansol님이 출제하신 문제입니다. 대회 1주일 전에 한 문제가 부족해서 터지기 직전인 대회를 살려주셨습니다. 감사합니다.
원래 chansol님이 들고 온 문제는 $k$가 주어지면 가능 여부를 판별하는 문제였는데, 출제자가 너무 쉬운 것 같다고 걱절하길래 제가 가능한 가장 작은 $k$를 구하는 문제로 바꿨습니다. 풀이는 똑같지만, 몇몇 팀을 Parametric Search라는 잘못된 풀이로 유도할 수 있는 효과를 얻을 수 있습니다.
본선 D - 가장 쉬운 문제를 찾는 문제
출제 계기
본선은 난이도 순서대로 정렬되어 있지 않지만, 이것을 인지하지 못한 몇몇 팀은 앞에서부터 풀다가 대회를 망치는 경우를 여러 번 보았습니다. 작년에 대회 현장 스태프를 하면서, 제가 문제를 출제하면 이를 알려주려고 다짐했고, 공지보다는 문제 지문을 통해 간접적으로 알려주는 것이 좋을 것 같아서 출제했습니다.
이 문제는 본선 문제 셋이 난이도 순서대로 정렬되어 있지 않다는 점을 알려주고, 대회에 참가한 팀이 최소한 한 문제는 풀도록 하려는 목적으로 만들었습니다.
데이터 제작
길이가 1, 2, 3, 4인 모든 순열을 넣었습니다. 문제 이름은 별로 중요하지 않기 때문에, 예제를 제외한 모든 테스트 케이스에서 string name[4] = { "ABCDEFGHIJ", "ABCDEFGHIK", "ABCDEFGHIL", "BBBB" };로 통일했습니다.
본선 E - 구름다리
출제 계기
작년 8월쯤 Centroid Decomposition을 갖고 놀다가 떠올린 문제입니다. 물론 문제 풀이는 Centroid와 전혀 관련이 없습니다.
초기 버전은 모든 경로의 길이가 $\lceil \log N \rceil$이하가 되도록 만드는 문제였습니다. 이는 트리에서 Centroid Decomposition을 하면서 분할 정복 과정을 트리로 만들면 됩니다.
하지만 조금 더 생각을 해보니 더 쉽고 항상 최적해를 찾을 수 있는 풀이를 찾게 되었습니다. 결론만 말하면, $N \leq 4$이면 1로 만들 수 있고, $N > 4$면 무조건 2입니다.
원래 Good Bye BOJ 2020에 출제하려고 했지만, 이미 트리/그래프 문제가 많이 있어서 출제하지 못했습니다.
데이터 제작
Prufer Sequence를 이용해 $N = 2, 3, 4$일 때 나올 수 있는 모든 $2^{2-2} + 3^{3-2} + 4^{4-2}$가지 트리를 넣었습니다. $N > 4$인 데이터는 좋은 생각이 안 나서 랜덤 데이터만 넣었습니다.
스페셜 저지는 Floyd-Warshall Algorithm을 이용합니다.
난이도가 문제 풀이 < 체커 < 데이터 제너레이터인 재밌는 문제였습니다.
본선 F. 균형
출제 계기
2019년 여름에 만든 문제라서 어떻게 만든 문제인지 기억도 안 납니다.
2019년 9월에 열린 UniCon, 2019년 12월에 열린 Good Bye BOJ 2019, 2020년 12월에 열린 Good Bye BOJ 2020까지 총 3개의 대회에서 거절당한 비운의 문제입니다. 올해 천하제일 코딩대회는 제 마음대로 할 수 있어서 넣었습니다.
문제가 안 좋아서 거절당한 건 아니고, E-구름다리와 마찬가지로 이미 트리/그래프 문제가 많이 있어서 거절당했습니다.
데이터 제작
랜덤 데이터 / 큰 데이터 / 정답이 바뀌는 지점 ± 2 지점만 주는 데이터, 총 3가지 종류의 데이터를 넣었습니다. 데이터 만들기 쉬워서 좋았습니다.
본선 G. 대나무숲
출제 계기
빡구현 문제를 만들고 싶었고, 이제는 없어진 선린인터넷고등학교 대나무숲이 생각나서 이런 문제를 만들게 되었습니다. 문제 만들고 생각을 해보니 casework가 상당히 귀찮은 문제인 것 같습니다. 다만 예제가 굉장히 친절하게 주어져 있어서 한 번에 맞추는 건 어렵지 않은 것 같습니다.
데이터 제작
이미 저격 데이터는 예제에 다 있어서 별로 신경쓸 것이 없었습니다.
일단 트리 문제니까 Star Graph / Skew Tree를 넣고, 지름이 매우 긴 트리도 몇 개 넣었습니다.
본선 I - 문제 재탕
출제 계기
올해 예선 대회가 끝나고 운영진 몇 명과 밥 먹다가 생각한 문제입니다. 문제 지문에서 예선 문제를 언급하고 있지만, 예선 문제처럼 투포인터로 풀면 오히려 말릴 수 있습니다.
데이터 제작
증가하는 수열, 감소하는 수열, 산이 하나만 있는 수열, 랜덤 데이터를 넣었습니다.
본선 J - 증가하는 부분 수열의 개수
출제 계기
원래 스위핑 + 위상 정렬 + DP을 섞은 문제로 Good Bye BOJ 2019에 출제하려고 했지만, 모 대회 기출과 겹쳐서 나오지 못한 문제입니다. 문제를 약간 바꾸니 쉽고 간단한 문제가 되어서 천하제일 코딩대회에 출제하게 되었습니다.
데이터 제작
놀랍게도 I-문제 재탕과 데이터가 똑같습니다. 날먹 
본선 K - 테러
junie님이 출제하신 문제입니다. 원본 문제는 조금 다른데 너무 어려워서 2~3번 정도 너프시켰습니다.