shake! 2019 본선 출제 후기
shake!는 경인지역 6개 대학(아주대학교, 경희대학교, 성균관대학교, 인하대학교, 한국항공대학교, 한양대학교 ERICA)의 학생들이 참여하는 대회입니다. 예선을 통해 각 학교 대표 10명이 선발되고, 본선에는 60명의 대표들이 모여 대회를 치룹니다.
이 포스트는 2019년 shake! 본선(7월 7일에 열림)의 출제위원을 맡으면서 있었던 일들과 결과에 대한 후기를 다룹니다. 기타 운영에 관해서는 참여하지 않았기에 후원사 찾기, 출제진이 구성되는 과정 등은 다루지 않습니다. 출제진은 koosaga님과 ainta님, spectaclehong님, 그리고 메인 운영진인 Acka님과 저(hojoon0205)로 이루어졌습니다(모두 acmicpc.net 아이디 기준입니다).
혹시 이 대회의 문제들을 풀어보고 싶으신 분들은 백준 온라인 저지에 가셔서 대회에 있는 2019 경인지역 6개대학 연합 프로그래밍 경시대회 shake!에 들어가셔서 문제들을 보실 수 있습니다. 백준 문제 번호로는 17300번 부터 17307번 까지입니다.
들어가기에 앞서, 아래의 내용들은 운영진 전체의 생각이 아닌 전부 제 개인적인 생각임을 밝힙니다.
대회 전 출제과정
난이도 구성
대회의 룰은 ACM-ICPC와 같았습니다. 모두가 성취감을 느낄 수 있는 것이 좋은 대회라 생각했기에, 스코어보드가 밑에 있는 조건들을 만족한다면 난이도 밸런싱이 잘 된 것이라 생각했습니다.
- 모두 푼 사람은 안 나올것
- 아무도 못 푸는 문제는 없을것(1명 이상에게 풀릴 것)
- 아무것도 못 푸는 사람은 없을듯(모든 참가자가 1문제 이상은 풀 수 있게)
- 그래도 1등은 문제수-1 정도는 풀어줬으면 좋겠다.
그리고 작년 기출문제와 결과를 통해 참가자들의 실력 구성을 다음과 같이 예상했습니다.
참가자격에 ‘역대 ICPC 수상자 참가 불가’, ‘역대 shake! 3위 이내 입상자 참가 불가’ 조건이 있으므로 실력 좋은 사람은 신입생 정도 말곤 불가능할 것.
학부에서 자료구조와 알고리즘에 대해 배웠고 구현도 가능하지만 PS에 대해서 따로 공부하지 않은 사람들이 평균
작년에 Parametric Search + DP가 아무도 못 푸는 문제가 되었으니, 더더욱 PS에 대해서는 익숙하지 않을 것이다.
Codeforces 기준 Blue중위권이 상위권~탑1 (Div2 기준 2시간 동안 A,B,C는 웬만큼 풀고 D번 문제 간간히 풀 수 있는 수준)
저대로면 PS에 익숙하지 않은 사람들이 대부분일 것이라 생각하여 학부 수준에서 다루는 알고리즘에 한해서 내기로 합의했습니다.
BrainStorming ~ 문제 확정
5월 중순에 출제진이 확정된 후, 모든 출제진이 각자 문제 아이디어들을 내는 시간을 가졌습니다. github에 repository를 하나 파서 공유하는 식으로 작업했고, 약 2주 가량 모은 결과 12개의 문제가 나왔습니다. 이후 출제진이 모여 문제 선별 및 개량/개조 과정을 거치는 작업을 하게 되었습니다. 총 8개의 문제들을 출제할 생각이고, 후원사가 둘이 있었기 때문에 두 문제를 후원사 헌정 문제로 두어야 했습니다. 그 중 한 문제는 후원사인 Superb AI에서 감사하게도 문제를 제공해 준 덕분에 7문제를 출제하게 되었습니다.
위에서 말한 난이도 구성에 맞게끔 고르기 위해, 먼저 각 문제의 난이도들을 Codeforces의 Div2 수준에서 몇 번 문제의 난이도와 비슷한지 각각 부여했습니다. 상당수가 Div2D와 비슷한 수준이라 많은 사람들이 풀기 힘들어할 난이도라 예상했습니다. 그래서 일부 문제에 대해서 난이도를 하향시키는 작업을 했고, Div2D 문제 두개를 Div2C로 낮추는 결과가 되었습니다.
결과적으로 6개의 문제와 2개의 후원사 문제로 이루어진 문제set가 만들어졌고, 출제진이 제작한 문제들(후원사 제공 문제 제외)은 Div2 기준 A 한 문제, B 한 문제, C 두 문제, D 세 문제(어디까지나 출제진들의 생각입니다)로 이루어졌습니다. 다만, 후원사 문제 하나가 굉장히 큰 변수로 작용했습니다. 우리는 올솔브가 아쉽게 안나오는 수준의 난이도 분포를 원했으나, 후원사에서 굉장히 어려운 문제를 주셨습니다. 개인적으로 Div2F나 그 이상이라 생각했습니다.
Test Data 제작 및 검수
문제 set이 확정이 난 이후, Codeforces 사이트에서 별도로 제공하고 있는 polygon이란 문제 제출 플랫폼(https://polygon.codeforces.com/)을 이용하여 데이터 제작과 검증 및 다른 사람들의 검수를 진행했습니다. 이 과정에 약 1달 정도의 시간을 쓴 것 같습니다. 각자 데이터를 제작하고, 각자 낸 문제의 잘못된 풀이들을 생각하며 counter-case들을 준비하고, 다른 사람들이 낸 문제들을 틀린 풀이로 맞출 수 있는지 등에 대해서 서로 검수하는 작업까지 진행합니다. polygon 플랫폼이 너무 많은 기능을 잘 지원해주고 있어서 특별히 어려운 점은 없었던 것 같습니다. polygon 사용법에 대해 궁금하신 분은 Acka님의 포스트 https://www.secmem.org/blog/2019/05/17/polygon-how-to-use/ 를 참고해주세요.
BOJ Stack 플랫폼을 통한 문제 등록 과정
우리의 대회 플랫폼은 어디까지나 백준 온라인 저지(이하 BOJ)이기 때문에, 결국 polygon의 채점환경 말고 BOJ에서의 채점환경에서도 돌려보아야 했고, BOJ에서 문제는 잘 읽혀지는가, 시간제한은 얼마나 달라져야 하는가 등등에 대해서 다시 확인해보아야 했습니다. polygon에서 본인이 제작한 문제들의 text, test data, solution file 모두 따로 받아올 수 있었고, polygon과 BOJ 둘 다 잘 만들어진 플랫폼이었기 때문에 STL에 대한 issue가 잠시 있었던 것 빼곤 사실상 파일과 텍스트 옮기는 작업이나 다름없었습니다.
대회 도중
대회 도중에 출제진이 할 일은 다음과 같았습니다:
참가자들이 어떤 풀이로 풀었는가, 우리의 의도대로 풀어주었는가, 잘못된 풀이가 통과되었는가 확인하기
틀린 데이터가 있어서 수정해야 할 일이 급하게 생긴 경우에 대비하기
실시간으로 날아오는 참가자들의 질문들에 답변하기
새로운 풀이가 등장했다면 그 풀이가 맞는지 확인 및 증명하기
참가자 응원하기(?)
대회 도중이란 시간은 출제진이 모여서 난이도에 대해 회의했었고, 우리 의도대로 참가자가 풀어주었는지, 혹은 새로운 풀이가 등장하여 출제진을 놀라게 해 줄 것인지, 스코어보드는 우리가 예상한 난이도 순서대로 풀렸는지, 우리가 생각한 좋은 대회의 기준에 얼마나 적합했는지 등등 지금까지 우리가 해왔던 노력과 정성이 참가자들에 의해 평가받는 시간이고, 그 평가를 스코어보드 라는 형태로 실시간으로 받게 되는 시간입니다. 그렇기에 두근거리며 스코어보드 경과를 지켜보게 되었고, 각자 낸 문제가 풀렸을 때, 혹은 상상치도 못한 풀이가 나옴에 기뻐하는 시간이 되었습니다. 개인적으론 제가 재학중인 대학이 이 대회에 참가하는 대학이라 같은 대학 출신 참가자들을 응원하는 재미도 있었습니다(사실 상위권을 먹어서 더 재밌었습니다).
스코어보드가 변하는 모습에 대해서도 이야기 하고 싶으나, 각 문제 별 분석 및 후기 부분에 적도록 하겠습니다.
대회 종료 후, 후기
우선 제가 예상했던 난이도 순(=푼 사람수 역순)은 다음과 같았습니다.
A < F < H < B < C < (E, G) «< D
그리고 실제 결과도 정확히 저 난이도 순이었습니다. 난이도 예상과 푼 사람수와 정확히 매칭되어 기분이 굉장히 좋았습니다. 그렇다면 위에서 언급했던 좋은 밸런싱은 잘 되었을까 살펴보았습니다.
- 모두 푼 사람은 안 나올것 -> 1등이 5문제를 풀어서 만족
- 아무도 못 푸는 문제는 없을것(1명 이상에게 풀릴 것) -> D번을 제외하고 모든 문제가 풀렸습니다. D번은 출제진이 낸 문제가 아니니 적당히 목표를 이룬 셈이라 생각했습니다.
- 아무것도 못 푸는 사람은 없을듯(모든 참가자가 1문제 이상은 풀 수 있게) -> 아쉽게도 두 명이 한 문제도 풀지 못했습니다. 그래도 60명의 참가자를 생각하면 개인적으론 충분히 봐줄만한 정도라 생각합니다.
- 그래도 1등은 문제수-1 정도는 풀어줬으면 좋겠다. -> 상당히 어려웠던 D를 제외하더라도 6문제를 푼 사람이 나오지 않아서 다소 아쉬운 점입니다.
전체적으로 이상에 가까운 난이도 밸런싱이었다 생각하고, 참가자들이 감탄을 많이 했던 아이디어형 문제인 C번 문제도 있어서 문제에 대한 호응도 꽤 괜찮았다 생각합니다. 거기에 대회 중에 질문이 많이 들어오지 않아 문제 설명에 대해서 충분한 설명을 했다는 점에 대해서도 만족스러웠습니다.
단 한가지 대회에 대해서 아쉬웠던 점으로, 스코어보드 공개 때 호응이 너무 없었습니다. koosaga님께서 분위기를 띄워보려고 열심히 리액션을 해주셨고 나도 나름대로 했으나, 끝까지 호응을 같이 안해주던게 굉장히 아쉬웠엇습니다. 다들 이런 공개방식을 처음 겪어서 그런 것이라 생각합니다.
각 문제 별 분석 및 후기
제가 예상했던 난이도 순으로 써볼까 합니다.
A. 패턴
모든 사람이 한 문제 이상은 풀고 가게끔 하자는 의도로 낸 spectaclehong님의 문제입니다. 간단한 구현이든, 노가다같은 구현이든 풀어주길 바라는 마음에 출제되었습니다. 60명 중 58명이 풀어주었고, 목표를 완전히는 아니어도 거의 이뤘다고 생각했습니다. Div2A 수준으로 생각하고 출제되었습니다.
F. 사탕배달
koosaga님께서 BOJ의 설탕배달 문제에 질문글이 굉장히 많은 것에서 착안하여(https://www.acmicpc.net/board/search/all/problem/2839) 출제하신 문제입니다. Div2B 수준이라 생각했습니다. 스코어보드에 첫 도전한 사람이 7번 연속으로 실패하여 다른 참가자들이 겁을 먹었는지 스코어보드가 잠시동안 변화가 없었습니다. 결과적으론 두 번째로 가장 많이 풀린 문제이긴 했으나, 한동안 대회가 망할까봐 불안에 떨기도 했었습니다. 3과 5라는 숫자조합에 뭔가 있는게 분명합니다.
H. 색깔 통일하기
제가 출제한 문제입니다. 처음에는 N 제한을 5000으로 줄이고 버튼이 일직선으로 연결된 것이 아닌 트리형태로 연결되어 있었습니다. Div2D 수준을 예상하였으나, 다른 문제들이 Div2D가 너무 많았기 때문에 N제한을 250000으로 늘리고 선형으로 연결되어있는 구조로 바꿨습니다. 그 결과 Div2C 수준을 노린 문제가 되었고, 세 번째로 많이 풀린 문제가 되었습니다. 맨 마지막에 위치해 있어서 그랬는지 한동안 풀리지 않아 불안에 떨기도 했었습니다.
B. NC 문자열
후원사 NC에게 헌정하는 문제입니다. Acka님이 문제 컨셉에 대한 아이디어를 주셨고, ainta님이 초안을 완성해주셨으며, 제가 난이도를 낮춘 개정안을 제시하여 완성된 문제입니다. 후술하게 될 문제들과 H번 난이도의 사이에 들어갈 수 있는 적당한 난이도를 원했습니다. H번 보다는 덜 풀렸고, 10명 정도가 풀어주었으니 만족스러운 난이도 배치였습니다. 개인적으로 난이도 보정을 정말 잘 한것 같아 뿌듯했던 문제입니다.
C. 흰색으로 만들기
ainta님께서 출제하신 문제입니다. 아이디어성 문제로, 난이도 배정하기가 가장 까다로웠습니다. 개인적으로 코딩이 A번 보다도 쉬운 문제였다 생각했으나 아이디어를 떠올리지 못하면 사고가 이상하게 빙빙 돌다가 말릴만한 문제라 생각해서 Div2D 정도에 배치했습니다. 아이디어가 생각나면 정말 쉬운 문제인지라 적어도 한 명은 풀 것이라는 마음가짐으로 출제되었고, Div2D 문제들 중에서 가장 쉬운 선에 놓았습니다.
대회가 끝나고 문제가 공개된 후, 다른 사람들은 H번보다 쉬운 문제라고 평가하고 있었습니다. 대회 도중에 많이 안 풀린 것은 스코어보드에 휘둘려서 문제를 제대로 고민해보지 못한 영향이 크다고 생각했습니다.
E. 변호사들
ainta님께서 출제하신 문제입니다. 그래프에서 단방향과 양방향 간선들을 처리하고, cycle을 확인하는 알고리즘을 의도했었습니다. 그러나 참가자들 사이에서 각 정점들의 degree를 이용한 간단한 풀이가 나왔습니다. 출제진들끼리 풀이에 대한 검증을 시작했고, 풀이가 틀리지 않았다는 증명이 된 후 모든 출제진이 새롭고 더 간단한 풀이법에 감탄했습니다. 대회가 끝난 후 또 다른 풀이가 발견되어 다양한 풀이가 존재하는 흥미로운 문제로 남았습니다.
G. 전쟁 중의 삶
koosaga님께서 출제하신 문제입니다. trie를 이용한 풀이와 set(map)을 이용한 풀이 두 가지를 준비했고, 둘 다 Div2D 수준이라 생각하였습니다. 그러나 max heap을 사용한 출제진도 생각 못했던 간단한 풀이가 나왔고, 지금은 그 덕에 풀릴만한 문제였다고 생각하고 있습니다.
D. 슈퍼브 다트
후원사 Superb A.I.에서 제공해주신 문제입니다. 계산기하라는 압도적인 위압감 만으로도 제출 수 0회를 만들어버린 문제였습니다. 아무도 못 풀 것이라 예상했으나, 제출 수 0회는 다소 안타까운 결과였습니다. 그와 별개로, 풀이를 듣고 한번쯤은 구현 해볼만한 좋은 계산기하 문제인 것 같습니다. CCW, 각도정렬을 연습하기 좋은 문제라 생각합니다.