evenharder's profile image

evenharder

January 10, 2019 21:30

이 포스트는 2018년 고려대학교 프로그래밍 경진대회 출제 과정에 있었던 일들과 대회의 지향점 및 결과 및 사견을 다룹니다. 원래 대회가 끝나고 바로 쓰고 싶었으나 대회 1주일 후가 기말고사이기도 했고 준비가 워낙에 힘들었기 때문에 한 달이 지난 지금 쓰게 되었습니다.

우선 본 대회를 성공적으로 마무리해주신 운영진과 출제진에게 감사하다는 말을 드리고 싶습니다. 또, 본 대회의 규모 확장에 필수불가결한 기여를 해주신 Startlink, sooho, wishket, NAVER D2, vcnc, 삼성 소프트웨어 멤버십, 고려대학교 정보대학 SW중심대학, 정보보호학부 및 정보보호대학원과 관계자 분들께 감사의 말씀을 드리고 싶습니다.

제가 운영진을 시작한 것은 11월 9일로, 대회 날짜로부터 꼬박 한 달이 남은 때였습니다. 타 운영진이 각각 장소, 스폰, 예산안, 홍보 등을 다루고 있는 동안 저는 대회 문제의 난이도 분포를 구성해야하는 막중한 임무가 주어졌습니다. 게다가 올해는 지원도 많이 들어온 관계로 고려대학교 재학생이라면 누구나 응시할 수 있게 했기 때문에 난이도를 보다 잘 신경쓰고 싶었습니다. 결과적으로 준수한 문제들이 많이 나왔지만 중급반과 고급반에게는 쉽지 않은 대회가 되었습니다. 내년에는 보다 많은 사람이 만족해갈 수 있는 대회가 되기를 희망합니다.

출제 과정

대회 구성

우선 대회를 어떤 형식으로 열지를 정하고 시작해야했습니다.

Problem Solving / Competitive Programming에서 초보와 숙련자의 수준 차이는 대단한 수준입니다. 때문에 수많은 대회들이 Division을 나누어 치룹니다. 일반적으로 2개로 나누지만, 저는 다음과 같은 이유로 3개로 나누자는 생각을 했습니다.

고려대학교의 프로그래밍 동아리인 AlKor와 ALPS가 3개의 분반으로 나뉘어있었습니다.

2018년 8월에 진행되었던 ‘숭고한’ 연합 프로그래밍 캠프 / 대회도 3개의 분반으로 나뉘어 있었기에 난이도 배정이 편할 것 같았습니다.

참가자들의 수준이 초심자 / PS에 발을 담그고 있는 Codeforces 기준 Cyan, Blue 코더 / ACM ICPC 본선 진출자에 폭넓게 분포하여 있었습니다.

첫 번째 이유와 비슷하며, 중급반과 고급반의 실력 차이가 현저하기 때문에, 한 대회 세트를 통해서 양쪽이 모두 즐길 수 있게 만들기 어렵다고 생각했습니다.

운영진은 저의 뜻을 존중해주었고, 대회와 관련하여 순위 산정 방식과 패널티를 다음과 같이 생각하였습니다.

문제에 점수를 매기고 의미 있는 수준에서 서브태스크를 제작

문제에 점수를 매기는 건 난이도와도 연결되어 있기 때문에 다음 부절에서 다루도록 하겠습니다. 높은 점수를 보면 뿌듯하지 않을까라는 사견도 반영되어 있었습니다.

패널티는 ‘마지막 제출 시간’ + ‘제출 결과에 대한 패널티’로 설정

초반에 문제를 빠르게 푸는 것보다는 몇 개의 문제를 푸는데 걸린 총 시간이 (ACM ICPC의 스타일에 익숙하지 않은 참가자가 많은) 교내대회에 더 적합하다고 생각했습니다. ACM ICPC처럼 패널티의 총합으로 하자는 의견도 있었으나, 출제진의 투표를 통해 마지막 제출 시간 기준으로 결정되었습니다.

난이도 구성

본 대회의 목적은 개인 능력 측정 및 경쟁이기도 하지만 또 즐거움이 결핍되면 안 되기에, “올솔이 나오지 않게 하면서도 모두가 성취감을 느낄 수 있는 대회”를 지향했습니다. 점수제와 연결되는데, 당시 AtCoder에 깊게 감명을 받은 상태였고 숭고한 때 너무 난이도가 높게 나와서 스코어보드가 처참했던 기억까지 났습니다. AtCoder의 ABC는 쉬운 문제들이 많고 ARC에도 충분히 모두를 만족시킬 만한 수준의 난이도가 나오기 때문에 모델로 삼았습니다.

괜히 멋을 부리고 싶었던 걸까요? 3개의 division의 총 점수가 규칙성 있게 나오는 걸 원했습니다. 처음부터 2400 - 3600 - 4800을 생각했으며 이에 맞추어 난이도를 짜맞추었습니다. 난이도는 원래는 AtCoder와 거의 비슷하게 맞추려고 했는데 굳이 안 그래도 된다는 사실을 출제된 문제를 보면서 깨달았습니다. 이후 문제수를 8개로 하자는 의견이 대두되었고, 수용하였습니다.

처음에 구상되었던 문제 점수 체계는 다음과 같습니다. 점수는 난이도를 의미하기도 하며, AtCoder와 비스무리하게 생각했었습니다.

점수	100	200	200	300	300	400	400	400	500	500	600	600	700	700	1000
초급반	o	o	o	o	o		o	o	o
중급반			o	o		o		o	o	o	o			o
고급반				o			o		o		o	o	o	o	o

원래는 중급반만의 문제를 2~3문제 정도 넣고 싶었으나, 그러지 않아도 세트가 괜찮아보였고 출제진이 어려운 문제를 많이 제공하기도 해서 최종적으로는 다음과 같이 변경되었습니다.

점수	100	200	200	300	300	400	400	500	500	600	600	700	700	700	1000
초급반	o	o	o	o	o	o	o		o
중급반		o		o		o	o	o	o		o	o		o
고급반				o			o	o		o		o	o	o	o

결과적으로는 초급반은 정말 적절했으나, 중급반과 고급반은 스코어보드가 처참했습니다. 점수 분포를 2400 - 3200 - 4000이나 2400 - 3000 - 3600 수준으로 매겨야 하지 않았나 싶습니다.

문제 출제

문제 출제 과정은 생각보다 순조로웠습니다. 위의 점수표와 각 점수별 난이도의 예시 문제를 문서로 만들어놓자 며칠 만에 10개가 넘는 문제의 초안이 잡혔습니다. 처음에는 Google Drive를 통해 공유하며 작업을 했습니다. 대회 플랫폼을 BOJ로 생각하고 있었기 때문에 빠르게 BOJ Stack을 사용하고 싶었으니 당시 BOJ에서 논란이 많았던 대회 하나가 진행되었던 관계로 무슨 문제를 낼지와 지문, 테스트 케이스가 어느 정도 완성된 상태에서 이전하였습니다.

출제된 문제 중 몇 개는 빛을 못 보고 아이디어만 남기는 선에서 사라지기도 했고, BOJ Stack까지 올라갔으나 출제되지 못한 문제가 있기도 했습니다. 중위권 문제가 이 경향이 컸습니다. 중급반 수준에서 적당한 문제를 만드는 게 그리 쉽지는 않았던 느낌이 듭니다.

기본적으로 문제제안자가 문제를 만들어도 괜찮겠다는 암묵적인 분위기가 형성되면 테스트 케이스를 만들었으며, 검수는 상위 난이도 문제의 경우 출제자를 제외하고 1~2명이 검수를 진행했습니다. 조금 더 했으면 좋았겠지만 문제의 데이터나 솔루션이 터질 것 같진 않아서 크게 문제삼지는 않았습니다.

문제 제작은 결코 쉬운 일이 아닙니다. 그러나 다행히 대부분의 출제진이 여러 번 문제를 출제를 해보았던 분들인지라 수월하게 진행되었습니다.

문제지 제작

문제지 제작은 제가 담당했으며, 표지는 @subinium님이 제작해주셨습니다. 링크는 여기에 있으며, 세부 사항은 해당 repo의 README.md를 봐주시기 바랍니다. 서브태스크와 점수제를 강조하기 위해서 olymp.sty 파일을 뜯어고치던 기억이 납니다. 형식과는 별개로 지문에 모호함이나 오탈자가 없게 최대한 노력을 하였으나, 정작 제가 출제한 두 문제의 지문에 그런 여지가 있었다는 게 슬펐습니다.

진행 결과

진행 결과는 각각 여기에서 확인할 수 있습니다.

• 초급반 (Beginner Division)
• 중급반 (Intermediate Division)
• 고급반 (Advanced Division)

초급반 (Beginner Division, Div. 3)

초급반은 신청하신 31분 중 19분께서 참가해주셨습니다. 스코어보드를 보면 C번과 D번이 역전되는 것을 제외하면 매우 흡족스러운 결과가 나왔습니다. 내년에도 동일한 포맷으로 대회를 진행한다면 난이도를 비슷하게 유지하면 될 것 같습니다.

중급반 (Intermediate Division, Div. 2)

중급반은 신청하신 31분 중 11분께서 참가해주셨습니다. no-show가 지나치게 높았던 대회였습니다. 난이도 측면에서는 B번까지는 대부분 잘 풀고 넘어갔으나 C번을 많이 난감해했습니다. D번과 E번과는 달리 이 대회 최고의 조커 문제인 F번에서 많은 분들이 점수를 따갔습니다. GH는 0솔브를 예상했고 실제로도 그러했습니다.

고급반 (Advanced Division, Div. 1)

고급반은 신청하신 14분 중 9분께서 참가해주셨습니다. 거의 모든 점수가 ABCD에 몰려있었고, D번을 풀었는지의 유무가 수상 여부를 결정지었습니다. 원래 셋의 의도는 맨 마지막 문제인 H가 0-1솔브가 나오는 것이었고 많은 출제진이 EFG 중 1-2개는 풀릴 것이라고 예상하였으나 개인적으로는 E부터 만점이 절대 나오지 않을 것으로 예상했고 적중했습니다.

오픈¹에서는 고급반의 경우 D가 시간이 많이 까먹었던 점은 동일하며, E가 나름 well-known이라 많이 풀렸습니다. F는 오픈에서도 만점이 나오지 않았습니다.

문제 분석

각 문제에 대한 간단한 풀이와 감상을 서술하도록 하겠습니다.

고려대학교에는 공식 와인이 있다 (100점, 초급반 A번)

$ \sum_{k=1}^n k $, $ \sum_{k=1}^n k^{2} $ 공식으로 풀 수 있는 문제입니다. 가장 쉬운 문제로 간주되었으며 실제로 모든 초급반 참가자가 해결하였습니다. 시간 제한이 0.1초인데, 의미가 있는 제약인지 잘 모르겠습니다.

2018년을 되돌아보며 (200점, 초급반 B번, 중급반 A번)

문자열에 2, 0, 1, 8이 몇 개 포함되어있는지를 이용하면 풀 수 있는 문제입니다. 문자열 처리로도 정수 계산으로도 풀 수 있지만 위의 문제보다는 조금 어려웠던 것 같습니다. 19명의 초급반 참가자 중 17명이, 중급반은 전부 해결하였습니다.

절대적으로 보면 쉬운 문제이지만, 이런 문제조차도 익숙치 않은 프로그래머들은 숙련자들이 전혀 예상치 못한 방향으로 코딩을 하는 경우가 있어서 다채로운 테스트 케이스를 제작해 넣었습니다. 경험상 이렇게 조건문만으로 풀리는 문제는 더 합니다.

두 개의 손 (200점, 초급반 C번)

가위바위보 한 손 빼기 문제입니다. 상대가 무얼 내든 이길 수 있을 때만 승부가 결정이 나는 문제로, 코드도 짧고 어렵지 않으며 아이디어도 재미있지만 생각보다는 난감할 수 있는 문제였습니다. 초급반에만 배치했고 그러길 잘했다는 생각이 듭니다. 200점짜리 문제였지만 다음 문제인 ‘근우의 다이어리 꾸미기(300점)’보다 초급반에서 적게 풀렸습니다 (11명). 효율적으로 조건문을 6~7개만 사용해서 해결한 참가자도 있는가 하면 하드코딩을 시도한 참가자들도 있었습니다.

참고로 테스트 케이스에는 가능한 81가지의 입력이 모두 들어가 있습니다.

근우의 다이어리 꾸미기 (300점, 초급반 D번, 중급반 B번, 고급반 A번)

재밌고 간단한 그리디 문제입니다. 출제자는 200점으로 내리기를 원했으나 그러면 점수 분포가 원만해지지 않아서 그러질 못했습니다. 0이 입력으로 들어올 때 처리를 올바르게 하지 못한 경우와, 수의 자리 개수로 답을 잘못 가정한 경우가 종종 있었습니다. 초급반에서는 19명 중 13명, 중급반과 고급반은 전부 해결하였습니다.

지문의 숫자를 각각 하나씩 가져가서 사용하는 메커니즘을 명확하게 설명하려고 노력했습니다.

악마 게임 (300점, 초급반 E번)

모 대기업의 게임이 주제가 된 문제로, 문자열 처리 문제입니다. 한 문자열에서 다른 문자열을 만들어낼 수 있는지 판별하는 방법은 간결하지만 초급반에게는 그리 쉽지 않았을 것으로 생각됩니다. 입력이 작아서 실수 오차는 크게 신경쓰지 않아도 괜찮습니다. 초급반에서는 9명이 해결하였습니다.

모독 (400점, 초급반 F번, 중급반 C번)

역시 모 대기업의 게임이 주제가 된 문제로, 코드 자체는 짧게 나오는 정렬 + 그리디 문제입니다. 기본적인 접근은 현재 쫒아낼 수 있는 최대 명예 점수를 저장하면서, 이를 다음 국회의원의 명예점수와 비교하며 쫒아낼 수 있는 최대 명예 점수를 올려나가는 것입니다. 그러나 잘못된 그리디 접근으로 인한 ‘틀렸습니다’가 적지 않게 나와서 통곡의 벽이 되어버리고 말았습니다. ‘틀렸습니다’를 받는 코드를 많이 검수하지는 않았는데 잘 걸러진 걸 보면 테스트 케이스를 잘 만드신 것 같습니다. 별개로 답이 $ 2^{31}-1 $을 넘어갈 수 있음에도 불구하고 32비트 정수형을 사용하신 분이 적지 않았습니다.² 초급반에서는 6명, 중급반에서는 11명 중 9명이 해결하였습니다.

고려대학교와 이렇게 동떨어진 지문이 나와도 되는지에 대한 토의가 약간 있었지만, 출제자의 뜻을 존중하여 그대로 출제하였습니다.

Back to the Bones (400점, 초급반 G번, 중급반 D번, 고급반 B번)

약간의 고찰이 필요한 확률 동적 계획법 문제입니다. 그리디하게 주사위를 한 번에 선택할 수 있는 방법은 없습니다.³ 그러나 굴린다면 낮은 숫자부터 굴려봐야 하므로, 1개, 2개, 3개……굴려보는 방식으로 해결할 수 있습니다. 같은 400점이지만 바로 위의 ‘모독’ 문제보다는 어렵다는 평가를 받았습니다. 초급반에서 단 1명도 풀지 못했으며, 중급반도 2명밖에 풀지 못했습니다. 고급반에선 9명 중 7명이 해결하였습니다.

문제의 레퍼런스는 한 스팀 게임입니다. 문제와 동일한 조건으로 주사위를 굴려야 할 때가 생깁니다.

등산 (500점, 중급반 E번, 고급반 C번)

정해는 위상정렬이고, 다익스트라 알고리즘으로도 해결할 수 있습니다. 최단거리 알고리즘을 2번만 사용하면 되는 문제라 빠르게 풀릴 것이라고 생각했으나 심리적인 압박과 짧지 않은 지문 때문이었는지 중급반에서도 고급반에서도 신통치 않았습니다. 오픈에서는 C번을 B번보다 먼저 푸는 사례가 속출했습니다. 중급반에서는 단 1명, 고급반에서는 6명이 해결하였습니다.

추가적으로 본 문제에는 비효율적으로 짠 다익스트라 코드와 SPFA 알고리즘을 저격하는 데이터가 들어가 있습니다.

안수빈수 (500점, 초급반 H번, 중급반 F번)

본 대회 최고의 조커 문제입니다. 출제자에 의하면 수학 대회 문제라고 합니다. 오픈컵까지 포함하여 랜덤, 다양한 커팅, 조금 다른 전탐색 등등 다채로운 솔루션이 나왔습니다. 시간 초과나 틀렸습니다가 대부분이었지만 운영진 및 출제진 입장에서는 예상치 못한 시도가 많이 나와 흥미로웠습니다.

처음 문제는 제약이 $ 10^9 $까지인 대신 쿼리가 1개뿐이었습니다. 대충 전탐색을 돌리는 코드를 방지하기 위해 테스트 케이스를 도입해서 최대 1000개의 숫자에 대해 답을 구해야 하는 것으로 바꾸었고, 시간제한도 0.5초로 낮추었습니다. 수의 제약을 $ 10^8 $으로 하기 보다는 $ 5 \times 10^8 $로 했으면 난이도에 보다 부합했을 것 같습니다.

많은 출제진이 이 문제는 풀 수 있는 사람이 한정되어 있을 것이라고 생각하였으나 초급반에서도 1명 풀었으며, 중급반에서는 4명이 해결하였습니다. 원래는 이 문제가 고급반 문제였으나 수학적 직관력에 대한 메리트를 최소화하고 싶어서 고급반에서는 제외하였습니다.

하노삼의 탑 (600점, 고급반 D번)

3가지의 (변형) 하노이 탑을 구현해야 하고 분할정복을 통해 역추적까지 진행해야 하는 문제입니다. 다양한 경우에 대한 관찰이 필요한 문제이기 때문에 고급반 만점자는 2명밖에 없었습니다. 다음 고급반 문제부터 난이도가 훅 뛰어서 적당한 위치에 있는 문제라고 생각이 됩니다. 실제로 본 난이도 체계의 모티브가 된 AtCoder도 600점이라는 난이도가 애매모호해서 문제가 많지 않습니다.

오픈에서는 본 문제를 4분만에 푼 분이 있었습니다. 이 문제를 구상했었고, 정해 코드까지 가지고 있었다고 합니다.

삼원색 (600점, 중급반 G번)

낮지 않은 난이도와 정해 코드의 상당한 구현량을 보면서 과연 이게 중급반 문제일까라고 깊은 고민을 하게 되었습니다. 그러나 고급반에 이미 세그먼트 트리를 이용한 자료구조 문제가 있었기 때문에 중급반에 나오게 되었습니다. 결국 이 Plane Sweeping 문제는 중급반에서 제출자가 아무도 없었고 오픈에서도 주목받지 못한 비운의 문제가 되었습니다.

XOR 포커 (700점, 중급반 H번, 고급반 E번)

subset xor maximization 문제에 약간의 트릭을 섞은 문제입니다. 사전지식이 있거나, 검색을 할 수 있었던 오픈에서는 많이 풀렸습니다. 그러나 중급반이나 고급반이나 이 문제와 이후 문제를 푼 사람은 없었습니다. subset xor maximization은 구현과 아이디어가 간단하지만, 사전지식이 없다면 풀기 매우 힘든 문제라고 생각합니다. 시간이 더 있었으면 좋았겠지만, D번까지 이르는 과정도 참가자들에게 버거웠으리라 예상합니다.

종이 자르기 (700점, 고급반 F번)

700점 이상 문제 중 이해하기 쉬운 축에 드는 문제이나, 오픈에서조차 만점이 나오지 않은 대단한 문제입니다. 기하에 실수오차가 들어가 있는 이 문제는 검수 과정이 정말 힘들었습니다. 테스트 케이스가 너무 알차서 $ N \leq 10 $ 이하인 경우에서 반례가 잘 잡혔습니다. 오차를 $ 10^{-4} $ 정도로 했으면 더 괜찮았을 것이라는 평이 있었습니다. 그나마 본 대회에서는 150점짜리 서브태스크가 유의미했습니다.

실시간 내비게이션 (700점, 고급반 G번)

동적 계획법 기반 세그먼트 트리로 해결이 되는 어려운 문제입니다. 250점짜리 서브태스크는 다익스트라 알고리즘 같이 적당히 빠른 최단거리 알고리즘으로 해결이 됩니다. 오픈에서는 E를 푼 사람의 절반도 풀지 못하는 난이도를 보여주었습니다.

기묘한 여행계획 (900점, 고급반 H번)

상당히 다양한 관찰을 요구하는 동적 계획법 문제입니다. 출제자는 Codeforces에서는 웰노운 트릭일 것이라고 생각하였으며, 실제로 제약조건만 다르고 사실상 동일한 문제가 JOI Open Contest 2016에 이미 출제된 바 있었습니다. 그럼에도 불구하고 오픈에서조차 3명밖에 해결하지 못한 고난도 문제입니다.

여담 및 결론

중급반과 고급반 대회가 너무 어려웠구나라는 생각만 머릿속에서 계속 맴돌았습니다. 중급반과 고급반의 대다수가 뿌듯함을 느꼈을지 잘 모르겠습니다. 다행히도 특별상이 많아서 수상식의 분위기는 쾌활했습니다. 또 no-show가 생각보다 많아 의외였습니다. 중급반의 경우 배정된 상의 개수와 인원수가 일치하는 현상이 나타나 전원 수상이라는 드문 일이 일어났습니다. 상을 받을 수 있는 확률이 올라가는 건 좋지만, 보다 많은 사람들이 참여하길 바라는 심정도 있었기에 만감이 교차합니다.

본 대회의 결과를 반면교사로 삼아 2019년 고려대학교 프로그래밍 경진대회는 다르게 진행될 가능성이 있습니다. 문제 수가 적어질지, 문제가 더 쉬워질지, xOI 스타일로 갈지, 아니면 2017년 대회처럼 될지, 어쩌면 전혀 색다른 방법으로 진행될지는 잘 모르겠습니다. 그러나 ‘모두가 성취감을 느낄 수 있게 하는 대회’의 취지는 살리지 못했다고 생각해서 미련이 남습니다.

내년, 아니 올해 고려대학교 프로그래밍 경진대회는 언제 어떻게 열릴지 감도 잡히지 않지만, 작년의 장점을 계승하고 단점을 보완하는 대회가 되길 희망합니다.