djm03178's profile image

djm03178

February 17, 2020 10:16

개요

• Codeforces Round #620 (Div. 2)
  • Announcement
  • Editorial
• Codeforces Round #578 개최 후기

작년 여름, nong (전 hyunuk) 님과 함께 개최한 Codeforces Round #578 (Div. 2)은 저의 문제 풀이 경력에서 가장 멋진 경험이었다고 해도 과언이 아닙니다. 항상 문제를 푸는 입장에서 참여하고 비교적 소규모의 대회 몇 개에만 부분 출제 및 검수를 해본 것이 전부였던 저에게 만 천 명이 넘게 등록한 대회의 문제 반을 출제하여 성공적으로 개최한 것은 굉장한 일임이 분명했습니다.

하지만 후기글에 남겼던 것과 같이 문제마다 부족했던 점들이 하나둘씩 있었고, 제가 가장 주된 역할을 한 문제는 세 문제뿐이었다는 사실이 시간이 지날수록 아쉬운 마음이 들게 만들었습니다. 그래서 작년 9월 말부터 단독 라운드를 개최하기 위한 준비를 시작하였고, 지난 2월 15일에 성공적으로 개최하였습니다.

이 글에서는 지난 578번 라운드 때와 마찬가지로 이번 620번 라운드의 개최 후기를 써보려고 합니다. 풀이를 설명하기 위한 글은 아니지만 일부 스포일러가 포함되어 있으니 주의하시기 바랍니다.

대회 준비

처음 단독 라운드를 결심하고 proposal을 만들기 시작한 날은 작년 9월 24일이었습니다. 문제 풀이에 쓰는 시간이 예전만큼 길지 않고 실력도 그다지 늘지 않은 것 같아 Div. 1 수준의 문제를 만들 자신은 없었기에¹, 이번에도 Div. 2 전용 라운드를 만들기로 했습니다.

이전 라운드에서 “출제자는 문제의 난이도를 과소평가하는 경향이 있다”라는 사실을 강하게 느꼈고, 모든 문제를 풀 수 있는 공식 참가자가 수십 명 정도는 있는 것이 좋다고 생각했기에² 가능한 쉬운 기조를 유지하려 노력하면서 proposal을 작성했습니다. 그렇게 온전한 proposal이 완성된 것은 10월 3일이었습니다.

준 Coordinator³인 300iq 님을 만난 것은 12월 중순이었습니다. 처음의 A, B, C, D, E, F번 문제 중 F는 전형적이라는 이유로 제거되고, 기존의 E가 F로, D가 E로 바뀌었으며, C는 너무 어렵다는 이유로 거절되었지만 D에 넣고 싶지는 않아서 지우고 새로운 C와 D를 만든 뒤 OK를 받았습니다.

처음에 만든 문제들이 약간 어려울 수도 있다고 생각했기에 D, E가 각각 E, F가 된 것은 무난할 것이라고 생각했고, 바로 문제 작성에 착수했습니다. 그러나, 이 중 마지막까지 처음의 모습을 그대로 유지할 수 있었던 문제는 A, B, C 뿐이었습니다.

테스트

문제들이 거의 완성되어 갈 무렵인 1월 23일이었습니다. 빠르면 2월 1일, 아니면 2월 8일 정도에 대회를 개최하기로 마음먹고 테스터를 모집하기 시작했습니다. 백준 온라인 저지의 Slack 서버에서 홍보를 했고, 많은 고수분들이 테스터로 참여를 해주셨습니다.

그런데 무언가 조짐이 좋지 않았습니다. 테스터 분들의 평가가 하나같이 ‘너무 쉽다’였던 것입니다. 쉬운 라운드를 추구하기 때문에 그럴 수 있다고 처음에는 스스로를 안심시켰지만, 아무리 봐도 그 정도가 아닌 것 같았습니다. 테스터 분들의 구성이 거의 Div. 1 수준이어서 쉽게 느낄 수 있다고도 생각했으나, E에서 제가 생각하지 못한 간단한 풀이가 발견되고, Candidate Master인 분이 DE를 푸는 데에 20분도 안 걸리는가 하면, 모든 문제를 푸는 참가자가 200명에 달할 것이라는 예측까지 나오면서⁴ 이대로 둘 수 없다고 확신을 가지게 되었습니다.

심지어 E번과 90% 유사한 기출 문제가 오래된 코드포스 라운드에서 발견되면서 불가피하게 E를 전면 교체할 수밖에 없게 되었습니다. 약 1주일을 고민한 끝에 새로운 아이디어를 냈고, 그 아이디어를 이용한 문제를 몇 차례 변형시키다가 현재의 E 문제가 탄생하게 되었습니다. 또한 이 문제가 기존보다는 훨씬 어렵다고 생각했기 때문에⁵, D와의 격차는 너무 크고 F와의 격차는 작다고 느껴져 D와 F에도 손을 대기 시작했습니다. F번은 몇몇 분들이 더 효율적인 풀이를 찾아내면서 조건이 강화된 버전의 문제를 만들어 F1과 F2로 분리되었고, D번은 기존의 부분은 그대로 두되 유사한 아이디어를 두 번 사용하도록 분량을 늘리게 되었습니다.

이렇게 만들어진 최종 문제 셋에 대해서도 여전히 기존의 다른 라운드보다는 쉽다는 의견이 지배적이었지만, 이 정도면 그래도 해볼만 하다고 생각하여 최종 문제 셋을 확정짓게 되었습니다. 이전의 라운드에서 문제를 저평가하여 coordinator KAN님께 조정을 많이 받았다면, 이번 라운드에서는 반대로 출제자의 문제 저평가 경향만을 믿어 너무 쉬운 셋이 될 뻔한 것을 테스터 분들이 막아주셨다고 할 수 있습니다.

마지막까지 D, E, F에 대한 난이도 의견은 논란이 있었지만, 전체적인 의견을 모아 점수 분포 (500 - 1000 - 1500 - 1750 - 2000 - (2000 + 1000))를 결정하고 대회날을 맞이하게 되었습니다.

대회 개최

참가자 수는 지난 라운드에 비해 크게 늘어 비공식 참가를 포함하여 14612명이었습니다. 코드포스의 사용자 수가 급격하게 늘어나고 있는 추세라는 것을 볼 수 있었습니다.

대회는 비교적 순조롭게 진행되었습니다. 큰 이슈나 지문의 모호함 등이 없었고, 눈에 띄는 난이도 역전 관계나 지나치게 불균형한 점수 분포도 없었습니다. 질문의 수는 지난 라운드와 비슷한 109개였으나, 그 때와는 달리 출제자가 저 뿐이었기 때문에 질문에 답하는 일이 훨씬 긴박했습니다. 게다가 중간에 300iq 님의 인터넷에 문제가 생겨 러시아어 질문들이⁶ 20분간 답변되지 못하는 해프닝도 있었습니다.

최종적으로 문제 해결자 수는 7859 - 6097 - 3852 - 1328 - 698 - (112 - 38)에 모든 문제를 푼 참가자는 정확히 30명으로, 거의 황금 밸런스에 가까운 분포로 대회를 성공적으로 마치게 되었습니다.

문제별 분석 및 평가

이전 라운드의 후기와 마찬가지로, 이번에도 각 문제별로 출제하면서 생각했던 점들, 대회 결과에 대한 평가 등에 초점을 두어 분석하도록 하겠습니다. 직접적인 풀이는 에디토리얼을 참조해 주세요.

A. Two Rabbits (500)

지난 라운드에서 처음에 A번으로 고안한 문제가 B로서도 쉽지 않은 문제였던 것을 감안하여, 이번에는 정말 누구나 쉽다고 생각할 수 있는 A번을 만들자는 생각으로 출제했습니다. 결국 정말로 쉬운 A번이 되었고, 너무 쉬운 것 같아서 토끼의 이동 방향을 반대 방향으로도 할 수 있게 해보는 건 어떨지 proposal에 남겨보기도 했지만 만약 그랬더라면 도로 어려운 문제가 될 뻔했습니다. 지금대로 놔둔 것이 적절한 판단이었다고 생각합니다.

그런데 너무 쉬운 것이 도리어 참가자들에게 함정이 있는 것이 아닐까 하는 의심을 주었던 것 같습니다. 심지어는 이 문제를 이분 탐색으로 푸는 분들도 종종 보였습니다. 그래도 전체적으로 대부분의 참가자들이 쉽게 풀어내었고 첫 문제임에도 불구하고 질문도 거의 없어 깔끔했던 것 같습니다. 이에는 대회 시작 몇 시간 전 그림을 추가해주신 MikeMirzayanov 님의 도움도 컸다고 생각합니다.

B. Longest Palindrome (1000)

아이디어보다 구현이 어려운 문제였습니다. 처음 proposal을 쓸 때는 구현체를 만들지 않아 글로만 설명하고 상당히 쉽다고 생각했는데, 막상 솔루션을 작성해보니 바로 뚝딱하고 코드를 완성할 수 있는 문제는 아니었습니다.

그래도 아이디어 자체는 비교적 간단하고, 이 정도 구현은 초보자들도 오래 시간을 들이면 충분히 가능할 것이라고 생각해 그대로 사용했는데 결과적으로는 아주 적절했던 것 같습니다. A번, C번과의 정답자 수 간격도 좋았고, 푸는 데에 들이는 평균 시간도 더할 나위 없이 완벽했다고 생각합니다.

조금 아쉬운 점이 있다면 시스템 테스트에서 틀린 코드가 제법 많았다는 것인데, 다중 테스트 케이스 문제로 했다면 이를 방지할 수 있었겠지만, 안 그래도 구현이 쉽지 않으면서 초기화가 번거로운 문자열 문제를 B번에서 다중 테스트 케이스 문제로 하는 것이 꺼림칙했기 때문에 많은 시스템 테스트 실패를 어느 정도 예상하면서도 단일 테스트 케이스로 밀고 나가게 되었습니다. 처음에는 프리테스트를 더 많이 (16개 정도) 넣고자 했으나 너무 많다는 300iq님의 지적에 12개로 줄였는데, 지금 생각하면 길이가 한 글자인 문자열들을 주는 13번 테스트를 프리테스트에 넣는 것이 좋았을 것 같습니다. 많은 시스템 테스트 실패 코드들이 13번 테스트에서 틀렸는데, 조금만 더 생각했더라면 이것이 제법 코너 케이스가 될 수 있다고 알아챌 수 있었을 것 같습니다.

또한 다른 문제에서는 잘 보기 어려운 현상도 자주 목격할 수 있었는데, 예제에서 틀리는 코드의 비중이 매우 높았다는 것입니다. 대부분의 문제에서는 예제에 대한 답이 유일하거나 직관적이므로 먼저 예제들은 다 통과하는 코드를 제출하기 마련인데, 이 문제는 자신의 코드가 예제를 통과하는지를 적절하게 판단하지 못하고 제출해 본 참가자들이 상당히 많은 것을 볼 수 있었습니다. 짝을 2개 찾아야 하는 4번 예제가 없었더라면 틀린 이유를 찾는 데에 고생하는 참가자가 정말 많았을 것으로 생각합니다.

C. Air Conditioner (1500)

C번은 이전 라운드의 B번과 유사한 형태이면서도 다른 그리디 전략을 사용하는 문제로 만들고자 했습니다. 그리디 문제를 많은 사람들이 어려워한다는 것을 충분히 느꼈기 때문에, 이 문제도 답을 알고 보면 정말 간단한 전략임에도 C번으로 쓰기에 부족함이 없는 난이도일 것이라는 확신을 가질 수 있었고, 실제로도 예상한 수준의 정답자 수가 만들어졌습니다.

이전 라운드의 B번과 마찬가지로 기상천외한 방법으로 문제를 풀으려는 참가자들이 많았고 그런 코드들이 틀리는 케이스가 매우 한정적이었기 때문에 다중 테스트 케이스 문제임에도 불구하고 7개의 프리테스트만으로 막지 못한 코드들이 간혹 보였습니다. 시스템 테스트에서도 패턴을 아주 다양화한 것은 아니었기 때문에 혹시나 잘못된 코드가 통과된 것이 있지는 않을지 살짝 우려도 됩니다.

대회 중에 여러 참가자들이 “문제의 조건과 달리 입력이 시간 순으로 정렬이 되지 않은 것 같다”라는 제보를 해서 긴장하게 만들기도 했습니다. 다행히 validator⁷를 다시 점검해 보아도 문제는 없었고, 제보자들의 코드를 읽어본 결과 그 분들은 모두 공통적으로 각 케이스의 입력을 전부 받지 않고 하나씩 입력받으면서 정답이 결정나는 순간 바로 해당 케이스를 종료해버리는 실수를 범하고 있었습니다. 다중 테스트 케이스 문제에서만 볼 수 있는 묘미인 것 같습니다.

D. Shortest and Longest LIS (1750)

D번부터는 본격적으로 출제 중 우여곡절이 많았던 문제들이 시작됩니다. 이 문제의 첫 버전은 LIS의 길이가 가장 긴 것만을 찾는 것이었습니다. 그러나 테스트 과정에서 Candidate Master 정도의 테스터 분들이 문제를 푸는 데에 대체로 10분도 걸리지 않는 것을 보고 많은 고민을 하기 시작했습니다.

문제의 난이도가 너무 쉽다고 느끼게 된 가장 큰 이유는 접근법이 다양하다는 것이었습니다. 정확한 원리를 찾아내지 않아도 ‘왠지’ 될 것 같은 접근법을 하나 생각해서 구현하면 대개 맞는 정답이 나오는 문제였고, 실제로 테스트 과정에서만 정답을 찾아내는 전략을 서너 종류 볼 수 있었습니다.

그래서 이 문제를 보다 어렵게 만들기 위해 다양한 변형을 생각해 보았습니다. 그 중에는 ‘정답 중 LIS를 뽑는 경우의 수가 가장 많은 것 찾기’와 같이 제가 처음에 의도한 풀이만을 통과시키는 것도 있었고, ‘LIS의 길이가 정확히 $k$인 수열 찾기’⁸도 있었습니다. 지금의 문제를 생각해내고 확정지은 것은 E번이 확정된 뒤였는데, 바뀐 E번도 그렇게 어렵지는 않다고 평가받았기 때문에 기존보다 어려운 아이디어를 사용하는 문제를 생각하는 대신 기존 문제의 아이디어를 두 가지로 떠올리게 해서 구현량과 문제를 푸는 시간을 늘리는 방향으로 생각하게 된 것입니다.

결과적으로 정답자 수로 보았을 때는 오히려 C와 D의 격차가 제법 많이 났고 배점도 250점 차이를 두기엔 조금 균형이 맞지 않는 모습이기도 합니다. 그래도 문제 자체를 놓고 보았을 때에는 LIS의 길이가 가장 짧은 것과 긴 것을 둘 다 해보는 것이 문제를 더욱 재미있게 만들었다고 생각합니다.

이 문제도 B번과 마찬가지로 예제에서 틀리는 경우가 많았는데, 주로 출력한 수열의 LIS의 길이가 몇인지를 제대로 체크해보지 못했거나, 입력으로 주어진 비교 결과와 일치하는지 주의깊게 살펴보지 않았기 때문인 경우가 많은 것으로 보입니다. 또한 예제는 pretest 1이고 pretest 1에서 틀리는 것에는 페널티가 없다는 점도 한몫 한 것 같습니다.

이 문제의 솔루션을 만들 때 느꼈던 것 중 하나는 Java의 System.out.print가 매우 느리다는 것입니다. 시간 제한을 3초로 설정한 것도 이 때문인데, 겨우 40만 개의 정수를 출력하는 데에도 시간이 2초 이상이 소요되는 것을 볼 수 있었습니다. 심지어는 일반적으로 많이 쓰이지만 느리기 때문에 시간 제한 설정의 기준이 되는 Python 솔루션보다도 더 느렸습니다. 그 때문에 정해는 0.3초도 소요되지 않는 문제의 시간 제한을 크게 늘릴 수밖에 없었지만, 다행히 특별히 생각나는 나쁜 시간 복잡도의 풀이도 없었기에 크게 고민하지 않고 여유 있는 시간 제한을 설정할 수 있었습니다.

E. 1-Trees and Queries (2000)

이 문제 역시 정말 많은 일이 있었던 문제입니다. 문제의 태생 자체가 기존에 있던 다른 E번을 대체하여 만들어진 것이기도 하고, 출제 과정에서 쉬운 풀이를 떠올리지 못하고 난이도를 잘 파악하지 못해서 테스터 분들께 많은 도움을 받기도 했습니다.

처음에 떠올렸던 문제 아이디어는 트리에서 어떤 노드의 두 자식을 잇는 간선만을 추가하는 것이었습니다. 이때까지는 테스터 분들께 아이디어를 알리지 않고 혼자서만 풀이를 생각하고 있었는데, 문제를 괜히 어렵게 받아들여 괴상하고 복잡하기만 한 풀이밖에 떠오르지가 않았습니다. 그 때문에 일찍 문제를 포기해 버리고, 문제의 형태를 정점의 수를 줄인 일반 그래프 상에서 간선 추가 없는 쿼리로도 바꾸어 보았습니다. 하지만 문제가 너무 전형적이라는 평가를 받았을 뿐 아니라, 제 풀이에서 실수까지 발견되어 마음이 급했던 저는 상당히 고통스러운 경험을 하게 되었습니다.

결국 다시 처음의 문제로 돌아가 테스터 분들께 말씀을 드려보았는데, 트리에서 아무 정점끼리나 연결하는 간선을 추가해도 쉽게 풀 수 있다는 말씀을 듣고 굉장히 충격을 받았습니다. 풀이를 들어보니 결과적으로 정말 간단하기는 한데, 아직까지도 직관적으로 와닿지 않고 어떻게 그런 생각을 쉽게 해낼 수 있는지도 잘 이해가 되지 않습니다.

더욱 놀라웠던 것은 300iq님이 부르신 한 테스터 분은 이 문제를 매우 쉽게 푸셨을 뿐 아니라 D보다도 쉽고 매우 전형적이라면서⁹ 둘의 순서가 바뀌어야 한다고 주장하신 것이었습니다. 저로서는 이해할 수 없는 의견이었지만, 많은 테스터 분들이 D와 E의 차이가 크지 않다는 의견을 내주셨기에 지금과 같이 250점 차이를 두었고, 결과적으로는 아주 적절한 판단이 되었습니다. 이 문제를 출제하면서 저의 큰 약점을 하나 찾은 것 같아 좋은 경험이 되었다고 생각합니다.

데이터를 만드는 것도 매우 힘든 작업이었습니다. 트리를 사용하는 문제를 출제한 것은 처음이었기에, 다양한 트리 모양과 쿼리의 패턴을 고려하여 나쁜 시간 복잡도의 풀이가 통과되지 않게끔 조정하는 일이 상당히 힘들었습니다. 지금까지 문제를 풀어본 경험상 트리는 그 제한적인 구조 때문에 여러 방면으로 ‘치우친’ 형태를 만들지 않으면 최악의 경우의 시간 복잡도가 보장되지 않는 여러 최적화 테크닉으로 뚫기가 쉽기 때문입니다. 일자형, v자형¹⁰, 스타형¹¹ 등의 트리 종류와, 거리가 충분히 먼 노드끼리의 거리만을 묻는 쿼리, 최단 거리에 가까운 $k$ 값을 설정하는 쿼리 등 여러 특성을 가진 데이터를 만들어낼 수 있도록 제너레이터를 만들다 보니 무려 300줄이 넘어가고 말았습니다. 그 정도 길이의 코드에 큰 실수가 없었다는 점은 다행이었던 것 같습니다.

F. Animal Observation (2000 + 1000) (easy version, hard version)

처음 테스트를 받기 전에는 easy version만이 있었습니다. 본래 E번을 생각하고 만든 문제였으나, 더 위에 있던 문제가 빠지고 이 문제 자체로도 충분한 난이도가 있다고 생각해서 F번으로 올리려고 했었습니다. 그러나 그것은 너무 짧은 생각이었습니다.

테스터 분들은 이구동성으로 “F번 치곤 너무 쉽다”, “난이도가 2100 정도인 것 같다”¹², “모든 문제를 푸는 사람이 200명 정도 나오겠다”라고 말씀해주셨고, 이번에도 저는 이 문제가 그렇게 쉽게 평가되는 것에 (E번보다는 덜하지만) 충격을 받았습니다. 물론 전체적으로 쉬운 난이도를 추구하기는 했지만, 일반적으로 “출제자는 자신의 문제를 저평가한다”라는 경향과는 정반대되는 상황이었기 때문입니다.

다행히도(?) 이 문제를 더 어렵게 만들기 위해 새로운 문제를 개발할 필요는 없었습니다. 몇몇 테스터 분들이 문제의 정해진 $O(nmk)$를 개선한 $O(nm\log{m})$과 $O(nm)$ 솔루션을 발견해주셨고, 제가 직접 해당 풀이들을 만들어보았을 때에도 지나치게 쉽거나 어렵지 않은 수준이라고 느꼈기 때문입니다.¹³ 다만 더 어려운 버전만을 쓰기에는 E번과의 격차가 매우 크다고 생각했기 때문에 지금과 같이 서브태스크로 나누게 되었고, 더욱 균형잡힌 정답자 수 분포를 만드는 데에 일조했습니다.

이 문제의 풀이는 어느 정도 전형적일 수도 있으나, 참가자들의 실력 분포를 생각하면 좋은 경험이 될 수 있는 문제였다고 생각합니다. 한 댓글에 의하면 이전에 코드포스에서도 잘 보이지 않던 테크닉이라고 합니다.

종합 의견

A, B, C번은 초기부터 적절한 수준으로 잘 만들어졌으나, 처음의 D, E, F번 난이도 조정은 실패했고 고쳐나가는 데에 많은 어려움을 겪었습니다. 또한 그 과정에서 제가 상대적으로 취약한 분야가 어디인지도 알 수 있었고, 많은 사람들의 의견을 들어보는 것이 대회의 완성도를 높이는 데에 매우 중요하다는 것을 깊이 느낄 수 있었습니다.

결과적으로 정답자 수의 분포는 매우 만족스러웠으며, 점수 분포도 이에 어느 정도 맞게 잘 설정한 것 같습니다. 다만 F번의 Easy version이 2000점으로 E번과 배점이 같은데, 푼 사람의 수는 제법 많이 차이나서 과연 둘의 난이도가 비슷한가 하는 것은 의문이었습니다.¹⁴ DEF의 배점은 2000 - 2250 - (2750 + 750) 정도가 더 낫지 않았을까 하는 생각이 들기도 합니다.

마치며

단독 출제에 대한 욕심으로 시작한 라운드였고, 그 대가로 많은 고생을 했지만 이렇게 성공적으로 대회를 마칠 수 있어서 행복했습니다. 무사히 대회가 개최될 수 있도록 오랜 기간 많은 도움을 주신 열아홉 명의 테스터 분들과 대회의 시작부터 끝까지 관리해주신 coordinator 300iq님, 그리고 좋은 대회 제작 및 출제 플랫폼들을 제공해주신 MikeMirzayanov 님께 감사의 말씀을 전하고 싶습니다.

추후 다른 코드포스 대회를 다시 열 수 있을지는 모르겠으나, 꼭 코드포스가 아니더라도 다른 대회의 문제를 출제하거나 검수를 하는 데에 있어 많은 도움이 될 것으로 기대합니다.