2022 SKKU 프로그래밍 대회 in 소프트의 밤 출제

2022 SKKU 프로그래밍 대회 in 소프트의 밤에 문제를 출제했다 (대회 문제, 풀이 슬라이드). 이전에 SW마에스트로 제13기 알고리즘 대회에 문제를 출제한 적이 있어서 Polygon과 같은 도구는 사용해 본 적이 있었지만 백준에서 대회를 연 것은 처음이라 새로운 경험이었다. 내가 출제한 문제는 총 세 문제로 E. 수열의 합, J. 달나라에 사는 토끼와 우주에서 떨어지는 떡, K. 커모드 곰의 연어 사냥을 출제하였다.

출제

E. 수열의 합

대회에 간단한 수학 문제가 있으면 좋을 것 같아서 만든 문제이다.

아이디어를 얻기 위해 고등학교 수학 I 문제집을 살펴보다가 $a_n = \left(-1\right)^{d_1} + \left(-1\right)^{d_2} + \cdots + \left(-1\right)^{d_k}$의 성질을 묻는 문제를 찾았다. ㄱ,ㄴ,ㄷ이 주어지고 "$n = {10}^{m}$이면 $a_n=m^2-1$이다"와 같은 명제가 참인지 거짓인지 판단하는 문제였다. $a_n$을 가지고 문제를 만들 수 없을까 생각을 하다가, $a_n$의 성질을 활용하는 문제보다는 간단하게 $a_1 + a_2 + \cdots + a_N$을 묻는 문제를 내면 좋을 것 같다는 생각이 들었다. 식을 정리해보니 $\sum_{i=1}^{N}{a_i}=\sum_{i=1}^{N}{\left(-1\right)^{i}\lfloor\frac{N}{i}\rfloor}$를 얻을 수 있었다. $\sum_{i=1}^{N}{\lfloor\frac{N}{i}\rfloor}$를 $\mathcal{O}\left(\sqrt{N}\right)$에 구하는 문제는 AtCoder, Codeforces, 타 대학교 프로그래밍 대회에서 각각 한 번씩 본 적이 있었기에 $\sum_{i=1}^{N}{a_i}=\sum_{i=1}^{N}{\left(-1\right)^{i}\lfloor\frac{N}{i}\rfloor}$를 $\mathcal{O}\left(\sqrt{N}\right)$에 구하는 문제를 내면 적당하겠다는 생각이 들었다. 이렇게 $1 \le S \le T \le {10}^{14}$에 대해 $\sum_{i=1}^{N}{a_i}$를 묻는 문제를 작성하였다.

이 문제의 경우 풀이가 많이 존재한다. 우선 $\mathcal{O}\left(N^2\right), \mathcal{O}\left(N\sqrt{N}\right), \mathcal{O}\left(N\lg{N}\right), \mathcal{O}\left(N\right), \mathcal{O}\left(\sqrt{N}\right)$ 풀이를 생각하고 출제를 진행했다. 각각의 풀이는 풀이 슬라이드에서 확인할 수 있다. 대회 이후에 알게 된 사실인데 $\mathcal{O}\left(N\lg{\lg{N}}\right)$ 풀이도 있다고 한다.

마침 작년에 진행된 대회보다 많은 문제를 출제하면 좋겠다는 이야기가 나왔어서 Small과 Large로 문제를 출제해도 좋겠다고 생각했다. 그래서 $1\le S \le T \le {10}^{5}$인 Small은 $\mathcal{O}\left(N\sqrt{N}\right)$에 해결할 수 있고 $1\le S \le T \le {10}^{14}$인 Large는 $\mathcal{O}\left(\sqrt{N}\right)$에 해결 할 수 있도록 문제를 작성하였다.

수열의 합 초안.pdf

57.6 kB

대회에 출제할 문제를 고르는 과정에서 Small과 Large를 모두 출제하기 보다는 $\mathcal{O}\left(N\right)$ 풀이까지만 허용해서 실버 상위에서 골드 하위의 문제 하나를 출제하기로 결정이 되었다. 그러나 실제로 코드를 작성해 보니 $\mathcal{O}\left(N\lg{N}\right)$ 풀이를 막는 것이 어려워 보였다. 내가 작성한 $\mathcal{O}\left(N\lg{N}\right)$ 코드의 경우 메모리를 많이 사용하는 풀이의 경우 TLE를 받았지만 배열을 사용하지 않는 것 만으로 AC를 받을 수 있었다. 심지어 AC를 받은 코드의 경우 $\mathcal{O}\left(N\right)$ 풀이보다 실행 시간이 짧았다. 이는 검수때도 마찬가지여서 빠른 $\mathcal{O}\left(N\lg{N}\right)$ 풀이까지 허용하게 되었다.

이번 대회에 작년보다 많은 문제를 냈던 이유는 다양한 사람이 모두 프로그래밍 대회를 즐길 수 있기를 원해서였고, 이 문제는 많은 사람이 풀어주기를 바라는 마음으로 출제한 문제였다. 실제로 대회에서 많은 사람이 이 문제를 즐겁게 푼 것 같아서 제한을 $10^7$으로 조정해서 출제하기를 잘한 것 같다. 하지만 처음부터 $\mathcal{O}\left(\sqrt{N}\right)$ 풀이를 생각하고 만든 문제였기에 아무래도 아쉬움이 남았다. 그래서 제한이 ${10}^{14}$인 문제를 개인적으로 출제하기로 했다. 해당 문제는 검수 중에 있고 수열의 합 2라는 이름으로 백준에 올라갈 예정이다.

J. 달나라에 사는 토끼와 우주에서 떨어지는 떡

Functional Graph 위의 토끼들의 이동을 한꺼번에 처리해주어야 하는 문제이다.

이 문제를 풀기 위해 알아야 하는 알고리즘은 사이클 판별과 토끼의 이동을 처리하기 위한 DFS/BFS, 사이클 안에서의 토끼의 이동을 계산하기 위한 누적합 배열 정도이다. 문제를 해결하기 위한 아이디어는 떡이 사이클에 떨어지는 경우와 사이클에 떨어지지 않는 경우로 구분하여 토끼의 이동을 한꺼번에 처리할 수 있다는 것이다. 문제를 풀기 위해 필요한 알고리즘과 아이디어의 난이도를 생각했을 때 골드 정도의 난이도로 출제하면 좋겠다는 생각으로 만든 문제였다. 대회에 출제할 문제를 결정할 때 다른 출제진들 역시 골드 상위에서 플래티넘 하위 정도의 난이도를 예상했다.

그러나 실제로 코드를 작성해 보니 구현이 생각보다 까다로웠다. 검수 과정에서 예상보다 높은 난이도를 받게 되었고, 아이디어는 떠올리지만 구현에 말려서 대회에서 이후 문제를 풀지 못하는 사람이 생길 수 있다는 의견이 있어서 원래 배치하려고 했던 위치보다 많이 뒤로 밀려나 J번 문제가 되었다. 실제로 문제가 백준에 올라간 후에 플래티넘 2의 난이도를 받았다.

E. 수열의 합은 문제도 짧고 구현량도 적은 문제를 목표로 만든 문제이다. 반면 J. 달나라에 사는 토끼와 우주에서 떨어지는 떡은 긴 지문과 약간 복잡한 구현을 목표로 만든 문제이다. J번의 구현량이 생각보다 많기는 했지만, 두 문제가 의도한 대로 대비를 잘 이루는 것 같아 마음에 들었다.

관련 문제로는 Planets Queries II가 있다.

K. 커모드 곰의 연어 사냥

이 문제는 캐나다의 유령곰 가족이라는 다큐멘터리를 보고나서 만든 문제이다. 커모드 곰은 아메리카 흑곰의 아종인데 대부분 검은 색이지만 알비노가 아님에도 흰 색인 곰이 있다. 실제로 위 다큐멘터리에서는 어미곰은 흰 곰이지만 새끼들은 검은 곰이다. 뿐만 아니라 두 검은 곰 사이에서 흰 곰이 나올 수도 있고, 형제자매지만 색이 다른 경우도 있다.

이전에 ABC 266에서 Well-defined Path Queries on a Namori라는 문제를 풀었는데 문제의 제약 조건 때문에 사이클만 찾으면 되는 문제였지만 대회 당시에는 생각이 나지 않아서 Heavy-light Decomposition과 단절선을 사용해서 문제를 해결했다. 대회가 끝나고 나서 단절선을 이용하면 해당 문제보다 일반적인 그래프에 대해서도 경로의 유일성을 판단할 수 있다는 것을 알게 되었다. 이 아이디어를 사용해서 문제를 만들면 좋을 것 같았고 그래프 위의 토토로라는 제목의 문제를 만들었다.

그래프 위의 토토로.pdf

88.1 kB

이 문제는 처음에는 SW마에스트로 알고리즘 대회에 출제될 예정이었는데 난이도 조절 과정에서 출제 목록에서 제외되었다. 그러다가 최단 경로를 구하는 것보다 게임 이론을 섞으면 재미있는 문제가 될 것 같다는 생각이 들어서 커모드 곰의 연어 사냥 문제를 만들게 되었다. 마침 solved.ac에서 찾아보니 단절선과 게임 이론 태그가 모두 붙어 있는 문제는 없는 것 같아서 성균관대 프로그래밍 대회에 내도 좋겠다고 생각했다.

나름 참신한 문제라고 생각했으나 단절선과 스프라그 그런디 정리를 알고 있다면 어렵지 않게 떠올릴 수 있었던 것 같다. 그럼에도 여전히 마음에 드는 문제이다.

검수

A. 안녕 클레오파트라 세상에서 제일가는 포테이토칩

원형으로 앉아서 진행하는 게임을 반복문으로 구현하여 해결 할 수 있는 문제이다. A번으로 출제하기에 적절한 문제라고 생각한다.

B. 장인은 도구를 탓하지 않는다

식을 정리해보면 곱셈의 교환법칙에 의해 순서는 중요하지 않다는 것을 알 수 있다. 가장 작은 $p_i$를 $k$라고 할 때 답은 $\frac{{10}^9}{9!k}\prod_{i=1}^{10}{p_i}$이다. 입력 제한이 작기 때문에 고민 없이 모든 경우의 수를 다 따져보아도 해결할 수 있는 문제이다.

C. 수렵의 시간이다!

브루트포스로 해결할 수 있는 문제이다. 그러나 조건이 약간 복잡하고 구현량이 많아서 실수를 하기 좋은 문제라고 생각한다. 실제로 대회에서도 사람들이 구현에 시간이 오래 걸릴 것이라고 생각했는지 C번을 건너뛰고 다음 문제를 푸는 사람이 많았다.

D. 양과 늑대

인터랙티브 문제이다. 인터랙티브라는 단어와 질문을 최대 20번 할 수 있다는 조건을 보면 이분 탐색일 것 같다는 생각이 든다. 실제로 이분 탐색을 통해 해결할 수 있는 문제이지만 흥미로운 점은 함수가 증가 함수 또는 감소 함수가 아니라는 점이다. 그럼에도 사잇값 정리와 같은 느낌으로 $\mathcal{O}{\left(\lg{N}\right)}$번의 질문을 통해 답을 구할 수 있다.

F. 수확의 계절이다!

매개 변수 탐색 문제이다. (위치, 시각)을 기준으로 정렬해서 전처리를 해두면 해당 배열을 훑어보는 것만으로 빠르게 답을 계산할 수 있다.

G. 게이트웨이 정하기

처음에는 Rerooting DP로 접근했다. 식을 잘 정리해보니 임의의 정점을 루트로 정해서 계산해놓으면 다른 정점이 루트인 경우에 대해서는 $\mathcal{O}\left(1\right)$에 구할 수 있다는 것을 알 수 있었다. Rerooting DP로 구하는 것과 시간복잡도에 차이는 없지만 앞의 성질을 이용해서 구현하는 것이 간단하다. XOR 연산에 대해 서로 다른 자리의 비트는 독립이라는 것을 고려하면 좋다.

H. 현상금 헌터

DP 문제이다. 이 문제를 해결하기 위한 중요한 아이디어가 있는데 이를 떠올리기가 어렵다고 생각한다. 또한 문제에 무지는 언제나 동서남북 중 원하는 방향으로 방향을 바꿀 수 있다고 나와 있는데 그렇다면 대각선으로 이동할 수 있다는 생각이 들었다. 그러나 방향은 $90$도로만 바꿀 수 있기 때문에 극한을 취해서 계산해도 거리는 항상 맨해튼 거리로 계산된다.

I. 전투 시뮬레이션

머지 소트 트리 또는 오프라인 쿼리와 세그먼트 트리로 해결할 수 있는 문제이다. 나는 머지 소트 트리 대신 Wavelet Matrix를 사용해서 구현했다.

마무리

큰 문제 없이 대회가 잘 마무리 된 것 같아서 다행이다. 대회 출제자, 검수자, 참가자 및 도움을 주신 모든 분들께 감사하다는 말씀을 드리고 싶다. 처음 알고리즘 공부를 시작했을 때는 대회에 문제를 출제하게 될 것이라고 생각도 못했는데 대회에 출제진으로 참여하고 있는 것을 보니 감회가 새롭다. 문제를 푸는 것도 좋지만 새로운 문제를 만드는 것 또한 꽤나 즐거운 일인 것 같다. 그럼에도 문제를 만드는 것이 쉬운 일은 아니라고 생각한다. 지문을 작성하고 데이터를 만드는 과정 역시 쉬운 것은 아니지만 좋은 문제를 생각해 내는 것이 가장 어려운 것 같다. 다음에 다시 출제를 하게 된다면 충분히 고민하다가 아하 하고 깨달으며 즐겁게 풀 수 있는 문제를 만들고 싶다.