Problem Solving

Goodbye, BOJ 2019! 후기

Ryute 2020. 1. 5. 08:15

Intro

 굿바이, BOJ 2019! 라는 대회는 어떻게 보면 제 주도로 만들어진 대회입니다. leejseo님과 rdd6584님과 작년 백준에서 진행했던 디디포스를 끝내고, 다음 대회를 진행해 보자는 말이 나왔었습니다. 10월 초 경에 생각이 나서 대회를 열고 싶었는데 만약 12월 말에 대회를 개최하게 된다면 디디포스와 거의 1년 간격이 된다는 것을 알았습니다. 구데기컵과 키파컵을 보고 백준에도 매년 정기적으로 개최되는 대회가 있었으면 좋겠다고 생각했는데 마침 대회를 여는 시기가 연말이었기 때문에, 낼름 연말 대회 자리를 먹기로 시도했습니다. 백준 대회란이 백준 고유 콘테스트가 아닌 다른 교내대회 오픈컨으로만 가득 채워진 것이 조금 안타까워서도 있었습니다. 그런 고로 자주 활동하는 알고리즘 채팅방에서 사람을 모으기 시작했습니다.

준비를 시작하기

 (대회 운영진들이 아셨을지는 모르겠지만) 개인적으로 디디포스의 정신을 잇는 대회인 만큼, rdd6584님과 leejseo님을 빠르게 모셨습니다. 또한 다른 친구들도 학교 내 대회가 아닌 공개 콘테스트를 개최하는 경험을 한번 쯤 해 보면 좋겠다고 생각하여 계절학교 학생들이 다수 있는 소규모 채팅방 #싯포에서 justicehui나 ahgus89, junseo를 비롯한 동생들을 모았습니다. 디디포스때도 많은 도움을 주었던 lawali를 고민을 거듭한 끝에 운영진으로 끌고 왔고, PS판의 아이돌 wookje님이 합류해주셨습니다. 그 외에도 cheetose님과 gs11008님이 도와주셨고, rdd6584님이 ckw1140님을 초빙해 주셨습니다. 

 잠깐 디디포스에 대해 짚고 넘어가자면, 디디포스는 전반적으로 중상위권 난이도의 문제들로 채워진 셋이었고(다른 말로 해서 주는 문제가 없었다고 봐도 되고: 제일 쉬운 문제가 solved.ac 기준 골드3인데 이 정도면 코드포스 블루 미만은 풀기 힘듭니다), 서브태스크 문제도 있었습니다. 문제가 난이도 순서대로 정렬된 것도 아니었습니다. 이러한 조건들이 겹쳐서 초보 분들이 어 대회네? 하고 건드려 봤다가 바로 탈주하는 경우가 너무 많았습니다. 결국 참가자 수는 바닥을 찍었고 고인물들만 남아서 rdd6584님 문제를 푸는 상황이 발생했습니다.

 이 상황이 마음에 들지 않았기에, 또 연말 대회인 만큼 이번 대회는 초보자분들도 부담없이 참가할 수 있는 대회를 만들기로 결심했습니다. 더해 모두가 즐길 수 있어야 하는 만큼 오렌지와 레드를 포함한 고인물 유저들도 문제를 재밌게 풀 수 있어야 했습니다. 초보자들이 부담없이 참여하면서도 좋은 대회가 되려면 어떤 대회를 구성해야 할까? 라는 고민 끝에, 다음과 같은 조건을 만족시키기로 했습니다.

- 문제를 풀 때 옮겨 다니면서 갈팡질팡하지 않아야 합니다. 즉, 난이도가 명확해야 합니다.
- 문제를 아예 풀지 못하는 사람이 존재해서는 안 됩니다.
- 굉장히 빠른 시간 안에 올솔브가 나오는 상황을 방지할 수 있어야 합니다.
- 단순 수학 이론이나 구현 문제의 출제를 지양합니다.
- 사용하는 알고리즘이 치우쳐 있지 않아야 합니다.

어?

 

야, 너 좀 낮이 익다?

 

허구한 날 Mathforces로 욕을 처먹는 점만 빼면, 제가 원하는 대회 세트가 코드포스와 굉장히 닮아 있다는 것을 발견했습니다. 매우 명확한 난이도 판단이 가능하고 점점 증가하는 이상적인 난이도 곡선을 그리면서 어려운 문제는 있는, 상당히 괜찮은 형식입니다. 코드포스의 스타일을 따기로 정하고 나서, 대회 이름은 자연히 Goodbye 2019가 되었고 문제 수와 난이도 배치도 실제 코드포스의 Goodbye 2019와 유사하게 하기로 했습니다. 물론 순전히 제 개인적인 의견과 기획이었지만, 다른 운영진 분들이 따라와 주셔서 굉장히 감사하다는 말을 전하고 싶습니다. 그럼에도 불구하고 여기에 자존감 넘치는 쓸데없는 한마디를 더 얹자면 저는 결과적으로 제 선택이 괜찮은 선택이었다고 생각합니다(...)

 안타깝게도 저는 대회 준비 기간 초반에 수험생이었기 때문에 leejseo님에게 주최자 자리를 빠르게 떠넘기고 튀었습니다. 만족스러운 선택이었습니다. 모두 믿을 수 있는 사람이 있다면 적극적으로 해야 할 업무를 떠넘기도록 합시다.

 문제를 만들자

 기억이 잘 나지는 않지만, 문제를 대략 7~9문제로 하기로 했고 대충 8문제쯤으로 하기로 분위기가 잡혀 있었던 것으로 기억합니다. 비교적 초반에 ckw1140님의 최단경로와 쿼리 문제, wookje님의 (대충 제목이 너무 길어서 쓰기 곤란한 문제)가 제시되었습니다. wookje님의 문제는 웰논 비빔밥이라는 본인의 평가가 있었으나(실제로 금광 문제와 같은 문제입니다) 저는 괜찮은 문제라고 생각했습니다. ckw1140님의 문제는 처음에 해법이 정확하지 않은 듯 하여 출제진 사이에서 많은 토론이 있었는데, 저는 잘 모르지만 토론 과정에서 풀이가 정확한 것으로 밝혀져서 출제가 될 수 있었다는 것으로 기억합니다. wookje님 문제가 F, ckw1140님 문제가 E를 차지했습니다. 그리고 lawali가 다른 데 낼까 고민하던 문제가 있다고 해서, 그냥 여기 내라고 회유를 거친 끝에 대회 준비 초반부에 벌써 킬러 문제 쿼리와 쿼리가 나와버렸습니다. 신나서 풀이와 데이터까지 순식간에 만들어버린 lawali 덕에 H번에 문제가 들어갔습니다.

 이렇게 세 문제가 나오니까 앞 부분 문제들이 필요하다는 생각이 들었고 앞부분 문제들을 받았습니다. 여러 후보들이 있었지만 난이도 배치가 애매하거나 너무 수학적이고, 아니면 초보자들에게는 어려운 개념이 있다는 이유로 잘려 나갔습니다(제 독단적인 판단이었는데, 사실 좀 많이 죄송합니다 ㅠㅠ). 또 쿼리 문제가 너무 많았기에 비율 또한 조정해 나갔습니다. 결과적으로 DP를 사용하는 ahgus89의 욱제가 풀어야 하는 문제, 그래프 문제가 부족하다는 저의 징징거림을 해결해 준 leejseo의 철도 여행, 그리고 요청했던 노솔브 방지용 문제인 겨울왕국 티켓 예매가 출제되었습니다. 각각 C, D, A에 들어가게 되었네요. 마지막으로 leejseo가 B에 들어갈 적절한 문제면서 연말 분위기도 내 주는 제야의 종 문제를 출제하여 모든 문제가 깔끔하게 채워지게 되었습니다.

 여기서 제 강박증이 강하게 발동했습니다. 그래프가 있고, DP 있고, 최단경로 있고, implementation 있고, 세그먼트 트리 있는데, 그게 없습니다. 기하가 없습니다. 사실 많은 대회에서 기하는 문제 제작과 데이터 만들기의 어려움으로 인해 걸러지고는 합니다. 당장 백준 대회 목록만 봐도 기하 문제를 찾기란 매우 어려운 일이 아닐 수 없습니다. 처음에는 수험생이라는 조건 때문에 이번 굿바이2019에서는 출제를 하지 않고 검수만 진행할 생각이었습니다. 하지만 수능이 끝나고 입시를 조져서 라왈리의 KCPC 검수노예가 될 수도 있는 기구한 운명이 기다리는 상황에서도 한 문제 자리가 남았기에, 기하 문제를 출제하고자 하는 욕심이 생겼습니다. 그렇게 별이 빛나는 밤에라는 문제를 출제하게 되었고, G에 배치되었습니다. 제가 출제한 문제에 대한 잡설들은 나중에 풀도록 합시다.

지지고 볶기

 문제가 나오고 나서 여러가지 해프닝이 있었습니다. 먼저 욱제님의 문제에 더 쉬운 해법이 존재하는 것으로 확인되어, 빠르게 정해가 갈아치워졌습니다. 라왈리의 솔루션 수행 시간은 라왈리가 이상한 최적화들을 박음에 따라서 굉장히 빠르게 줄어들었고, 제한을 빡빡하게 주는 것을 사랑하는 라왈리 특성 상 제한 시간도 빠르게 줄어들었습니다. 저는 제한을 널럴하게 주는 쪽을 선호하기 때문에 2초를 주고 싶다는 라왈리를 설득해서 3초로 시간제한을 변경하는 것을 시도했습니다. ckw1140님의 문제도 시간제한이 변경된 것으로 알고 있습니다. 중간에 풀이가 확실치 않은 제 문제의 검수를 위해 boj 슬랙에 요청글을 올리고 ho94949님을 모셔왔지만, 제 문제 대신 라왈리의 쿼리와 쿼리를 avx를 통해 너무나도 쉽게 뚫어주셨습니다. 여기서도 작은 소란이 있었습니다.

 문제 난이도 배치가 정확하지 않다는 의견이 있었습니다. 일단 저는 아직까지도 왜 현재 G인 최단경로와 쿼리가 E에 배치되어 있었는지 이해가 되지 않고, 그 당시에도 E는 좀 아닌 것 같은데를 주장했었습니다. G로 올려서 너무나도 다행인 문제라고 생각합니다. 최단쿼가 G로 올라가면서 자연스럽게 별밤이 F로 내려갔고, 새로운 풀이가 발견되면서 욱제님의 문제도 E로 내려갔습니다. 욱제님의 문제가 D까지 내려갈 뻔 했고 저도 철도 여행인 D가 더 어렵다고 생각했으나 구현 난이도를 고려하여 유지하는 쪽에 한 표를 던졌습니다. 결국 최종 문제 배치가 완성되었습니다.

 하지만 제일 사건사고가 많았던 것은 역시 제 문제인 별이 빛나는 밤에라고 생각합니다. 이에 대한 썰은 나중에 모아서 독립된 글로 풀겠습니다. (2)

대회가 시작되다

 대회 당일날 운영진 중 시간이 남는 사람들끼리 놀고 실시간 모니터링을 하러 선린인터넷고등학교 근처에서 모였고, 제가 사랑하는 규카츠를 먹을 수 있게 되었습니다. (사실 운영진 중 한 사람의 특이한 체질 때문에 식사 종류가 매우 제한되기는 했습니다) 규카츠를 먹으면서 수다를 좀 떨고, 제 문제인 별밤에 대한 토론이 오가고, 대회 시작 1분 전의 폭풍전야가 지나간 뒤 급하게 시간 제한을 1초로 변경했다는 공지글을 올림과 동시에 대회가 시작되었습니다. 저희는 그 시간에 스타벅스로 이동하는 길목에서 핸드폰으로 어 시작했네?를 외치고 있었습니다. 당연히 이러면 안 됩니다...

 스타벅스에서 대회 모니터링을 시작했습니다. 이동 시간이 편도로 2시간 가까이 되는 관계로, 노트북을 들고 오지 않아 옆에 있는 ahgus89의 노트북으로 "모"니터링을 진행했습니다. 시작한지 5분 안에 3문제의 퍼스트 솔브가 나왔습니다. 11분과 19분에 D와 E의 퍼스트 솔브가 나왔고, 잠잠하다가 40분을 조금 넘겨 F의 퍼스트 솔브가 나왔습니다. 사이에 재밌는 일도 있었습니다. 중간에 wookje님에게 E번 문제가 표절 아니냐는 장난성의 질문이 들어왔는데, 이 질문이 유사한 문제의 링크를 포함하고 있었습니다. 문제는 욱제님이 여기에 답변을 공개로 하는 바람에 이 질문이 유출될 뻔 한 일이 있었습니다. 급하게 비공개로 돌려 해결했지만 다시는 겪고 싶지 않은 끔찍한 경험이었습니다. 하나 더 재밌는 일도 있었습니다. 사실 G번 문제인 최단경로와 쿼리는 출제자 분이 대회 출제 이전에 같이 토론해주신 분이 있다고 해서 그분께 대회에 참가하지 말아 달라고 부탁을 드렸습니다. 그런데 예전에 그분이 사용하셨던 계정이 G의 first solve를 가져가는 일이 생겼고, 굉장히 당황스러웠습니다. 나중에 들어 보니 그 문제가 이미 과거에 출제된 문제라서(!) 본능적으로 제출하셨다고 합니다. 수상 과정에서 이를 어떻게 처리해야 하나 논의가 오갔고, 조용히 덮어 넘어가기로 결정했습니다. 결과적으로는 스무스하게 해결되었습니다. 그 외에는 G와 H가 풀리고, 올솔브가 나오면서 cki86201님이 1등을 확정지으셨고, 프리징을 하고, 특이한 일은 없었습니다. H가 imeimi님한테 bitset으로 뚫렸다는 소식도 있었는데, 뚫린 것엔 그닥 관심이 없었고 그저 F를 풀어주시지 않아 아쉬울 뿐이었습니다. :(

 대회 모니터링 중에 시간이 남았고 leejseo님이 에디토리얼을 바로 올리시는 것을 원하시는 것 같아 급하게 F번 문제의 풀이를 작성했습니다. 작성하기가 너무 귀찮았기에, 세세한 증명은 곰국에 맡겼습니다 ㅋㅋ

마무리하며

 전반적으로 짧은 시간 내에 급하게 준비한 대회였음에도 불구하고, E와 F 사이 난도 갭이 컸다는 것만 제외하면 문제 푼 사람 수도 그렇고 시간도 그렇고 노솔브도 2명밖에 없었다는 점에서 정말 깔끔한 셋이었다고 생각합니다. 데이터 오류나 디스크립션 관련 문제도 없었고, 큰 사건사고도 없었습니다. 매우 만족스럽습니다. 기회가 된다면 이번에 같이 운영한 분들과 내년에도 Goodbye, BOJ 2020을 준비해보고 싶습니다. 정말 친절하시고 열심히 준비해주신 운영진 분들 덕에 제 부족함에도 불구하고 대회가 잘 준비될 수 있었던 것 같습니다. 다시 한번 대회 운영진 분들과, 또 참가자 분들께도 감사드립니다.

2020년에 봐요!

 

P.S. junie는 왜 운영진 목록에 명단이 올라가 있는가? 라고 물어보시면 양꼬치라고밖에 대답할 수가 없습니다.
P.S.S. 제 문제인 별이 빛나는 밤에 관련되어 생략된 수많은 썰들은 다음 포스팅에 자세히 올라올 예정입니다.

edited: