SCPC 2025 후기

SCPC에서 상을 이미 2번 받은 나는 더 이상 상을 받을 수가 없다. 그래서 이번 scpc는 오프라인 대회장에 가는 것을 위해서 치기로 했다.

 

예선 1차

이때는 몰입캠프 중에 있었다. 1차는 조금만 풀면 통과해서 밤에 대충 쳤다. 만점을 받았다.

예선 2차

꽤나 어려웠다... 1번 2번은 쉽게 풀었는데 3번에서 막혔다. 

스위핑을 하는 복잡한 풀이가 나와서 오랜 시간 구체화만 하다가, 이 문제를 이렇게 풀게 되었다가는 디버깅만 하다가 끝날 것 같다는 생각이 들었다. 그래서 4번에서 서브태스크 2를 긁기로 했다.

설상가상 4번 서브태스크도 왜인지 모르게 틀렸다. 중간에 멘탈이 나가서 잠깐 샤워를 하고 왔다. 차분하기 읽어보니까 내가 점수 조건을 잘못 읽었다는 것을 깨달았다. 지문에 있는 기준은 d_G(x, y) / d_H'(x, y)를 최소화하는 것이었는데, 이걸 d_H(x, y) / d_H'(x, y)를 최소화하는 것을 잘못 읽었다. 그래서 기존에 했던 관찰은 모두 무효화 되었고, 처음부터 다시 풀어야 되는 상황이 발생한 것이다! 이때 대략 시작한지 6시간 쯤 되었다. 그런데 천천히 생각해보니까, (x, y)를 간선에 대해서만 관찰하면 된다는 것을 깨달았고, 빠르게 서브태스크를 긁었다.

 

이제 3번을 풀어야 했다. 사람들이 많이 풀었다는 것을 보고서 나는 나의 풀이보다 훨씬 간단한 풀이가 있다고 생각했다. 실제로 아주 간단한 풀이를 찾았고, 코딩을 하려는데 좌표압축이 걸렸다. 생각보다 많은 좌표를 봐야 한다고 착각한 나는, 구체화를 오랜 시간동안 하면서 16N개의 좌표를 우겨넣어 세그먼트 트리를 쓰자는 결론이 나왔다. 이대로 짜다가는 tle가 날 것 같아서, 조금 더 관찰을 해서 8N개로 줄여서 코딩을 했다. 생각보다 긴 코드를 짜서 WA가 뜰지도 모르는 상황에서 부분점수가 나왔다! 나의 코드가 어느 정도 맞다는 부분에서 안심을 했고, 시간을 조금만 더 줄이면 되겠다고 생각을 했다. 세그먼트 트리를 사용하는 것을 deque를 이용해 최적화를 해서 겨우 만점을 받았다.

 

남는 시간 동안 4번과 5번을 봤는데, 5번은 아인타님이 냈을 것 같이 생겼는데 아무리 생각해도 못 풀겠었고, 4번은 그냥 어떻게 하라는지 모르겠어서 이대로 끝났다. 나중에 보니까 컷이 123번을 풀면 여유롭게 통과할 수 있어서 본선을 진출했다. 6시간 지점에 1번, 2번만 풀었다는 것을 보면 퍼포먼스가 안정적이지 못하다는 것을 알 수 있다.

 

본선

대회장에 딱 맞춰서 도착했다. 일찍 가서 scpc 쿠키도둑이 되어보자는 나의 계획이 무산되어서 아쉬웠다. 가니까 몰입캠프에서 본 형도 있고, 평소에 ps하는 사람들도 많이 보여서 좋았다. 그리고 앞에 스코어보드가 띄워지는 대회를 할 생각에 신이 났다.

 

대회가 시작하고 1번을 무난하게 풀었다. 2번을 보는데, 적당한 상수 k에 대해 n^2/k에 풀라는 것 같았다. 그래서 대략적인 계산만 하고 코딩을 했는데 64점이 나왔다. 정확한 쿼리 개수는 n/k(n + k * 2^(k-1))이었던 것 같다. 이때 스코어보드에 만점 몇 명만 있고 나 혼자 64점이어서 대수롭지 않게 생각했다. 좀 있으면 만점을 받을 수 있을 줄 알았는데, 그렇지 않았다. 랜덤 같은 것을 섞는지 좀 고민을 하다가 더 이상 들여다보아도 점수가 안 오를 것 같아서 3번으로 갔다. 이때쯤에 스코어보드에 123번 만점자가 여러 명 생겨서 이번 대회 1등은 아주 글러먹었다는 것을 깨닫고 대충 치기 시작했다.

 

3번은 아인타님이 낸 것이라고 추측했다. 나는 하나둘셋과 점 연결하기를 풀었고, 내가 직접 하나둘셋을 출제하기도 했다. 아인타님의 문제를 많이 풀었기 때문에 3번도 풀 수 있을 것이라고 생각했다. 대략적인 풀이가 나오고 코딩하기 시작했는데, 짜다가 잘못된 풀이임을 깨달았다. 이때가 1시간 30분이 지났을 때였다. 스코어보드에 1번 2번 풀고 3번 대략 긁은 사람들은 많은데, 나는 2번도 못 풀고 3번도 진전이 없다는 생각에 자괴감이 들었다. 

 

3번에 대한 그림을 하염없이 노트에 그리고 있을 때, 갑자기 그림을 보고 풀이가 생각났다. 1과 4는 항상 오른쪽/왼쪽에 있는 수와 매칭한다는 자명한 사실을 사용하면, 12로 매칭하는 2와 34로 매칭하는 3의 경우의 수가 n가지 밖에 없다는 것이다! 그래서 대충 n^2은 알겠는데, 제곱 미만에는 어떻게 할지 고민하고 있었다. 사실 제곱을 알면 제곱미만으로 줄이는 것은 적당히 하면 풀린다. 그래서 코딩을 했고, 2시간 30분 시점에 174점을 받았다!

 

좀 어려운 문제를 풀었으니 긴장이 풀려서 3번 만점 받는 것도 오래 걸렸다. dp 식 세우는데 틀린 식을 2번쯤 세우고 나서 초기화 실수를 여러 번 하고나서야 만점을 받을 수 있었다. 이때가 3시간 30분 시점이다. 아주 호되게 반성을 해야된다.

 

이제 2번을 풀어야겠다고 결심을 했다. 이전에 생각한 풀이의 쿼리 개수는 n/k(n + k * 2^(k-1))인데, k*2^(k-1)에서 k를 떼어내면 되겠다고 생각을 했다. 이게 만점을 받으려면 n/k(n + 2^(k-1)) 정도는 되어야 되는데, 내 풀이에서는 적어도 2^k번의 쿼리를 사용해야 되어서 좀 의아했다. 2^(k+1) + 2 * 2^(k/2) 같은 meet in the middle을 생각하면서 고전하고 있었는데, 깔끔한 2^(k+1) 풀이가 떠올랐다. n/k (n + 2^(k+1))을 바로 짜서 86점을 받았다. 이때 k=6이었다.

 

생각보다 점수가 낮아서 아쉬워하고 있었다. 곰곰히 생각을 해봤는데, 위 식이 최소일 때는 k=7일 때이었다! k=7로 바꿔서 제출을 해서 120점을 받았다. 그냥 아무거나 제출하는 마음으로 k=8을 제출했는데 156점이 나왔다. 계산을 했을 때는 k=7이 최적인데, 점수가 올라서 좀 당황했다. 점수 배점이 120점 이상부터는 굉장히 촘촘하게 되어있어서 조금만 더 쿼리를 줄이면 만점이 나오겠다고 생각했다. 그런데 이제 정말 줄일 곳이 안 남아있었고, 2번 만점은 못 받고 대충 4번 5번 문제 지문만 읽다가 대회가 끝났다.

 

마지막에 사람들과 대화해보니 나는 행별로 k개씩 묶어서 처리했는데, 열별로 k개씩 묶어서 처리하면 아주 쉽게 풀린다고 한다. 아주 쉬운 풀이가 있으니까 67명이나 풀지 않았을까? 왜 그런 생각을 못 했는지 잘 모르겠다. 하지만 6명 밖에 못 푼 3번을 풀었으니 괜찮다. 3번도 못 풀었으면 엉엉 울지 않았을까 싶다.

 

특별상을 받았다! 2번을 못푼 시점부터 대회를 말아먹었다고 생각했는데, 운이 좋아 3번도 풀고 2번도 잘 긁어서 특별상을 받게 되니까 너무 기분이 좋았다. 갤럭시 버즈를 받았다. 이번에 구사과님이 1등을 했던데, 자세한 상황을 들어보니 정말 극적인 1등이었던 것 같다. scpc 졸업을 축하드립니다!

 

대회가 끝나고 미국에서 오랜만에 한국에 온 구사과와 함께 998244353명이서 맛밥을 먹었다. 사실 이게 오프라인 대회에서 제일 재미있는 부분이 아닌가 싶다. 다음 scpc도 오프라인 대회로 치면 좋을 것 같다!