GBS Coding Contest 2021 후기

서론

여러 우여곡절 끝에 본 대회와 오픈 콘테스트가 모두 끝났다.

첫 대회 운영이었음에도 불구하고 많은 역할을 맡게 되어서 정말 좋은 경험이 되었지만, 그만큼 놓친 것도 많아서 아쉬웠다.

이번 경험을 바탕으로 내년, 내후년에는 더욱 수준 높은 대회를 열 수 있기를 희망한다.

Special thanks to...

부족한 저와 함께 출제와 운영에 적극적으로 참여해주신 권도현과 장래오, 이채준, 박수빈 선배님,

검수로 참여하셔서 많은 조언을 해주시고 대회를 살려주신 나정휘, 신민철, 오주원, 최유빈, 최준석님,

후원 문의에 선뜻 응해주신 넥슨 사회공헌팀과 대회 운영을 도와주신 스타트링크 관계자분들,

그리고 대회에 관심을 가지고 참여해주신 모든 분께 정말 말로 표현하지 못할 만큼 감사드립니다.

문제 구상

출제는 2021년 초에 열린 제6회 GCC가 끝나자마자 시작했다. 기록을 보니 겨울방학 동안 5문제 정도를 생각했었는데, 다 대회에 나올 만한 퀄리티는 아니었다.

프린트 전달은 개학식 다음 날에 뽑혔다. ㅋㅋ 물리 선생님이 포스트잇을 나눠주시는 방법을 조금 각색해서 만들었다.

비숍 투어는 여름 방학 즈음에 만들어졌다. 개인적으로 잘 만든 문제라고 생각한다.

그 외에도 많은 문제를 생각했지만, 내 마음에 들지 않거나 기존의 문제와 겹치고, 실수로 공개해 버리는 등의 여러 이유로 출제 리스트에 올릴 문제가 많이 없었다. 그런데 출제 리스트를 보니 브론즈, 실버 급의 쉬운 문제가 부족해서 내가 쉬운 문제를 채우기로 마음먹었다.

아이디어가 필요 없는 구현 문제를 동아리 이름인 ALPS와 어떻게 연관 지을까 고민하다가 나온 문제가 알프수다. 조건을 어떻게 줘야 모두가 납득할 만한 '알프수'가 될지를 많이 고민했다. 알프스 컨셉을 유지하기 위해 '산 모양'의 조건을 조금 까다롭게 설정했다.

정수론 문제를 내긴 해야 할 것 같아서 내가 푼 정수론 문제를 둘러보다가 갓 문제 Range GCD를 발견했다. $gcd(a,b)=gcd(a,b-a)$ 의 아이디어를 등차수열에 적용하면 적당할 것 같았고, 슈퍼 웰논 등차수열의 합 공식을 함께 묻는 문제인 등차수열과 쿼리를 구상했다.

데이터 제작

데이터 제작이 진짜 어렵고 귀찮다. 보통 폴리곤을 이용해 각 문제의 데이터를 만드는데, 나와 도현이는 당연하게도 폴리곤을 써본 적이 없어서 애를 많이 먹었다. 그래도 evenharder님의 블로그를 여러 번 정독하고, 다른 분들의 제너레이터 & 밸리데이터를 열어보면서 어느 정도 감을 잡았던 것 같다.

비숍 투어의 데이터는 만들기 어렵지 않았다. 각 섭태별 저격해야 하는 코드가 명확해서 솔직히 손으로 만들어도 될 뻔했다.

알프수의 데이터는... 후에 서술하겠지만 망해버렸다. 일단 알프수가 되는 경우가 많이 없어서 알프수를 생성하는 제너레이터가 필요했다. 이를 조금 변형해서 알프수와 비슷한 논알프수를 생성하는 제너레이터도 만들었고, 손으로 데이터 몇 개를 추가했다. 그런데 섭태 3의 직접 만든 데이터가 많이 부실했다.

프린트 전달은 그래프 문제답게 데이터 만들기가 정말 힘들었다. 거기다 내가 섭태로 힌트를 준답시고 (제너레이터가) 복잡한 섭태를 만드는 바람에 일이 좀 커졌다. 제너레이터와 밸리데이터를 죄다 BFS로 짜야해서 좀 고생했다.

등차수열과 쿼리는 무지성 자료구조를 통과시킬 건지에 대한 고민이 필요했다. 이를 저격하려면 오버플로우를 고려해 모드를 쓰는 등의 처리가 필요한데, 그냥 깔끔한 문제를 만들기 위해 자료구조 풀이를 허용해주기로 했다. 데이터는 랜덤, 워스트, 로우 케이스를 적당히 섞으면 충분하다.

본 대회 (2021.12.29)

대회 전날까지 장소와 상품이 준비가 안 되어 있었고, 당일에는 대회용 계정이 전체 공개되는 소란이 있었지만, 대회는 예정대로 시작했다.

시작하고 얼마 지나지 않아 A에서 다 같이 35점을 받는 모습에 출제자로서 뿌듯함을 느꼈다. 대다수의 팀이 함정을 늦지 않게 빠져나와 다행이었다.

B도 빠르게 풀리고 있었는데, 갑자기 70점을 받는 팀이 등장해서 엄청 당황했다. 70점 코드는 몇 가지 조건을 놓치고 있었고, 내 제너레이터가 이것조차 거르지 못했다는 것이 믿기지 않았다. 일단 해당 코드를 저격하는 데이터를 몇 개 추가해 빠르게 재채점을 돌렸다.

C와 D에서 참가자들이 고전하고 있는 사이에 갑작스럽게 F가 풀렸다. 직관이 중요한 문제에서 1학년 팀들이 좋은 모습을 보여주었고, 2학년들은 기대 이하였다. ㅋㅋ

아이디어와 구현 면에서 까다로운 편이라고 생각했던 C가 다음으로 풀렸다. BFS와 DFS를 짤 줄 아는 사람에게는 쉬웠나 보다. 여담으로, 이 문제의 디스크립션을 내가 깔끔하게 작성하지 못해서 검수자 분이 한 번 갈아엎어 주셨고 오픈 대회 중에도 수정이 있었다.

D가 85분 만에 솔브가 나왔고, 총 5팀이 해결했는데 그중 한 팀이 세그로 뚫어주셨다. 나머지 팀 중에는 정해에 접근했음에도 오버플로우에서 벗어나지 못한 팀이 꽤 있어서 정말 가슴 아팠다. 개인적으로 이 문제가 많이 풀리지 못한 게 상당히 아쉬웠다. $l, r$ 의 범위를 더 크게 잡았으면 오버플로우를 고려해보지 않았을까?

다음으로는 E, G, H가 순서대로 풀렸다. E는 비교적 앞 쪽에 배치했음에도 두 팀 밖에 풀지 못했는데, 나는 이 그리디 아이디어가 쉽지 않았다고 생각한다. (실제로 검수 때도 혼자 이해를 못 했다.) G는 냅색 DP의 좋은 연습 문제로 손색이 없었고, H는 지문을 보면 알겠지만 달팽이 문제와 비슷한 느낌이 났다.

I와 J는 0솔을 어느 정도 예상하고 있었지만, 그래도 I 정도는 누군가 풀어주지 않을까 기대했었다. 두 문제 모두 정말 멋진 문제들이라 한번 도전해보는 것을 추천한다.

오픈 대회 (2022.01.02)

오픈 날짜를 1월 1일에 잡으면 아무도 안 풀겠지 싶어서 아무 생각 없이 일요일로 정했는데, 생각해보니 내가 학원에 있는 시간이었다. 그래서 스코어보드나 채점 현황을 모니터링하지 못했다.

대회 시작할 타이밍엔 쉬는 시간이라 눈팅하고 있었다. 그런데 얼마 지나지 않아 B번에서 또 70점이 나와서 그냥 학원 수업을 포기하고 데이터를 단단히 고쳤다. (라고 생각했는데 얼마 전에 데추주 글이 올라왔다)

다행히 내가 출제한 문제에서 다른 이슈가 터지진 않았고, 거듭된 재채점 끝에 어찌어찌 대회가 마무리되었다.

aeren님, cozyyg님, kdh9949님이 상당히 빠른 시간 내에 올솔을 해주셨다. 수학, 애드혹 범벅이라 전체적으로 코드가 짧은 것도 한 몫한 것 같다.

마무리

모든 것이 새로운 경험이었고, 이번 대회를 통해 정말 많이 배우고 얻어갈 수 있었다. 본 대회 시작 후 오픈 대회가 끝날 때까지 10번이 넘는 데이터 수정이 있었을 정도로 운영이 미흡했지만, 그럼에도 많은 분들이 격려와 응원, 그리고 큰 도움을 주셔서 무사히 대회를 마칠 수 있었다. 참가자 분들도 대회를 즐기셨기를, 그리고 앞으로도 대회 문제들이 잊혀지지 않고 꾸준히 풀리길 바란다.

대회 링크 : GBS Coding Contest 2021 Open

문제 링크 : GBS Coding Contest 2021

공식 풀이 : GCC 2021 Official Solution

종료 글 : GBS Coding Contest 2021 Open 종료