서론
3달 동안 준비한 숭고한 연합 알고리즘 대회가 드디어 끝났습니다. 저는 Div.1의 가장 어려운 문제, Div.2의 두 번째로 어려운 문제, Div.3의 가장 어려운 문제를 출제하고, 문제의 선제와 검수를 총괄했습니다. 대회 종료 후 풀이 방송도 담당했습니다.
올해 초에 대회 준비를 시작할 때부터 주변 지인들에게 때려치우고 싶다고 1시간에 한 번씩 징징거렸는데 대회가 끝나고 나니 속이 후련하네요.
운영진에 합류하게 된 과정부터 대회 풀이 방송까지, 여러 가지 이야기를 풀어보도록 하겠습니다.
운영진 합류
원래 이 대회는 2월에 개최될 예정이었고, 저는 2월까지 1학년 신분이기 때문에 대회에 참가하려고 했습니다. 하지만 제가 운영하지 않으면 사람이 없어서 대회가 안 열린다는 이야기를 듣고 눈물을 흘리며 운영진에 합류하게 되었습니다.
대회 코디네이터 역할을 맡은 것이라고 기대했지만 대회에 낼 문제가 부족해서 출제도 하게 되었습니다. 짧은 시간 동안 급하게 아이디어를 짜내다 보니 재미없는 문제만 2개 나왔습니다. 별로 대회에 내고 싶지 않았지만 어쩌다 보니 두 문제 모두 대회에 출제되었습니다.
출제했다고 코디네이터를 안 해도 되는 건 아니었습니다. 운영진 중 대회 운영 경험이 가장 많았기 때문에 문제 선제와 검수를 총괄했습니다. 문제 선제 회의 진행을 도와주신 2021년 고려대학교 ALPS의 회장이자 BOJ 연말 대회의 핵심 운영진인 Ryute님과, 예산이 적어 검수비를 많이 드리지 못하는 상황임에도 기꺼이 검수를 도와주신 7명의 외부 검수진 덕분에 문제를 완성할 수 있었습니다.
BOJ 측에 연락할 때 일개 운영진인 줄 알았던 제가 대회 개최자로 지정되어서 BOJ Stack도 제가 관리하게 되었습니다. 맨날 하는 일이라서 별로 부담이 되지 않았습니다.
대회 풀이 방송도 제가 하게 되었고, 방송에서 사용할 문제 풀이 슬라이드 제작도 자연스럽게 제 담당이 되었습니다. 출제자가 풀이를 적어주면 제가 문장을 다듬고 내용을 적당히 수정해서 슬라이드에 넣었습니다.
대회 문제와 관련된 대부분의 일을 제가 처리한 대신 행정적인 업무는 2021년 한양대학교 ALOHA 회장이신 dksu40님께서 담당해 주셨습니다. 정말 감사합니다.
문제 출제 과정 - 통행량 조사
Div.3의 마지막 문제(H)이자 Div.2의 G번 문제로 출제된 통행량 조사 문제는 제가 좋아하는 Unicycle Graph가 등장하는 문제입니다. 마침 한양대역이 있는 수도권 지하철 2호선이 Unicycle이라서 지문도 편하게 작성했습니다.
원래 이 문제는 HLD를 활용한 $O(Q \log^2 N)$ 풀이를 막으려고 했지만 BOJ의 채점 서버가 너무 좋아서 실패했습니다. 분명 Codeforces Polygon에서는 막혔는데… Intel Xeon을 쓰는 BOJ에 비해 Polygon은 i3를 써서 캐시 메모리의 크기에서 차이가 발생하는 것 같습니다.
이번 숭고한 연합 알고리즘 대회는 현대모비스의 후원을 받아 진행되었습니다. 기업을 소재로 한 문제를 만들어야 했고, 교통망과 관련된 이 문제가 후원 문제로 선정되었습니다. 덕분에 지문을 다시 썼습니다. 현대 오토에버의 후원을 받은 Hello, BOJ 2022!의 교통량 분석 문제의 지문을 많이 참고했습니다.
데이터는 Good Bye, BOJ 2020!에 출제했던 양분 문제의 데이터를 재활용했습니다.
아래 목록은 제가 작성한 솔루션 코드의 일부입니다. $O(N+Q)$, $O(N\log N+Q)$, $O(N+Q\log N)$, $O((N+Q)\log N)$, $O(N+Q\log^2 N)$ 등 다양한 복잡도의 풀이가 존재합니다.
1 | |
문제 출제 과정 - DCMSF
Div.1의 마지막 문제(H)로 출제된 DCMSF는 모르면 못 풀고 알면 쉽게 풀리는 전형적인 사전지식 문제라서 정말 대회에 내고 싶지 않았습니다. 다들 풀이를 먼저 고정해놓고 문제를 만들었다고 생각할 텐데, 사실 문제를 만들고 풀이를 생각한 문제입니다.
2021 Winter SUAPC에 Degree Bounded Minimum Spanning Tree라는 문제가 출제되었는데, 이 문제처럼 정점 차수에 제한이 있는 스패닝 트리를 구하는 것은 k = 2면 해밀턴 경로 문제로 reduction 되기 때문에 NP-Complete입니다. 여기에 조건을 적당히 붙여서 다항 시간에 풀 수 있는 문제를 만들고 싶었고, 이렇게 해서 나온 문제가 DCMSF입니다.
처음에는 차수 제한이 1일 때 MST를 구하는 문제였습니다. 이건 왼쪽에 제한이 걸린 정점, 오른쪽에 나머지 정점을 놓고, 오른쪽에서 MST를 구한 다음에 Kuhn-munkres algorithm이나 MCMF 등으로 가중치 이분 매칭을 해서 해결할 수 있습니다.
이틀 정도 문제를 고민하다 보니 트리 조건과 차수 조건이 각각 matroid라서 matroid intersection 으로도 문제를 해결할 수 있다는 것을 알게 되었습니다. 그리고 조금 더 고민해보니 트리 조건과 차수 1 제한 조건이 함께 있어도 matroid라서 단순한 그리디로 풀린다는 것을 깨달았습니다.
이렇게 문제를 버릴 수는 없어서 차수 $K_i$ 제한 조건을 추가해서 matroid intersection 문제로 만들었습니다.
문제를 검수할 사람이 없었는데, 외부 검수진으로 참여하신 dennisstar님과 cs71107님에게 matroid를 강제로 공부시켜서 검수를 하게 했습니다. 정말 감사합니다.
TMI) 일반적으로 3개 이상의 matroid intersection은 해밀턴 경로 문제로 reduction 할 수 있어서 다항 시간에 해결할 수 없습니다. 유향 그래프에서 간선 집합 $E$에서 $\mathcal{I}_1$을 모든 정점의 in-degree가 1 이하인 간선 집합, $\mathcal{I}_2$를 모든 정점의 out-degree가 1 이하인 간선 집합, $\mathcal{I_3}$를 방향을 무시했을 때 forest가 되는 간선 집합이라고 정의하면 해밀턴 경로 문제가 됩니다.
문제 검수
문제는 총 16문제였고 그중 제가 2문제를 출제했기 때문에 남은 14문제를 검수해야 하는 상황이었습니다. 문제별로 간단한 코멘트를 작성해 봅니다.
Div.2는 완전 탐색과 그래프 이론, Div.1은 사전 지식 문제가 많이 나와서 셋의 밸런스가 좋지 않다는 것을 알고 있었지만, 대부분의 시간을 문제에 오류가 없도록 하는 것에 투자하느라 밸런스를 맞추려는 시도조차 하지 못했습니다. 이밖에도 전체적으로 문제 지문의 상태가 별로 좋지 않고 그냥 문제가 재미없다는 점 등 여러 이슈가 있었는데, 제가 별로 대회에 의욕이 없어서 그런지 알고 있음에도 불구하고 고치지 않았습니다. 여러 채널로 대회에 대한 피드백이 들어오고 있는데, 문제가 너무 안 좋다고 느껴졌다면 제 탓이니까 저를 욕하시면 됩니다.
문제별 코멘트 (노잼 주의, 펼치기/닫기)
Div.2A 자동완성
현대모비스를 소재로 한 통행량 조사 문제처럼 Naver D2를 소재로 한 문제입니다. 저는 이 문제의 지문을 작성했습니다.
Div.2B 장작 넣기
원래 Div.2D에 출제할 예정이었지만 다른 문제가 더 어려워서 앞으로 이동했습니다. 스코어보드를 보면 좋은 선택이었다고 생각합니다.
문제를 잘 읽으면 완전 탐색을 이용해 간단하게 해결할 수 있습니다. 알고리즘을 처음 공부하는 분들은 대부분 완전 탐색을 구현하는 것에 익숙하지 않아서 많이 고전할 것이라 예상했지만, 이 점을 대회 4일 전에 깨달아서 손을 쓸 수 없었습니다. 죄송합니다.
Div.2C 주식
대회 시작 30분 전에 풀이에 오류가 발견된 문제입니다. 기존에는 매수/매도의 양을 자유롭게 결정할 수 있고 대출도 최대 $K$배 만큼 자유롭게 할 수 있었는데, 급하게 영끌 대출/풀매수/풀매도로 수정했습니다. ahgus89님 정말 감사합니다.
지문을 꼼꼼하게 읽지 않으면 많이 틀리기 좋은 문제고, 저도 검수하면서 많이 틀렸습니다. 장작 넣기처럼 완전 탐색을 이용해 해결할 수 있습니다.
Div.2D SKH 문자열
원래 Div.2B에 출제할 예정이었지만 너무 어려워서 장작 넣기와 위치를 바꿨습니다.
Div.2E 최대한의 휴식
드디어 완전 탐색이 아닌 문제가 나왔습니다. 문제를 많이 풀어봤다면 기계적으로 풀 수 있는 문제고, 많이 안 풀어봤으면 어려운 문제인 것 같습니다. 처음에 지문을 이해하기 어려웠는데 다른 검수자들은 잘 푸는 것 같아서 딱히 수정하지는 않았습니다.
Div.2F 노트 조각
교육적인 측면에서 봤을 때, Div.2에서 가장 좋은 문제라고 생각합니다. 이 문제도 문제를 많이 풀어봤다면 기계적으로 풀 수 있습니다. DE에 비해 전형적인 유형이라 그런지 문제 포지션에 비해 많이 풀렸습니다.
원래 Bellman-Ford와 SPFA의 저격 데이터를 만들려고 했는데 귀찮아서 TLE 나와야 하는 코드만 올리고 방치했습니다. 결국 대회 4일 전에 출제자가 직접 저격 데이터를 만들었습니다.
Div.2G 통행량 조사
노잼 문제
Div.2H 원형 게임
원래 Good Bye, BOJ 2021 / Hello, BOJ 2022 후보 문제였는데 숭고한에 나오게 되었습니다. 제가 검수를 시작할 시점에는 이미 잘 완성되어 있어서 딱히 건든 부분이 없습니다.
Div.1A 단어 마방진
원래 가지치기를 열심히 해야 하는 백트래킹 문제였지만, 올라온 솔루션마다 TLE 데이터가 튀어나오면서 단순한 완전 탐색 문제가 되었습니다.
Div.1B 이차 함수
왠지 될 것 같은 풀이를 짜면 통과되는 문제입니다. Div.2에 나와도 될 난이도지만 모듈러 곱셈 역원 때문에 Div.1에 나오게 되었습니다. 다행히 Div.1에서는 페르마 소정리라는 지식이 걸림돌이 되지 않은 것 같습니다.
고등학생 때 학교 공부를 안 했더니 풀이 증명하는 데 애를 먹었습니다. 아 미적분 너무 어려워…
Div.1C 캐슬 디펜스
제가 검수를 시작할 시점에 이미 잘 완성되어 있어서 건들지 않았습니다.
$ak-bt$가 최소가 되는 $(k, t)$를 2차원 좌표 평면에 찍으면 Convex Hull이 나오는 것을 이용해 새로운 문제를 만들 수 있을 것 같은데… 1시간 정도 고민했는데 좋은 아이디어가 안 떠올라서 포기했습니다.
Div.1D 내적
식을 만지다 보면 전형적인 문제로 바뀝니다. 개인적으로 식을 잘 변형하는 것이 어려웠는데 많이 풀려서 놀랐습니다.
오버플로우/실수 오차 때문에 좌표 범위를 더 키우지 못해 아쉬웠습니다.
Div.1E 다트
원래 이 문제가 Div.1D에 나올 예정이었지만, 미리 작성된 코드 없이 이 문제를 푸는 것은 매우 어렵다고 생각해서 내적과 위치를 바꿨습니다. 사전에 작성한 코드가 있다면 두 문제의 난이도가 비슷합니다.
2019 경기과학고 송년대회의 촛불과 그림자의 하위 호환으로, 풀이를 떠올리기는 굉장히 쉽지만 구현이 고통스러운 기하 문제입니다. 2018 ICPC World Final 은메달리스트인 서울대학교 MolaMola팀의 팀노트 덕분에 편하게 검수했습니다.
Div.1F 르블랑의 트리 순회
검수 안 했습니다.
Div.1G 숲 게임
BBST를 직접 구현해서 $O(N \log N)$ 솔루션을 작성하려고 했는데 귀찮아서 안 했습니다. 출제자가 의도한 풀이는 $O(N\log^2 N)$입니다.
Div.1H DCMSF
쓰레기 문제
풀이 방송
작년부터 알고리즘 강의를 비대면으로 하고 있기 때문에 마이크와 타블렛 같은 기본적인 장비는 이미 준비가 되어 있었습니다. 예전에 심심풀이로 문제 푸는 방송을 한 적이 있기 때문에 트위치 계정도 있고, OBS Studio도 사용할 수 있습니다. 그러다 보니 풀이 방송도 담당하게 되었습니다.
풀이 슬라이드는 UCPC 2020에서 했던 것처럼 overleaf에서 제작했고, 문제 해설은 마찬가지로 UCPC 2020에서 했던 것처럼 drawable pdf를 사용했습니다. 대회 스폰서 중 하나인 CorcaAI의 홍보 세션은 Zoom 회의를 트위치로 송출하는 방식으로 진행했습니다.
방송에 있어서 아쉬운 부분이 많이 있습니다. UCPC처럼 여러 레이아웃을 만들어서 깔끔하게 하고 싶었는데 제 능력과 시간이 모두 부족해서 단순히 화면 송출만 했습니다. 제가 검수하지 않은 Div1F와 Div1G의 풀이를 제대로 이해하지 못해서 잘 설명하지 못한 것도 아쉬웠습니다. 다음에 또 방송을 하게 된다면 방송 준비에 시간을 더 투자해야 할 것 같습니다. 그래도 슬라이드에 사소한 오타가 몇 개 있었던 것을 제외하면 별 문제 없이 진행된 점은 좋았습니다.
대회 마무리
이제 상금 지급, 인건비 지급과 같은 일만 남아서 인건비 계산을 제외하면 제가 할 일은 없는 것 같습니다.
대회 운영을 정말 밥 먹듯이 해왔지만, 이번처럼 운영진이 많은 대회에서 제가 중요한 역할을 맡은 건 처음이라 너무 힘들었습니다. 숭고한과는 비교도 안 될 만큼 규모가 큰 UCPC를 이끌어 나가는 UCPC 회장들과 BOJ 연말 대회 핵심 운영진들이 정말 대단하다는 것을 느꼈습니다.
이번에 너무 많이 고생해서, SCCC 회장이지만 다음부터는 숭고한 대회 운영은 안 하고 싶습니다. 올해 여름에는 제 공부가 급해서 절대 운영 안 할 생각이고 겨울에는 내년 회장한테 넘기고 도망가는 것이 목표입니다.
“알고리즘 동아리들이 모여 공부 방법과 내용을 교류하자” 는 취지에서 만들어진 행사인 만큼 차라리 알고리즘 강의를 시키면 할 텐데, 다른 운영진들은 강의보다 대회를 더 중요하게 생각하는 것 같아 아쉽습니다. 강의 준비보다 대회 개최가 더 쉽다고 생각하는 사람들이 많던데, 대회 개최를 가볍게 생각하지 않았으면 좋겠습니다.
고등학생 때 고생했던 것들이 지금은 정말 재미있었던 기억으로 남아있는 걸 생각해보면, 나중에 생각해봤을 때 이것도 나름 재미있던 추억으로 남을지도 모르겠습니다. 심지어 대회 준비 초반에 화났던 일들이 지금은 잘 기억이 나지 않습니다. 하지만 이번에 힘들었던 기억을 까먹고 다시 숭고한 대회를 운영하는 일은 발생하지 않았으면 좋겠습니다. 제 기억력을 한 번 믿어보겠습니다.
마치며…
고등학교 2학년 때 대회 열어보겠다고 객기부리던 것과 3학년 때 UCPC Call for Tasks에 문제 제출하고 조마조마하며 기다리던 것이 엊그제 같은데, 이제는 문제 출제와 관련된 대부분의 업무를 처리할 수 있을 정도로 성장한 것 같습니다. 3년 전, 수능을 100일 앞둔 시점에 제 첫 대회 개최를 도와준 Ryute님과 UCPC, SPC, SUAPC 등 다양한 대회의 운영 경력을 쌓을 기회를 주신 shiftpsh님을 비롯한 서강대 분들, BOJ 연말 대회마다 저를 불러주신 leejseo님, 그리고 최고의 선배 wookje님께 정말 감사드립니다.
중간고사 이후부터는 SCCC 내부 스터디를 진행해야 해서 쉴 틈이 없을 것 같습니다. 소모임 회장을 괜히 한 것 같아 매일 후회하고 있지만, 미래의 저에게는 좋은 추억과 양분이 되리라 생각하며 열심히 하고 있습니다.
학점을 포기했다고 떠드는 사람은 대외 활동을 지배하고 있다는 말이 있습니다. 이미 학점은 망해서 대외 활동을 지배해볼까 합니다. 뭔가 한 건 많은데 수상 실적이 부족한 것 같으니 SCPC와 ICPC를 위해 열심히 공부해야겠습니다. 여름방학 끝날 때까지 대회 운영 안 한다는 얘기입니다.
끝!