Reply Code Challenge 2023 - Standard Edition 후기

Reply Code Challenge 2023 - Standard Edition에 참가했습니다. 박신욱님, 장래오님, jthis님과 함께 팀 '4 Oranges Can't Win'으로 참가했고, 운이 좋게도 전체 3,990팀 중 35위를 차지했습니다. 그 과정에 대해 얘기해보겠습니다.

 

팀 구성하기

Google Hash Code 2023 팀원을 구합니다.

 

원래 저는 Google Hash Code에 참가하려고 했습니다. 그래서 모 커뮤니티에 Google Hash Code 팀원을 모집하는 글을 업로드했습니다. 글을 올린 후 감사하게도 박신욱님께서 연락을 주셨습니다. 그 후 Hello, BOJ 2023! 때 출제자로 합을 맞췄던 한동규님께 팀 제의를 드렸고, 흔쾌히 수락해주셨습니다. 남은 팀원 한 분을 고민하던 찰나에 박신욱님이 강희원님께 제의를 드려 함께하게 되었습니다. 다들 잘하시는 분들이고, 좋은 팀을 만들었다는 생각에 기대에 부풀어 있었습니다. 그런데...

 

구글의 모든 알고리즘 대회가 폐지되었습니다

 

그런데 Hash Code, Code Jam를 비롯한 구글의 알고리즘 대회들이 모두 폐지되었습니다. 얼마 전 구글의 대규모 정리해고 때 대회 관리자 분들이 해고되었다는 소식은 들었는데, 결국 이런 결과로 이어졌습니다. 아쉽지만 어쩔 수 없다는 생각에 포기하려고 했습니다.

 

그러던 중 우연히 Hash Code와 유사한 대회인 Reply Code Challenge를 알게 되었습니다. 다시 대회를 나갈 수 있다는 생각에 팀원 분들께 연락을 드렸습니다. 대회 날까지 며칠 남지 않은 시점에 갑작스럽게 연락을 드렸고, 아쉽게도 한동규님, 강희원님께서는 일정 상의 이유로 참가하기 힘들 것 같다는 답변을 주셨습니다.

 

강희원님이 소개해주신 장래오님, jthis님이 새롭게 합류해주셨습니다. 이렇게 Reply Code Challenge 2023 - Standard Edition에 참가하게 되었습니다.

 

여기서 한 가지 교훈을 얻었습니다. 좋은 팀을 만들었고, 이런 기회는 자주 있지 않습니다. 따라서 Hash Code가 폐지되었을 때, 곧바로 유사한 활동을 찾아보는 편이 좋았을 것 같습니다. 우연히 Reply Code Challenge를 알게 되어 참가하기는 했지만, 몰랐다면 아무것도 하지 못했을테니 좋은 기회를 놓치는 셈이 됩니다.

 

대회 전 상황

대단한 준비를 했으면 좋았겠지만, 대회가 얼마 남지 않았었습니다. 다들 바쁘신 분들이라 많은 준비를 요청드리기 부담스럽기도 했습니다. 이런 글을 읽고 상대적으로 부족한 것 같아 걱정이 좀 되었지만, 준비 없이 부딪혀보기로 했습니다.

 

대회 시간은 CET(중앙유럽 표준시) 기준 16시 30분부터 20시 30분까지였습니다. 한국 시간으로는 새벽 00시 30분부터 04시 30분까지입니다. 시차 적응이 필요하다고 생각해서 저는 대회 전날에도 04시 30분까지 깨어있었습니다. 좋은 컨디션으로 대회를 치르고 싶었습니다. 전 세계를 대상으로 개최하는 대회는 종종 이 부분이 힘이 듭니다. Codeforces, Hacker Cup 등등..

 

대회 전 Reply 측에서 공식 라이브 방송을 진행했습니다. 방송을 보다보니 대회를 치른다는 실감이 났습니다. 설레는 마음으로 대회를 시작했습니다.

 

대회 중 진행 상황

문제 상황은 대략적으로 다음과 같습니다:

$N \times M$ 크기의 격자가 주어집니다. 각 칸 $(i, j)$에는 값 $V_{i, j}$ ($-10\,000 \leq V_{i, j} \leq 10\,000$)가 주어집니다. 이후 $K$마리의 뱀들이 주어집니다. $K$마리의 뱀들은 각각 길이가 주어지고, 주어진 길이만큼 격자를 덮어야 합니다. 이때 한 칸에 두 마리 이상의 뱀들이 있거나, 한 뱀이 같은 칸을 두 번 이상 덮어서는 안됩니다. 뱀이 좌표의 왼쪽 끝까지 갈 때에는 같은 행의 오른쪽 끝에서 이어지고, 아래쪽 끝까지 갈 때에는 같은 열의 위쪽 끝에서 이어집니다(and vice versa). 어떤 칸에는 웜홀이 존재해서 뱀은 한 웜홀을 통해 다른 웜홀로 이동할 수 있습니다. 이 때 뱀들이 덮은 모든 칸의 값들의 합이 최대한 커지도록 뱀들을 배치해야 합니다.

 

휴리스틱 대회이기 때문에 당연히 최적해를 구할 수는 없습니다(혹은 적어도 최적해를 구하는 것이 매우 어렵습니다). 먼저 모든 뱀들을 가로, 또는 세로로 펼치고, 길이가 긴 뱀부터 값을 최대화할 수 있는 행, 또는 열에 넣는 풀이를 생각했습니다. 웜홀은 아예 이용하지 않았습니다. 신욱님과 제가 이러한 코드를 짜서 여러 번 제출했지만, 출력이 문제 조건에 맞지 않는다는 답변만 계속해서 받았습니다.

 

The solution file is not correctly formatted

 

대회 내내 이 문제는 저희 팀을 괴롭혔습니다. 래오님, jthis님도 같은 문제를 계속 겪었습니다. 저희 팀이 어떤 큰 착각을 한 것은 아니고, 그만큼 문제에서 요구하는 구현이 까다로웠습니다. 그러던 중 제가 적절한 답을 출력하는데 성공했고, 빠르게 제출한 결과 실시간 순위 1위를 차지했습니다. 적당히 쉬운 풀이를 빠르게 구현하는 전략이 유효했던 것 같습니다. 대회 시작 후 1시간 즈음이었습니다.

 

팀 4 Oranges Can't Win, 실시간 1위

 

그 후 jthis님이 휴리스틱 풀이를 제출했고, 3개의 데이터에서 더 높은 점수를 받는데 성공했습니다. 레오님도 휴리스틱 풀이를 짰지만, 어떤 이유에서인지 계속해서 출력이 문제 조건에 맞지 않았습니다.

 

저희 팀은 일반적인 알고리즘 대회에는 능숙하지만, 휴리스틱 대회에 대한 전문성은 없었기 때문에, 일정 수준 이상의 점수를 받기가 힘들었습니다. 저희보다 2배 이상 점수가 높은 팀들이 있었는데, 아마도 저희가 모르는 휴리스틱 전략을 사용했을 듯 합니다. 대회가 진행될수록 등수는 점점 떨어졌습니다.

 

그러던 중 6번 데이터가 추가되었습니다. 원래 문제에는 1개의 예제와 5개의 데이터만이 존재했습니다. 신욱님이 6번 데이터를 분석한 결과, 양수 값을 가지는 모든 칸들이 인접해 있고, 그 둘레를 웜홀들이 둘러싸고 있는 꼴의 데이터라는 것을 알아냈습니다. 둘레 바깥의 모든 칸은 음수 값을 가지고 있었습니다. jthis님이 적절한 휴리스틱 풀이를 제출하여, 6번 데이터에서 약 900만점을 받는데 성공했습니다. 6번 데이터에서 얻을 수 있는 점수의 상한이 약 1,000만점 정도였기에 적당히 만족스러운 결과였습니다.

 

대회가 끝나고 저희 팀은 전체 3,990팀 중 35위를 차지했습니다. 예상치 못했던 좋은 결과였습니다. 그리고 정말 재밌었습니다. 대회 시간 내내 진심으로 즐길 수 있었습니다. 그렇게 대회가 마무리되고 저는 당일 오전 9시에 수업이 있었기 때문에 그대로 동아리 방에서 잠에 들었습니다.

 

팀 4 Oranges Can't Win, 최종 35위

 

생각은 해보았으나 구현할 엄두가 나지 않은 풀이가 하나 있습니다. 5번 데이터의 경우 $N, M$이 모두 $2\,000$ 정도의 스케일이었습니다. 그리고 제 기억이 옳다면 양수 값을 가지는 칸의 개수가 약 $5 \times 10^6$개였습니다^[각주:1]. 또한 모든 뱀들의 길이의 합은 약 $10^6$였습니다. 또한 양수 값을 가지는 칸들의 분포는 랜덤이었습니다. 따라서 대략 양수 값을 가지는 칸이 $5$개 있을 때 그 중 $1$칸을 밟는 풀이를 생각해볼 수 있습니다.

 

이제 뱀들을 모두 합쳐 하나의 뱀으로 생각할 수 있습니다. $N \times M$ 크기의 격자를 $7 \times 7$ 크기의 격자들로 나누고, 각각의 $7 \times 7$ 격자 내에서 가능한 뱀의 이동 방향을 고정하여 dag로 생각할 수 있습니다. 예를 들어 오른쪽과 아래쪽으로만 이동하도록 한다면 dag가 됩니다. 방향을 고정하였기 때문에 각각의 $7 \times 7$ 격자에서 뱀은 $13$개의 칸을 밟게 됩니다. $49$개의 칸 중 $13$개만을 밟으므로 적당히 효율적일 것이라 추측해볼 수 있습니다.

 

이제 각각의 $7 \times 7$ 격자 내에서 최댓값 dag dp를 구하고^[각주:2], 이때 뱀의 이동 방향을 잘 설정하면 dp 값들을 합칠 수 있습니다. 뱀의 위치를 출력해야 하므로, dp 역추적도 구현해야 합니다. 아마도 구현에 성공했다면 높은 점수를 받았을 것 같기는 하지만, 이 풀이는 구현이 아주 어렵습니다. 대회 시간 내내 구현한다고 해도 성공할 자신이 많지는 않습니다. 

 

대략 이런 꼴입니다. 빨간색 선은 뱀의 이동 경로를 의미합니다.

 

마무리

별다른 준비가 없었음에도 좋은 결과로 마무리되어 좋았습니다. 다들 새벽 시간대가 부담스러웠을 텐데 흔쾌히 참여해주셔서 감사합니다. 개인적으로는 휴리스틱 대회에 재미를 느꼈습니다. 정확한 답을 찾아야 하는 일반적인 알고리즘 대회와 달리, 적당히 효과적으로 보이는 풀이를 시도해 볼 수 있다는 점이 매력적이었습니다. 앞으로도 비슷한 대회를 알게 된다면 참가할 것 같습니다. 이상 후기 끝!

 

1. 다시 확인해보니 약 $2.3 \times 10^6$개였습니다. [본문으로]
2. 혹은 최댓값을 완전 탐색으로 구할 수도 있습니다. 시간복잡도가 $\mathcal{O}(2^{13} \times \frac{NM}{49})$이기는 하지만요. [본문으로]