[SCPC] SCPC 2025 Round 1 (1차 예선) & Round 2 (2차 예선) 후기

후기가 많이 늦었습니다. 원래 1차 예선 글과 2차 예선 글로 나누어서 올리려고 했는데, 1차 예선 글을 쓰기 전에 2차 예선이 시작되어버리는 바람에 이왕 이렇게 된 거 1차와 2차를 합쳐서 올리기로 하였습니다. 2차 예선이 치러진 지 2주 가량 정도가 지났는데, 그 사이에 추가 합격 결과도 기다리느라 더 늦어졌네요 ㅎㅎ;; 추가 합격 결과는 ..
워낙 2차 예선에서 우여곡절을 겪어서 개인 기록용으로 자세하게 적어보았습니다.
 

[Round 1 (1차 예선)]

총점 750 / 1150

 
1차 예선 컷이 보통 1솔~2솔 근처이기 때문에 1차 예선은 부담없이 치렀습니다. 다만 1번 문제에서 자신 있게 코드를 제출했다가 부분점수를 맞아서 살짝 당황했는데.. 5000원인 경우에 조건 분기를 좀 더 세밀하게 조정해줬어야 하는데 생각없이 짜는 바람에 2트만에 솔브를 띄울 수 있었습니다. 1번에서 한 번 틀리고 나니 집중력이 올라서 2, 3번은 무난하게 흘러갔습니다. 3솔 상황에서 그만둘까 했는데 이왕 푸는 거 끝까지 한 번 해보기로 하고 4번을 풀어보기로 하였습니다. 제곱 풀이는 쉽게 떠올릴 수 있는데, 그 풀이를 제곱 시간 밑으로 떨어뜨리는 것이 살짝 어려웠습니다. 슬라이딩 윈도우 비스무리한 풀이가 나왔는데 구현 중간에 인덱싱에서 많이 버벅거려서 고생 끝에 AC를 띄울 수 있었습니다. 1차 예선에서 4솔브를 한 건 처음이라 5번도 한 번 도전해보았는데, 풀이가 쉽게 떠오르지 않았고 그나마 떠올린 풀이도 구현이 상당히 복잡해보여서 몇 번 시도해보다가 그만두게 되었습니다.
 
이번 1차 예선은 상대적으로 쉬운 1, 2번의 만점자 수가 예년 SCPC 1차 때보다 적지만, 1번부터 4번까지의 만점자 수가 거의 고르게 되어있다는 점이 특이했습니다. 참가 인원이 줄어든 건지, 난이도가 어려웠던 건지 가늠이 잘 되지 않았지만 어쨌든 1차 예선은 통과했기 때문에 2차 예선을 찬찬히 준비해보기로 했습니다.
 
 
 
 
 

[Round 2 (2차 예선)]

총점 415 / 1500

 
2차 예선은 시작부터 걱정이 많았습니다. 2차 예선은 토요일 9시부터 21시까지 치러지는데, 7월 말부터 알바를 하게 되면서 토요일에 무한정 시간을 비워두기가 어려웠습니다. 12시간을 전부 투자해도 본선에 붙을 수 있을지 없을지 장담할 수 없는데 문제에 집중할 수 있는 시간도 줄어들면 아마 올해도 본선 진출은 어렵지 않을까 하는 생각이 들었지만.... 작년 2차 예선 때 안일한 생각으로 아쉽게 떨어진 걸 생각하면, 주어진 시간만이라도 최대한 활용해서 최선을 다하는 것이 낫지 않을까 하는 마음으로 2차 예선을 임해보기로 하였습니다.
 
알바가 11시부터여서 그 때까지는 최대한 문제들을 고민해보고 구현까지 끝마쳐보려고 했습니다. 다만 문제는 1번 난이도가 상당했다는 점인데.. 처음에 읽어보고 너무 어려워서 당황하다가 만점자 수가 굉장히 천천히 오르는 걸 보고 "나만 어려운 게 아니구나" 하는 생각이 들어 다시 침착하게 문제를 고민해보기로 했습니다. DP 풀이를 떠올렸는데, 그 과정에서 예전에 풀었었던 이 문제의 아이디어가 많은 도움이 되었습니다. '실제 양'뿐만이 아닌 '필요 양' 또한 같이 넘긴다는 점에서 신선한 충격을 받았던 기억이 있었는데 이렇게 도움이 될 줄은 몰랐습니다. 구현에서 어이없는 실수를 하나 해서 부분점수(17점)을 받았다가 후딱 고치고 만점을 받아낼 수 있었습니다.
 
 나머지 문제들도 한 번씩 읽어보았는데, 감이 오는 문제가 단 하나도 없었습니다. 2번은 행 번호가 10^9까지 주어질 수 있다는 점에서 까다로웠고, 3번은 서브태스크1("실력 한계치의 값이 모두 같다.")의 간단한 투포인터 풀이만 떠올랐으며, 4번은 문제 자체를 이해하기도 어려웠고, 5번은 문자열이 나와서 반가웠지만 아쉽게도 문자열 알고리즘을 쓰는 문제는 아닌 것 같았습니다. 1번을 30분만에 빠르게 풀어냈지만 나머지 문제들의 풀이를 내기가 너무 어려웠습니다. 다행히도 알바가 학원 알바인지라, 문제들을 프린트해서 잠깐잠깐씩 고민해보기로 하였습니다. 
 
그렇게 한참을 고민하다가.. 2번 문제 풀이에 감이 잡히기 시작했습니다. '오프라인 쿼리 + 세그'를 이용한 풀이였는데 여전히 10^9개의 행이 걸림돌이었고, 그 부분을 해결하기 위해서 좌표압축도 같이 사용하기로 하였습니다. 어차피 코딩을 할 수 있는 상황은 아니었기 때문에 풀이를 줄글로 먼저 정리해보고, 집에 가면 바로 타이핑할 수 있게 손코딩도 미리 해놓았습니다. 
3번도 사실 풀이가 나왔는데, 이게 정당한 풀이인지도 모르겠고 시간복잡도도 제곱인 것 같아서 일단 풀이 스케치만 해놓았습니다.

2번 풀이 스케치 / 3번 풀이 스케치 / 2번 손코딩

 
문제는.. 구현하고 제출해보니 2번에서 부분점수(100점)가 나왔다는 점인데, 서브태스크별 점수를 확인해보니, '페인트칠이 된 칸의 개수'는 맞게 구했는데 '최소 붓질 횟수'가 맞지 않아 만점의 반타작이 나왔다는 것을 알게 되었습니다. 고생고생해서 몇 번을 틀리고 고친 끝에야 만점을 받아낼 수 있었습니다. 3번은 어느 한 쪽을 투포인터로 돌린 다음, 나머지 쪽을 투 포인터 구간에 끼워넣는 방식으로 구현했는데, 풀이가 잘못된 건지 구현이 잘못된 건지 계속 부분점수(23점)만 나왔습니다. 될 듯 말 듯 해 보였는데 결국 10회 제출 횟수에 다다랐고 3번은 23점으로 끝나게 되었습니다. 4번은 여전히 문제가 이해되지 않아서 5번을 고민해보기로 했습니다. 서브태스크2("모든 쿼리에 대해, 문자열에서 모든 A는 모든 B, C보다 앞서 있다.)는 B와 C의 위치만 고려하면 되기 때문에 이를 이용한 세그 풀이로 부분점수(42점)을 따낼 수 있었습니다. 
 
150 + 200 + 23 + 0 + 42 = 415점으로 2차 예선이 마무리되었는데, 점수가 너무 낮다는 생각이 들어서 아무래도 본선은 가지 못할 듯 싶었습니다. 그런데 운이 좋게도 예비합격 메일을 받게 되었고 예비번호도 3번인지라 "혹시..?"하는 기대감이 들기 시작했습니다.  조마조마한 마음으로 기다리다가 어제 드디어.. 

 대학교에 다닐 동안 SCPC 본선을 한 번이라도 가볼 수 있을까 하는 마음이었는데, 정말 좋은 기회로 본선에 참가해볼 수 있게 되었습니다..! 5등상이 없어지면서 수상 인원은 줄어들었지만, 본선 경험을 해볼 수 있다는 것 자체만으로도 (개인적으로는) 엄청난 성과이고 무엇보다도 6년 만에 SCPC 본선이 오프라인으로 치러진다는 점도 기대가 되는 부분입니다. 재밌게 하고 오겠습니다!