SCPC 2025 후기

0. 서론

 

PS(Competitive Progamming)을 다시(그러면서도 이전에 해본 적 없는 정도로) 열심히 한지 약 6~7달이 지났다. PS를 열심히 한 이유는 딱히 거창한 이유가 있는 건 아니었다. 다시 PS를 열심히 하게 된 주된 원동력은 아마 1월말에 홍콩/중국에서 했던 IOI 금메달리스트 캠프 (https://qwerasdfzxcl.tistory.com/44) 때문이 큰 것 같다. 왜 원동력이 되었냐면.. 그냥 PS를 잘해서 얻은 기회로 매우 극진한 대접을 받으니까 기분이 되게 좋아져서 그렇게 이끌어진 거 같다. 아무튼 그 이후로 뭔가 잘해지고 싶은 마음이 들어서 계획을 세우고 PS를 열심히 했다.

기본적인 계획은 하루에 버추얼 한 개 이상 돌기: ARC와 코포 div1(또는 div1+2)을 번갈아가면서 도는 것이었고, 대충 ICPC 셋이나 OI 셋 같은 걸 도는 날에는 이미 그걸 5시간 도는 게 더 큰 일을 한 거니까 예외처리를 하기로 했다. 사실 생각해보면 그렇게 빡센 목표는 아니다. 나는 목표의 지속가능성을 중요하게 생각해서 내가 하다가 힘들 거 같은 정도의 목표를 잡지는 않았다. 대신 목표를 충족하고도 시간이 남을 때 내 마음대로 백준에서 문제를 풀든 랜디를 뽑든 그냥 자유롭게 PS를 더 많이 했다.
아무튼 지속가능한 목표를 세운 덕분에, 약 6개월동안 그 목표를 계속 지키면서 살아왔다. (시험기간에도 버추얼 돌았다..) 현재 시점에는 코포 div1을 2019년 꺼를 돌아야 되는데 딱히 스탠딩이 참조하기 좋은 것도 아니고 문제퀄도 애매한 거 같아서 코포는 그만뒀고 앳코더는 이틀에 한 번 정도는 하고 있다.

vcrating 그래프. 시작할 때는 vcrating 누텔라 찍으면 현실 누텔라도 찍을 줄 알았는데 딱히 그런 건 아니었다..

코드포스는 디스코드 TLE 봇 확장으로 버추얼 콘테스트 레이팅을 매겨주는 기능을 활용하여 어느정도 긴장감을 가지고 쳤고, ARC는 그냥 쳤다. 푼 문제 기록은 https://kenkoooo.com/atcoder/#/table/platter에서 볼 수 있다.

 

뭐 아쉽게도 내 코드포스 레이팅은 오히려 2월초에 찍은 2804에서 우하향했지만(왜 그런진 모르겠다) 실력이 예전보다 훨씬 늘었다는 생각이 들어서 나는 만족한다.

 

아무튼 본론으로 들어가서, 그렇게 PS를 열심히 하던 도중 자연스럽게 SCPC 2025에 참여하게 되었다.

 

1. 1차 예선

문제가 쉬웠어서 딱히 기억나는 건 없다. 5번 MST 문제가 되게 귀찮았다는 사실은 기억났다. 사실 굳이 올솔 안 해도 되는데 뭔가 그냥 그래도 만점 받고 싶어서 꾸역꾸역 풀었다.

 

2. 2차 예선

 

2차 예선은 중국 칭화대에서 열린 프로그래밍 캠프 일정과 겹쳐서 상당히 곤란하긴 했다. 예선 일정이 중국 시간 기준 오전 8시~오후 8시였고, 캠프 일정상 오전 9시반~오후 2시반동안 5시간 대회를 치고 이후 행사도 하고 저녁도 먹어야 되고 그러는 일정이라서 통과를 목표로 응시하려고 했다. 

뭐 그리고 통과는 했다. 약 다섯 시간 정도를 남겨둔 상황에서, 앞에서는 캠프 시상식을 비롯한 행사가 진행되고있는 와중에서 대회를 시작했고, 중간중간 문제를 풀어서 일단 진출에 제일 중요한 문제로 보이는 3번 문제부터 해결했다. 그리고 4번 문제에서 생각해뒀던 풀이를 열심히 구현했는데, 계속 맞지 못했다. 결국 일단 4번 문제는 접어두고 1 2번 문제를 순서대로 해결했고, 2시간반이 남은 시점에서 다시 4번 문제에 꼬라박았다. 그러다가 결국 풀이의 반례를 발견했고 일단 5번 문제와 4번 문제를 나이브를 짜서 긁었다. 4번 문제는 10번의 제출 기회 중 9번째에서 0점->170점으로 올렸다.. 이러니까 한 한 시간이 남았는데 그냥 밥 먹으러 가고 gg쳤다.

 

3. 본선

 

전날 잠을 제대로 못 자서 컨디션이 애매한 상태였다. 뭔가 아직 엄청 졸리진 않은데 심박수가 높아진 게 느껴지고 곧 있으면 진짜 졸릴 거 같은 상태? 전날 코드포스를 친 것의 영향이 있을 수도 있겠지만 사실 코포 전 19시에 졸려서 잤다가 다시 일어나서 코포 친 거를 생각하면 코포와 무관하게 수면패턴이 좀 꼬여있긴 했다. 그래서 SCPC 대회장에서 커피를 주길래 그냥 눈 딱 감고 한 번 먹어봤다. 원래 살면서 커피를 한 번도 안 마셔봤다... 아이스커피가 맛은 당연히 없었지만(원래 맛이 없는 건진 잘 모른다) 조금씩 마셔도 부작용이 나는 건 같진 않아서 그냥 계속 마셔서 다 마셨다. 대회중에 컨디션 이슈를 느낀 적은 없기 때문에 이 카페인이 긍정적인 작용을 해준 것 같다.

그리고 대회장에서 환경세팅을 하는데, Codeblock으로는 VS Code 실행이 안 된다는 사실을 발견했다. 내 노트북에 VSCode 세팅할 때도 gpt의 도움을 받아 세팅했던 터라 세팅이 뭔가 쉽지 않을 것 같았고, 그래도 C++ Code Runner 확장을 깔면 됐던 기억에 그걸 깔아봤는데 까는데 엄청난 시간이 소모됐고, 대회 시작 2분 전인가에 설치가 완료됐는데 그때 실행해보니 실행이 안 됐다.. 그래서 그냥 Codeblock에서 실행을 해야 하는 상황이었는데 잠깐 타자쳐본 결과 Codeblock에서는 인덴트가 너무 맘에 들지 않아서 VSCode에서 코드를 치고 복사붙여넣기로 Codeblock에서 실행을 하기로 했다. 사실 나는 평소에 온라인컴파일러(https://csacademy.com/workspace)를 자주 사용해서 이 부분에서는 오히려 이득을 봤다고 할 수 있다. VSCode에서 열심히 코딩하고 Codeblock에 복사붙여넣기한 다음 콘솔창에서 실행하는 과정에서 큰 불편함은 느끼지 못했다.

 

그리고 대회가 시작됐다. 1번 문제를 보자마자 코딩을 시작해서  4분에 AC를 받았다. (4분 1제출 100점) 그렇게 빠르게 코딩했다고는 생각하지 않았는데(코포였다고 생각하면 내 앞에 150명 정도 풀었을 거 같다.) 대회 퍼솔이어서 신기했다.

그리고 2번 문제를 봤는데, 일단 이상한 쿼리 줄이기 문제인데 만약 이게 후반 문제였다면 N에 대한 복잡도를 줄이는 방향의 문제일 거라고 생각했겠지만, 2번이었기 때문에 그냥 O(N^2) 스케일에서 열심히 줄이는 문제일 거라고 추측했고, 일단 적당히 버킷으로 나눠서 문제를 푸는 방향으로 생각했다. K=8~10 정도로 나눈 다음 2^K가지 비트를 직접 만들고 그것들을 합쳐서 전체를 다 구성하자는 식으로 발상을 했고 원래는 K*2^K으로 2^K가지 비트를 만든다고 생각해서 쿼리가 꽤 든다고 생각했지만 생각해보니 2^K번의 쿼리만 필요해서 15만7천번이 필요하다는 결론이 나왔다. 만점 컷이 15만5천인데 15만7천에서 더 유의미한 아이디어를 요구하는 건 좀 이상해서 커팅을 생각해봤고, 일단 2^K가지 비트를 만들 때 2^K-K-1번밖에 쓸 필요 없다는 것이랑 125번이 아니라 124번의 쿼리만 쓰면 된다는 생각이 나서 쿼리 횟수가 줄어들었고 이걸 구현해서 AC를 받았다. (22분 2제출 300점) 놀랍게도 이 문제도 퍼솔이어서 계속 1등이었다.

그리고 일단 3번을 읽었다. 우선 문제 이해를 완료한 뒤에 K=3일 때 어케 풀지를 생각하였다. 이때 1은 무조건 앞에 있는 작은 수, 3은 무조건 큰 수에 배정되어야 하고 2는 앞에 있는 건 작은 수 뒤에 있는 건 큰 수에 배정되는 게 이득이라 무조건 배정이 확정되고 이러면 K=3일 때 그 배정에서 확인만 그리디알고리즘으로 하면 풀 수 있다는 사실을 깨달았다. 사실 이게 정해를 떠올리는 데에 가장 크리티컬한 관찰이었던 것 같다. 그리고 이 관찰을 확장해서 K=4일 때도 O(N)가지 후보가 존재하고 각각에서 판정을 O(N)에 하면 O(N^2)에 풀린다는 것을 관찰했다. 이제 이걸 더 줄이기만 하면 됐는데, 각각의 후보에 대해서 O(N)을 쓰는 건 당연히 비효율적이니까 후보집합을 옮기는 걸 잘하면 된다고 생각했고 결국 잘하면 됐다. 자세한 설명은 내가 솔브드 디코에 쓴 설명으로 대체

암튼 이 풀이를 내고나서, 사실 126점은 쉬워보이는 상황이었기에 이걸 고민한 다음 합쳐서 짤지 아니면 일단 짜놓을지 고민했는데, 체크포인트를 만들어둘 필요성이 느껴져서 174점을 일단 받기로 하고 열심히 구현했다. 무겁다면 무거운 구현이었고 열심히 짰는데 0점을 받았다. (70분 3제출 300점) K=3일 때도 틀린다는 사실이었기에 오히려 K=3인 케이스에서 나이브를 짜고 스트레스를 돌려서 반례를 찾고 디버깅을 했고 틀린 부분을 고쳐서 174점을 받았다. (85분 4제출 474점)

그리고 나머지 126점을 고민해봤는데, 스코어보드에서 느껴지던대로 그 파트는 되게 쉬웠다. 앞에서 K=3을 푼다고 한 관찰을 그대로 쓰면 됐다. 빠르게 만점을 받았다. (93분 5제출 600점) 이 시점에 1 2 3번 전부다 퍼솔이고 단독 1등을 달리고 있었어서 뭔가 1등을 하는 게 아니냐는 들뜸이 있었다...

그리고 잠시 문제를 둘러보면서 다음 풀이를 고민해보다가, 5번 문제가 너무 애드혹하다는 생각이 들었다. 일단 위치가 5번이라서 어려울 확률이 높고 애드혹 문제를 잡는다는 것은 너무 막막한 길을 걸어가는 것이라, 1등만을 노리는 게 아니라 수상기회가 있는 나한테는 맞지 않는 길인 것 같았다. 그래서 5번을 버리겠다는 결단을 내리고 5번의 자명섭태인 60점을 긁기로 했다. 5-2에서 SCC를 딸 필요가 없는데 땄다는 등(사실 알고보니 오히려 여기서 SCC를 딴 것이 풀태에 힌트가 되기도 하긴 한다) 사소한 찐빠가 있었지만 60점을 무사히 긁어냈고(121분 6제출 660점) 4번에 올인을 하기로 했다. 이 시점에 스코어보드에 구사과님이 3번을 제출도 안 하고 4번에 꼬라박고 있는 것이 보였고, 4번을 나도 풀어야 한다는 생각이 들었다.

의외로 풀이는 빨리 나왔다. 그냥 트리dp를 상태 몇 개 쓰면서 잘 쓰면 되는데 상태관리할 게 좀 많아서 구사과님이 왜 계속 틀리고있었는지도 알 것 같았다. (짜기 시작할 때쯤 시점에 구사과님이 42를 거쳐 300으로 올라갔다.) 그리고 이거를 풀고 다시 5번으로 돌아간다는 마인드로 열심히 구현해서 제출을 딱 했는데, 0점을 받았다. (166분 7제출 660점) 그 후 코드에 있는 몇 가지 오류들을 고친 다음 다시 계속 제출했는데 계속 오답을 받았다. 내리 6번 계속 오답을 받았고 시간은 계속 흘러 40분 남짓만 남은 상황이 되었다. 정말 잘 풀리고 있었던 대회였는데 이제 진짜 위기감이 느껴지는 상황. 그때 구사과님이 42를 거쳐 300으로 올라간 것이 생각나서 42점에 해당하는 N<=10 섭태의 나이브를 짜고 나이브를 AC받은 후 나이브로 스트레스를 돌리기로 했다. 심지어 나이브조차도 잘못 짜서 한 번 틀렸지만 아무튼 모든 간선의 경우의 수를 다 보는 O(N*3^N) 풀이로 42점을 무사히 받아냈다. (211분 14제출 702점) 그리고 스트레스 테스팅을 하는 코드를 짠 다음 돌려보니 진짜로 반례가 나왔다! 반례가 왜 나오는지 분석해본 결과 정말정말 코드의 오류를 찾을 수 있었고 이 부분을 고치니까 스트레스테스팅으로 생성된 테스트케이스 100개에서 모두 정답을 출력하는 것을 확인했다. 이 코드를 제출해서 만점을 받았고, 15분 남은 상황이었다... (225분 15제출 960점)

사실 15분 남은 상황에서 더 할 수 있는 건 사실 없다고 봐도 무방했고 안도의 한숨을 매우 크게 들이쉬고 내쉰 다음 5번 문제를 대충 읽어봤지만 이미 풀 수 없다는 생각이 들어서 제대로 집중이 안 됐다. 스코어보드상으로 이동현이 무조건 내 위인 게 확정적인 상황이라, 이동현이 1등상을 받으면 내가 2등상을 받을 확률이 높아지는 상황이라 이동현 응원이나 하고 있었다...

 

최종결과

 

대회를 끝나고 점수를 수소문해보니까 960점이 한 명 더 있었지만 15번을 제출한 나보다도 제출횟수가 더 많아서 내가 패널티에서 앞서서 아직 2등상권을 유지하는 상황이었다. 5번 만점자는 두 명이었는데 한 명은 점수가 낮다고 알려줬고 한 명은 구사과님으로 추측되는 상황이었다. 또한 3번 만점자 전원을 찾는 데에 성공해서 5번 만점자가 정말 구사과님이 맞다면 구사과님이 1등상을 받아도 2등상 말석에 들어갈 수 있는 상황이었다. 근데 구사과님이 정말 5번 만점을 받았는지 확답을 안 내려줘서 끝까지 가슴을 졸이게 했다.... 아무튼 결론적으로는 구사과님이 정말 5번 만점이어서 나도 2등상을 받을 수 있었다. SCPC 2등상이라고 인터뷰도 하고(머리도 제대로 정돈되지 않은 상태였다...) 아무튼 기분좋게 집에 갈 수 있었다.

 

결산을 내보면 올해 참가한 모든 오프라인 개인대회에서 좋은 성적을 거두고 있다. (헬로 2025 2등, SCSC 대회 1등, 코드트리 ACPC 3등, SCPC 2등상(3등)) 서론에서 언급했듯 PS를 열심히 한 게 결실을 이루고 있는 것 같아서 기분좋고 사실 팀대회는 여태껏 계속 잘하지 못하고 있는데 (UCPC 15 14 7등, ICPC 8 12등) 이번에는 ICPC도 잘 쳐서 한 해를 완벽하게 마무리할 수 있으면 참 좋을 것 같다.