서론
지난 2년간 온라인으로 진행되었던 천하제일 코딩대회가 3년 만에 오프라인으로 돌아왔습니다. 코로나로 인해 멈춰있던 학교 행사의 시작을 함께 하게 되어서 영광이었습니다.
작년에는 단순히 문제만 만들면 됐지만 올해는 오프라인 대회이기 때문에 문제지, 풍선, 자리 배치 등 신경 써야 할 요소가 많았습니다. 그럼에도 불구하고 잘 따라와 준 다른 출제진, 현장에서 열심히 힘을 써준 후배님들과 학교 선생님들께 이 자리를 빌려 감사하다는 말씀 전하고 싶습니다.
저는 예선 5문제 중 1문제, 본선 10문제 중 3문제를 출제했습니다. 그 외에도 여러 잡다한 일을 했는데 이 글을 통해 하나씩 풀어보려 합니다.
대회 준비
고등학생 때 가장 즐겁게 참여했던 대회인 만큼, 이번에 참가하는 학생들도 재밌게 대회를 치를 수 있는 환경을 조성하는데 많은 노력을 기울였습니다.
작년과 마찬가지로 어려운 사전 지식을 요구하는 문제는 최대한 배제하고, 알고리즘을 공부하지 않았더라도 모두가 재미있게 풀 수 있는 문제를 목표로 출제했습니다. 오랜만에 오프라인 대회로 열리는 만큼, 많은 학생들이 즐거운 경험을 하고 그 경험을 바탕으로 문제 풀이에 흥미를 가졌으면 하는 작은 바람이 있었습니다.
개발을 주로 공부하는 학생들은 C++에 익숙하지 않기 때문에 C++, JAVA, Python, Javascript로 모든 문제를 해결할 수 있음을 보장했습니다. 4가지 언어로 코딩해야 돼서 해야 할 일이 4배가 되었지만… 대회가 잘 마무리되었으니 저는 만족합니다. 4가지 언어로 작성된 정답 코드는 여기에서 볼 수 있습니다.
천하제일 코딩대회는 ICPC처럼 3명이 한 대의 컴퓨터만 사용하는 대회이기 때문에 문제지를 따로 출력해서 배부해야 합니다. 3년 전에는 단순히 BOJ 화면을 출력했지만, 올해는 조금 더 높은 퀄리티의 문제지를 만들고 싶었습니다. 그래서 $\LaTeX$로 문제지를 직접 조판했습니다. 원래는 문제지 표지 디자인 외주를 맡기고 싶었지만 너무 늦게 알아보기 시작해서 맡기지 못했습니다. 문제지는 여기에서 볼 수 있습니다.
문제 해설을 위한 풀이 슬라이드도 만들어야 합니다. 풀이 슬라이드는 작년과 마찬가지로 UCPC 2020 beamer 테마를 사용했습니다. 출제자들이 문제 풀이를 미리 요약해 준 덕분에 편하게 제작할 수 있었습니다. 풀이 슬라이드는 여기에서 볼 수 있습니다.
예선
예선 문제는 작년과 비슷한 난이도로 출제했고, 난이도 순으로 정렬해서 참가자에게 제공했습니다. 5문제가 출제되었으며, 저는 1문제를 출제하고 모든 문제를 세팅(지문 작성, 데이터 제작 등)했습니다. 다른 출제진들은 모두 후배라서 일을 떠넘길까 고민했지만(…) 그냥 제가 하는 게 빠를 것 같아서 제가 전부 했습니다.
작년 예선은 30분 만에 5문제를 모두 만들었는데 벌써 에이징 커브가 왔는지 올해는 문제 아이디어가 잘 나오지 않았습니다. 작년보다 더 열심히 고민했는데 더 재미없는 문제가 나와서 슬펐습니다.
예선 A - 심준의 병역판정검사
처음에는 누가 키(key 말고 height) 갖고 뭔가 하는 문제를 가져왔습니다. 너무 재미없어서 폐기할까 고민했는데 wesley2003이 병역판정검사 스토리를 붙여서 문제를 살려냈습니다. 원래 입력 범위는 최대 1000이었는데 float로 bmi를 계산하면 실수 오차가 발생해서 200으로 줄였습니다. 입력 범위가 작아진 덕분에 채점 데이터에 가능한 모든 데이터를 넣을 수 있었습니다.
w/(h/100)/(h/100), w/h/h*100*100, w*10000/h/h, w/(h/100*h/100), w/(h*h)*100*100, w*10000/(h*h) 등 창의력을 발휘해서 참가자들이 시도할 것 같은 모든 방법을 이용해 float 범위에서 통과하는 것을 확인했는데, 대회 중에 한 참가자가 double로 틀려서 당황스러웠습니다…
예선 B - 11월 11일
저는 $m$일 전을 naive하게 계산했는데 출제자가 더 똑똑한 방법을 알려줬습니다. Python의 datetime 패키지, Javascript의 Date 객체를 이용해서 해결할 수도 있습니다. 이 문제도 입력의 범위가 작기 때문에 가능한 2100×12개의 데이터를 모두 넣었습니다.
예제를 친절하게 주기 위해서 노력했습니다. 400의 배수라서 윤년인 해(2000년), 400의 배수가 아니지만 윤년인 해(2012년), 100의 배수라서 윤년이 아닌 해(2100년), 그냥 윤년이 아닌 해(2022년)을 모두 예제에 넣었습니다. 그래도 정답률이 낮은 거 보면 예제를 더 넣었어야 했나… 잘 모르겠습니다.
예선 C - 순열 정렬
그리디 하게 하면 쉽게 해결할 수 있는데 DP로 푼 학생이 많아서 놀랐습니다. 데이터를 만드는 게 조금 귀찮았는데, 일단 길이가 7 이하인 모든 순열을 다 넣고 항상 YES인 순열도 몇 개 넣었습니다. 나머지는 랜덤으로…
원래 입력 제한이 50만이었는데 Python이랑 Javascript가 입력도 못 받고 죽어서 5만으로 줄였습니다. 사실 5만으로 줄이는 것만으로는 안 되길래 시간제한도 3초로 늘렸습니다. 어휴…
예선 D - 영어 시험
De Bruijn Sequence를 공부하다가 substring 대신 subsequence 조건을 넣으면 쉬운 것 같아서 만든 문제입니다. 데이터 만드는 것도 쉽고 스페셜 저지 작성도 쉽고 풀이 작성도 쉬운 꿀문제입니다. 대회 끝나고 여러 사람들이 재미있다고 해줘서 기뻤습니다.
예선 E - 가장 긴 등차 부분 수열
여러 가지 풀이가 있고, 출제 과정에서는 $O(NX \log X)$, $O(NX)$ 풀이가 나왔습니다. 두 풀이 모두 좋은 풀이 같아서 둘 다 통과할 수 있도록 데이터를 만들었습니다. 덕분에 4가지 언어로 $O(NX), O(NX\log X), O(N^2)$ 풀이를 작성하는 개고생을 했습니다. 대회 중에는 $O(X^3), O(X^2 \log X)$ 같은 풀이도 나왔습니다.
본선
예선 결과가 생각보다 좋지 않아서 작년보다 더 쉽게 출제했습니다. 다만 작년처럼 대놓고 쉬운 문제가 없어서 상위권을 제외한 팀들이 초반에 헤맨 것 같습니다.
1등팀이 2시간 만에 다 풀고 자는 건 막고 싶어서 의도적으로 코딩이 귀찮은 문제도 몇 개 넣었습니다. 상위권이 다 풀고 자는 거 막겠다고 어려운 문제로 도배하면 다른 팀들이 고생하기 때문에, 귀찮은 문제와 어려운 문제 각각 한 두 문제씩 넣는 걸로 만족했습니다.
저는 10문제 중 3문제(DGI)를 출제했고, 5문제(DGHIJ)를 세팅했습니다. 작년에는 미리 쌓아놓은 문제가 많아서 여유롭게 작업했는데, 올해는 이미 1학기에 20문제 가까이 출제해서 아이디어가 바닥났습니다. 급하게 출제하느라 별로 재미있는 문제를 만들지 못해 아쉬웠습니다.
본선 A - Gravity Hackenbush
hackenbush 게임에 중력을 추가한 게임입니다. 무서워 보이지만 문제를 천천히 읽으면 쉽게 풀 수 있는 문제고, 실제로 많은 팀이 풀었습니다. 원래 입력 제한이 200만이었는데 Python과 Javascript가 입력받다가 죽어서…
나정휘(jhnah917)와 난정휘(jhnan917)가 게임하는 문제였는데, 대회장에서 참가자들이 제 이름을 외치며 괴로워하는 것을 보니 기분이 이상했습니다.
본선 B - K-균형 잡힌 수
가장 어려운 문제를 의도하고 만든 문제입니다. 올솔브를 지연시킬 목적으로 만들었는데 목적을 잘 달성한 것 같습니다.
본선 C - Merge the Tree and Sequence
원래 Split the SSHS 문제와 Split the GSHS의 후속작인 Merge the SSHS and GSHS라는 이름으로 출제될 예정이었지만, 교내 대회 참가자들은 저 스토리를 모르기 때문에 눈물을 머금고 제목을 교체했습니다. 검수하면서 제가 가장 재밌게 푼 문제입니다.
본선 D - 바지 구매
가장 쉬운 문제를 의도하고 만든 문제입니다. 원래는 문제가 조금 달랐었는데, 가장 쉬운 문제 치고는 너무 어려운 것 같아서 3~4번 정도 너프시켰습니다.
본선 E - 반전 수와 쿼리
크기가 $N$인 배열을 만들지 않고 해결할 수 있음을 알려주기 위해 $N$의 범위를 $10^9$로 줬는데, PS에 익숙하지 않은 학생들이라 그런지 크기가 $10^9$인 배열을 만드는 팀이 많이 보였습니다. $N \leq 10^{100}$으로 했어야 하나… 라는 후회를 하고 있습니다. 본선 문제 중 가장 좋은 문제라고 생각합니다.
본선 F - 시간딱딱충
원래는 구현이 귀찮은 문제를 의도하고 만들었는데, 어쩌다 보니 구현은 깔끔하고 지문이 어지러운 문제가 되었습니다. 지문이 무섭게 생겨서 늦게 풀릴 줄 알았는데 대회 시작 23분 만에 풀려서 놀랐습니다.
출제자는 대회에서 3번째로 빨리 풀렸고, 정답률(1제출 1AC, 100%)이 가장 높기 때문에 쉬운 문제라고 주장하던데… 저는 잘 모르겠습니다.
본선 G - 인공 신경망
원래 작년 천하제일 코딩대회에 나올 예정이었지만 Conv1D에게 자리를 뺏겨서 올해 나오게 되었습니다. 중학생 때 신경망을 공부하면서 왜 activation function을 넣어야 하는지 의문을 가졌었는데, 그때의 기억을 되살려서 만든 문제입니다.
신경망 전체를 퍼셉트론 하나로 압축하는 문제인데, naive한 풀이로 시도하는 팀들이 많아서 안타까웠습니다.
본선 H - 최대 최소공배수
구글에 maximize lcm of three numbers 처럼 검색하면 바로 풀이가 나오는 문제입니다. 검색이 허용되는 대회라서 쉽게 풀라고 낸 문제인데, 많이 안 풀려서 당황스러웠습니다. 대회장을 돌아다니면서 보니 한글로 검색하는 팀은 몇 팀 있었는데 영어로 검색하는 팀이 없는 것 같았습니다. 문제 해설할 때 검색의 중요성을 강조했습니다.
본선 I - 최장 최장 증가 부분 수열
원래 2D Segment Tree 쓰는 문제로 선린 정보 올림피아드에 낼 생각이었지만, 너무 재미없는 것 같아서 간단한 DP로 풀 수 있도록 $O(N^4)$로 너프하고 천하제일 코딩대회에 출제했습니다. 더 어려운 DP 문제인 예선 E를 푼 사람이 꽤 있어서 많이 풀릴 줄 알았는데 많이 안 풀려서 슬펐습니다.
본선 J - 행성 정렬
쉬운 문제로 만들고 싶어서 입력 제한을 정할 때 많은 고민을 했습니다. 가능한 풀이로는 유클리드 호제법($O(N \log X)$), 소인수 분해($O(N \sqrt X)$), 브루트포스($O(NX)$) 등이 있는데, 많은 고민 끝에 유클리드 호제법과 소인수 분해만 통과시키는 방향으로 제한을 정했습니다. 근데 다들 유클리드 호제법으로 잘 푼 거 보면… 괜한 고민을 한 것 같습니다.
마무리
2주 동안 쉬지도 못하고 일만 했습니다. 지금까지 대회만 40번 넘게 운영했는데, 가장 힘들었던 대회 3개를 선택하라고 하면 주저하지 않고 이 대회를 선택할 것 같습니다. 그만큼 대회에 큰 애정을 갖고 있다고 받아들이면 좋을 것 같습니다.
이걸 내년에도 해야 한다는 걸 생각해 보면 눈앞이 깜깜해지는데… 그건 1년 뒤의 저에게 미뤄두고 지금은 잠시 휴식을 취하려고 합니다. 사실 다음 학기에 선린 정보 올림피아드도 출제해야 합니다.
저와 같이 대회 문제 작업을 한 출제진과 검수진, 대회 현장에서 열심히 힘써주신 후배들과 선생님들, 그리고 대회와 오픈 콘테스트에 참여해 주신 많은 분들, 정말 감사드립니다.
끝!