SCPC 2025 후기

8/29에 SCPC 본선을 치고 왔다. 최근 친 (전설의 UCPC를 포함한) 대회들 중에서도 가장 도파민이 강하게 올라온 대회였기에 후기를 작성하고자 한다.

대회 전

올해 SCPC는 역대급으로 수상컷이 높았다고 생각한다. 가장 큰 이유는 올해 SCPC 5등상 부문이 사라진 것으로, 총 수상자 수가 38명 -> 18명으로 무려 반토막이 되어버렸다. 그 외로도 아직 수상 2회를 못하고 방을 안뺀 고수들이 너무나도 많았다. 미리 사전조사를 해본 결과, 무려 현역 레드인 인원이 수상 가능한 인원보다 많았고, 홀의 결혼 정리에 의해 레드가 수상을 실패하는 일이 무조건 발생하게 되는 빡빡한 대회가 예정되었다.. 개인적으로 내년엔 개별 상금을 조금 삭감하더라도 수상 인원을 더 늘려줬으면 하는 마음이다.

나는 올해 WF 후에 다녀올 영국 여행에서 돈이 엄청나게 깨질 것이 분명하였기에, 대회 전에 3등상 상금 쌀먹을 목표로 잡았다. 작년 라인업과 비교했을 때 코포 2700~2800의 국가권력급 코더들이 더 많아졌기에 이게 되려나라는 생각이 꽤 들었으나(방 좀 빼다오..), 저 당시 개인폼이 꽤 괜찮았기에 어떻게든 될 거라는 마인드로 쳤다.

대회 날

대회 당일 새벽에 엄청나게 재밌는 컨텐츠가 있었는데, 그것은 바로 leo020630의 코드포스 레드 승급전이다. 아마 조만간 본인이 후기를 작성할 것 같은데, 미리 조금 스포를 하자면... 대회 당시 Div1-D2 문제를 풀지 못하면 레드를 못 감 -> 대회 종료 5분 전까지 광란의 제출쇼를 했고, 놀랍게도 결국 AC를 맞음 -> 하지만 패널티 이슈로 레드 컷보다 2점이 모자라는 점수에 안착한다는 캐럿 예측이 뜸 -> 근데 사소한 문제 오류로 생겨서 캐럿보다 2점이 더 오를 수도 있다는 가능성이 생김 // 이라는 레전드 상황이 발생했고, 이 때문에 나랑 래오는 레이팅 반영을 기다리며 새벽 6시까지 잠을 안 자는 블런더를 저질러버렸다. 참고로 저 컨텐츠의 결말은 더욱 재미있으니 나중에 따로 찾아보기를 바란다. 아무튼 약 4시간 정도 수면을 한 후, AllSolvedIn1557 멤버로 합류해 아침을 든든하게 먹은 후 대회장에 도착했다.

대회 직전

대회장에 좀 빠듯하게 도착해서 사람들과 인사를 많이 나누지 못했다. 늘 보던 연세대 Endgame 팀들이랑 디스코드에서 보던 다른 지인분들과 조금 인사를 나누고 바로 착석했다.

늘 있는 개회식을 들은 후 세팅 시간이 주어졌는데, 노트북 환경에서 vsc 세팅이 상당히 이상했다. 일단 g++ 사용이 불가능했고, 안 그래도 졸려 죽겠는데 뭐 어디서부터 고쳐야 하는건지 모르겠어서 되게 짜증났었는데, 다행히 바로 뒤에 있던 이름모를컴퓨터초고수님 + JYJin 님이 환경 변수 세팅을 하면 된다고 알려주셔서 시작 직전에 컴파일이 되게 세팅하는 데 성공했다. 그럼에도 sanitizer를 포함 내 linux 세팅과 실제 환경에 꽤 차이가 있었고, 키보드도 꽤 불편해서(나중에 그냥 치우고 노트북 키보드로 코딩했다) 되게 불안한 상태로 대회가 시작되었다.

대회 중

1번 +100 (0:00 ~ 0:22)

대회 전 악재가 그대로 적용되었는지, 1번부터 되차게 말려버렸다. 간단한 2차원 DP 문제인데 처음에 이상한 2^4 state DP를 짜다가 예제컷 당했고, 나중에 풀이를 수정하고 냈는데도 이상한 실수로 2번이나 틀리고 맞았다; 무려 22분을 소요하고 나서야 100점을 받고 다음 문제로 넘어갔다.

2번 +200 (0:22 ~ 1:23) 

보자마자 "그냥 하나씩 추가하면 되는거 아님?"을 생각했으나, 제한이 생각보다 꽤 빡빡해 통하지 않았다. 하지만 이걸 1개씩이 아닌 8개씩으로 추가한다는 마인드를 가지면 아슬아슬하게 풀테 제한 안에 들어오는 풀이를 만들 수 있고, 바로 짜기 시작했다. 하지만 아직 환경에 적응이 덜 돼서, 계속해서 자잘한 구현 실수가 터지면서 0점을 띄우는 일이 반복되었다. 이 당시 auto 구문을 컴파일러 버전 이슈로 사용할 수 없었는데, 이걸 고치려고 꽤 많은 시간을 소모했으나 결국 못 고치면서 여러모로 멘탈이 엄청 갈렸다. 저 당시 엄청 날카로운 혼잣말을 꽤 뱉었던 것 같아서 대회 끝나고 옆 사람한테 사과했다.

JOAT

아무튼 여러 이슈를 다 잡고 나니 풀테를 받을 수 있었다. 이때 무려 대회시작 후 1시간 20분이 지나있었고, 3번 풀테를 받은 사람도 꽤 있었어서 되게 심리적으로 힘들었다.

3번 +0, 5번 +24 (1:23 ~ 2:21) 

마음을 다잡고 3번을 읽었는데, 이때 또 블런더를 저지르고 만다. 3번은 문제 인자로 정수 $K$를 주고, 지문을 잘 관찰하면 $K \le 4$라는 조건이 있다. 그러나 마음이 조급해져서인지 저 조건을 읽지 못한채로 꽤 깊게 문제를 생각했고, 무슨 말도 안되는 general matching 문제가 자꾸 튀어나와서 다시 문제를 읽고 나서야 저 조건을 봐버렸다. 이 덕분에 잘못된 문제에서 풀이BFS가 돌아간 상태의 뇌로 문제를 다시 생각해야 했고, 관찰들이 뒤엉켜버려서 섭태1 풀이조차 내지 못해버리는 참사가 일어난다.

개조졌다 싶은 생각으로 스코어보드를 봤는데, 누군진 모르지만 개하수같은 le...o?026...?30? 같은 닉을 단 사람이 5-1 섭테를 긁었고, 쌀먹 각이 보여서 바로 보러 갔다. 실제로 그냥 작은 N에서 TSP 같은걸 하면 되어서 바로 짜기 시작했는데, 아직도 손이 적응이 안되서 엄청 틀리고 겨우 5-1 긁기에 성공했다. (+24, 2:21)

JOAT2

 

3번 +15, 5번 +60 (2:21 ~ 2:51) 

잠시 5번에서 refresh를 하고 오니 3-1에 대한 갈피가 조금 잡혔고, (2,3) 매칭을 최대한 뒤에서부터 하면 된다는 관찰을 찾아서 바로 짜서 맞았다. (+15, 2:35) 이때부터 손이 좀 풀렸다.

3-1번을 맞은 후 잠시 4번을 봤으나, 문제 세팅이 좀 어지러워보였고 4번 섭테를 긁은 사람이 당시에 없었다. 대신 5-2 섭태를 긁은 사람이 꽤 있었어서 그쪽으로 노선을 정했다. 5-2 섭태 조건을 읽으니 무조건 최대 길이의 경로가 존재할 거라는 심증이 들었고, 귀납적으로 점이 N-1개일때 구한 경로에 새로운 점 1개를 붙이는 방법을 고민하다 보니 쉽게 풀이가 나왔다. 바로 구현에 들어가 섭태를 긁고 5번 60점을 얻는데 성공했다. (+60, 2:51)

대회 당시 앞 스크린에 스코어보드로 1~20등을 보여줬는데, 놀랍게도 5-2를 맞은 순간 처음으로 내 아이디가 스코어보드에 등장했다. 이마저도 얼마 안 있어 다시 밀려났고, 3시간 시점부터 스코어보드가 프리즈되었기에 사실상 내가 슼보에 등장한 시간은 3분 이하였던 것 같다. 나중에 뒤풀이에서 다른 사람들한테 들어보니, 이 사람이 out of 20일리가 없어서 내가 당연히 이상한 분탕 아이디로 신분을 숨기고 있다 생각했다고 한다. 어이x.

3번 +174 (2:51 ~ 3:31)

5-2를 긁은 후 다시 3번으로 돌아왔다. 여기서 또 블런더를 저질렀는데, 3-4, 3-5의 섭태 제한이 $K=3$인 것을 발견하지 못해 $K=4$ 풀이를 생각하고 있었다. 사실 이건 나름 근거가 있는 ^문제잘못읽기^ 인데, 일반적으로 섭태 문제에서 마지막 섭태는 앞쪽 섭태의 모든 제한을 포함하는 섭태인 경우가 많고, 섭태 2,3이 $K=4$인 경우를 이미 다루고 있기 때문에 섭태 4,5 또한 당연히 $K=4$라고 생각했다. 하지만 이 문제의 경우 섭태 구조가 양갈래길처럼 되어있고, 나는 이런 식의 구성을 아예 처음 보기에 저런 사고가 생기고 만 것이다. 이와 관련해서 나도리님이 찰진 비유를 한 게 있어 돚거를 좀 해왔다.

https://swoon1.tistory.com/44

 

이 때문에 아무리 생각해도 3-4, 3-5 풀이가 안 나와 3-2, 3-3으로 도망쳤다. 그런데 3-1을 긁을 때 한 (2,3)-뒤에서부터매칭 관찰은 놀랍게도 3-2에서 (3,4)-뒤에서부터매칭과 동일했고, N이 작을 때는 (3,4) 매칭의 개수를 고정하고 3-1의 나이브를 돌려도 시간복잡도가 괜찮다. 원래 짜둔 3-1 코드로 이걸 빠르게 구현했고, 섭태 긁기에 성공했다. 이 시점에서 4등상 수상은 어찌저찌 하겠다는 생각이 들었다. (+66, 3:02)

그리고 얼마 안있어 (1,2)-앞에서부터매칭 관찰도 이와 같이 할 수 있음을 깨달았고, 이걸 정리해보니 적당히 스위핑을 하며 세그트리를 관리하면 된다는 결론을 얻었다. 구현이 은근 더러웠지만, 본격적으로 손이 좀 풀렸기에 할 수 있다고 믿고 짰고, 크게 안 말리고 섭태 긁기에 성공했다! (+174, 3:31)

5번 +156 (3:31 ~ 3:56)

이후 노선을 또 정해야 했다. 처음엔 3-4, 3-5를 다시 고민했으나 여전히 $K=4$인 채로 문제를 알고 있었고, 너무 어려운게 영 이상해서 다시 문제 지문 관찰을 해보니 그제서야 3-4, 3-5가 $K=3$이라는 커닝시티식 섭테였다는 사실을 깨달았다. 위에서도 언급했지만, 문제를 잘못 읽은 상태로 포맷된 뇌를 원본 문제에 다시 사용하는 건 엄청나게 위험한 일이고, 난 시원하게 3번을 유기하기로 했다. 그럼 남은 선택지는 4번과 5번인데, 3번 풀테를 못 긁은 시점에서 3등상을 노리려면 꽤 큰 섭테를 긁어야 했으며, 4번은 문제의 inspiration도 제대로 안 잡혀있고 섭태 점수도 별로 안줬기 때문에 유기하고 5번을 긁기로 했다.

근데 5번을 보다보니, 어떤 vertex v에 대해 v에 도달할 수 있는 모든 점들은 사실 path로 잘 합칠 수 있다는 생각이 들었다. 5-2에서 항상 최대 경로 길이가 존재했던 것, 5-4 섭태에서 "임의의 u에서 v로 항상 도달 가능함"이라는 문장, 그리고 예제까지, 모든 정황이 저 추측에 부합했고, 이 추측을 기반으로 열심히 종이에 정리를 해보니 그냥 Factos였다. 결국 문제는 1) "자신에게 도달할 수 있는 vertex가 가장 많은 정점 찾기"를 한 후, 2) 정한 root로 path를 구성하기- 를 하면 되고, 다행히도 이는 5-3의 제한($N, M \le 5000$)에서 둘다 쉽게 가능하다. 여기까지 생각이 도달한 후 구현을 위해 컴퓨터를 잡은 순간 대회가 단 13분 남았음을 깨달았고 잠시 패닉이 왔는데, 짜면 400만원이라는 생각으로 정신을 차리고 열심히 구현에 들어갔다. 1)은 그냥 DFS N번 돌리기라 안 어렵고, 2)가 좀 빡센데 5-2의 코드를 거의 그대로 사용해서 짜니 생각보다 할만해서 금방 구현이 끝났고, 대회 종료 4분을 남기고 다다스식 60번 제출을 할 생각으로 일단 내고 봤는데 다행히 한 번에 맞았다! (+156, 3:56)

AC 직후 5-4가 5-3과 크게 차이가 없음을 안 후 약간 슬펐지만, 앞 시간대에서 지옥끝까지 말린 것을 생각하면 충분히 만족할 결과였기에 가벼운 마음으로 대회를 마칠 수 있었다.

최종 점수

대회 후

종료 후 친한 사람들이랑 모여 문제 풀이 얘기랑 점수 얘기를 좀 하면서 노가리를 깠다. 확실히 5등상이 사라져서 수상컷이 높아진 게 눈에 보였고, "이 사람이 못 타야해?" 싶은 분들도 꽤 계셔서 씁쓸했다. 내 점수는 630점. 아마 2솔 + alpha단들 중에서는 제일 높고 3솔+ 단들한테는 전부 밀리는 점수일 것이다. 그런데 3번 4번 만점자가 각각 6, 9명이고, 이중 상당수는 둘 다 풀었거나, SCPC 졸업생반들의 작품일 것이기에 3등상 막차나 뒤에서 2번째 정도를 예상하며 시상식까지 기다렸다.

곧이어 AI 트랙 시상식 후에 알고리즘 부문 시상식이 시작됐고, 4등상 목록에 내가 없는 것을 확인한 후 속으로 나이스! 를 외쳤다.

3등! 옆에 무서운 사람들이 많다

2025 2024. 이름 순서가 이상하다...

아무튼 대회 직후 AllSolvedIn1557 + 친한 사람들이랑 늘 가던 치킨집에 가서 잔뜩 먹고, 수상턱으로 내 테이블에 치킨을 쏜 후에 귀가했다. 바로 다음 날이 월파 출국이기 때문에 많은 응원을 받았던 것으로 기억한다. 으흐흐.

후기

대회 직후 5번이 꿀통이라고 주장하고 다녔는데, 나중에 알고 보니 아마 5-3만을 긁은 사람이 나밖에 없는 것 같다. 실제로 960(100+200+300+300+60)단들이 3분이나 계셨고, 저분들이 2등3등4등을 차례로 먹은걸 생각해보면 5-3 긁기는 고수 행동이 맞는듯 하다. 실력이 많이 는것 같아서 뿌듯하면서도, 블런더를 안 저지르고 문제를 조?금??더? 잘 풀었으면 더 높은 결과가 있었을 법 한 것 같아서 살짝 아쉽기도 하다. 그래도 이 정도면 엄청나게 좋은 결과가 맞기에 충분히 만족한다.

 

이제 공식적으로 우승이 아니면 상을 못타는 졸업반이 되어버렸다. 현역 시절 때 졸업반 선생님들을 봤을때는 되게 멋지면서도 왜 저렇게까지 매달리나 싶은 맘이 있었는데, 막상 직접 되어보니 뭔가 더 잘하면 나도 우승할 수 있지 않을까란 욕심이 든다. 난 $\epsilon$의 확률을 $1$로 만들 수 있는 사람이니 여기서 안 접고 계속 도전해볼 생각이다. 많은 응원 부탁드리고, 이 글을 보는 졸업반 고수분들은 부디 내년에는 굳이 더운데 나오지 말고 집에서 쉬어주시길 부탁해본다.

 

다음 글에는 WF 후기로 뵙겠다.