SCPC 2025 후기

대회 시작 전

컴퓨터 세팅 설정 시간을 몇 분 준다. 근데 워낙 이상한 환경이라서 설정 시간 안에 제대로 세팅하기가 쉽지 않다. 다행이도 옆자리에 앉아있던 신민철 (fefe) 가 환경 변수 설정 등을 알려줘서 VS Code를 사용할 수 있게 되었다. 이 세팅 때문에 우승 여부가 갈렸을 수도 있다. 무한한 감사를 표한다.

1번

아주 간단한 문제였는데, 이런 버그를 만들고 찾지 못했다.

int ret = 0;  
{  
int ret = 0;  
...
}  
return ret;

컴파일도 사실상 처음 해 본 거라, 여러 상황을 의심하다가 오래 걸렸던 것 같다. 결국 20분 걸려서 솔브.

2번

빡빡해 보이는 제한이 있는 문제였다. 열을 8개씩 묶으면 될 거라고 생각했는데, python이 깔려있지 않아 손으로 $256 * 125 + 125000$ 을 했더니 만점 제한에 살짝 못 미쳤다. 그런데 C++로 $b \in {7, 8, 9}$ 에 대해 $(2^b - b - 1) * N/b + (N/b-1)N$ 을 계산해보니 $b = 8$에서 만점 제한 이하가 찍혔다. 그래서 처음 생각한 풀이를 짜서 AC를 받았다.

두 문제를 풀었을 때 1등과 20분 정도의 시간 차이가 났다. 시작이 느려서 느낌이 좋지 않았다.

4번

3번을 읽어봤고 생각해봤는데 풀이가 잘 떠오르지 않았다. $K \le 4$ 인걸 보면 깔끔한 풀이는 없을 거 같아서 4번으로 도망갔다.

4번은 "깔끔하고 간단한" 풀이가 존재하는 문제긴 했다. 이제 문제는 이걸 트리 DP로 구현하는 건데, DP 상태 인자가 많아서 그 부분은 전혀 간단하지 않았다. 처음에 문제 상황을 제대로 정리하고 들어가지 못했고, 짜다가 틀려서 놓친 부분을 추가하는 식으로 이 때문에 DP 인자가 각 정점당 2~3개에서 5개로 증가했다. 코딩 다 하고 제출까지 한 뒤에 새로 틀린 부분을 찾고 새로운 인자를 추가하는 식으로 작업하다가멘탈이 나갔다.

VS Code에서 Linter 설정은 결국 실패해서, 코드 auto indent가 없이 코딩을 진행했다. 트리 DP 구현을 위해 한 7중 정도의 for문이 있었는데, 중괄호가 닫히지 않았다고 컴파일이 되지 않았다. auto indent가 없어서 코드들의 줄이 안 맞아서, 10분동안 빠진 중괄호만 찾고 있었다. 이 때도 멘탈이 갈렸는데, 괄호 짝을 맞춘 이후에는 AC를 받았다. 이때는 이미 4번 first solve도 나오고 3번 솔버도 많이 나온 상태.

5번

4번을 풀고 얼마 안되어서 이미 스코어보드에 960점이 있었다. 속도전으로는 승산이 없는 상태였기 때문에 5번에서 무조건 점수를 냈어야 했다.

서브태스크에 완전 방향 그래프가 있었는데 난 그 문제를 푸는 방법을 두 가지 알고 있었다. 하나는 그냥 아무 생각 없이 인접 행렬을 comparator로 정렬하는 풀이고, 다른 하나는 끝점을 고정한 후 postorder를 찍어서 해밀턴 경로를 찾는 방식. 근데 x->y, y->x 방향의 간선이 모두 존재할 수 있음을 간과하다가 푸는 데 오래 걸렸다.

모든 정점의 indegree가 1인 그래프는 문제 조건을 자명히 만족한다. 그래서 처음에는 모든 정점의 indegree를 1로 만드는 방향으로 접근했다. 만약에 정점의 indegree가 2 이상이면, 들어오는 정점들을 모두 방문하는 해밀턴 경로가 존재하니 (36점), 해밀턴 경로의 끝점을 유일한 indegree로 지정해준 후 pseudotree에서 쉬운 문제를 해결할 수 있다고 생각했다. 근데 이 접근을 잘 생각해보니까 자기들끼리 사이클을 형성할 수 있다는 이슈가 있었다. 그 이슈를 해결하기 위해서 사이클 노드가 생겼을 때 거기서 사이클로 들어오는 간선을 자료구조를 사용해서 찾아주는 방향으로 생각했는데, 이렇게 되니까 각 정점의 in-degree를 small-to-large 같은 걸로 관리해야 해서, 문제의 풀이가 너무 복잡해졌다.

이때 약간 대회가 망한 것 같다는 느낌을 받았다. 마지막 문제이기 때문에 정해가 대회 중에 짤 수 없는 아주 복잡한 문제일 수도 있다고 생각했다. 제곱 서브태스크를 푸는 식으로 접근하면 3번에서 꽤 유의미한 점수를 내야 하는데 이것도 시간이 부족해 보였다. 내년을 생각하면서 절망한 채로 체념하고 있었는데...

대회 창에서 5번 만점자가 1명 등장했다. (종료 30분 전쯤) 이 때 풀이가 아주 복잡한 문제는 아닐거라는 직감을 받았고, 간단한 풀이들을 생각했다. 어쨌든 완전 방향 그래프도 이 문제의 입력 중 하나이니, 만점 풀이가 존재한다면 완전 방향 그래프에서 해밀턴 경로를 구할 수 있어야 할 것이다. 그래서 완전 방향 그래프를 해결하는 풀이들을 고치는 방향으로 생각해 보았다. 인접 행렬을 정렬하는 건 말이 안 되는 것 같으니, 각 정점에 대해서 해당 정점을 도달할 수 있는 모든 정점을 DFS로 방문하고 그 postorder가 경로이기를 기도했다. 이는 놀랍게도 사실이었고, 그래서 모든 정점에 대해서 해당 정점에서 끝나는 경로를 DFS로 찾는 $O(nm)$ 풀이를 제출해서 맞았다. (종료 20분 전)

마지막 이슈는 최적의 끝점을 어떻게 찾느냐였다. 이것도 처음에는 좋은 방법이 보이지 않았는데, 잘 생각해보니 SCC를 구하고 longest path를 찾으면 입력 그래프의 성질에 따라서 그게 reachable한 정점의 개수와 동일하다는 것을 깨달았다. 그래서 급하게 SCC를 짜서 만점을 받았다. (종료 10분 전)

3번

남은 10분동안 떨면서 3번의 15점을 구현했다. 3번을 아주 고민해보지 않은 것은 아니라서, 15점은 구현만 하면 됐다. 생각보다 구현이 간단해서 5분 정도 안에 점수를 올렸다. 그 와중에 3번의 counting 서브태스크가 상당히 쉽다는 것을 깨달아서 슬퍼졌다.

대회 후

최종 100 / 200 / 15 / 300 / 400 = 1015점 으로 마무리.

프리즈가 된 1시간 동안 5번에서 60점 초과를 받은 사람이 단 한명도 없을지 의문이었는데, 또 한편으로는 5번 문제가 60점 / 400점 사이에 유의미한 서브태스크가 있어보이지는 않아서 가능성이 있다고도 생각했다. 난 느낌상 다른 5번 만점자가 4솔브는 아닐 거라고 짐작했다.

일단 대회가 끝나고 바로 5번 만점자를 찾았고, 실제로 4솔브가 아니었다. 그러면 우승 가능성이 있으니, 5번을 풀었다는 사실을 공개하지 않기로 했다 (ㅎㅎ). 얘기해 보니 960점으로 끝낸 사람들이 3명 정도 있길래, 기대를 품고 시상식을 기다렸다. 그리고 특별상에 내 이름이 호명되지 않아서 우승을 직감했다 ㅎㅎ

그렇게 1등상을 수상했다.

내가 1000점을 얻은 게 마지막 10분이니, 대회 시간 절대다수를 수상권 밖에 있다가 마지막 10분 뒤집기로 우승을 했다. 10년 넘게 대회하면서 이렇게 "역전승" 으로 이겨본 게 처음인거 같다. 보통 초반부터 상위권을 계속 유지하지 않으면 후반에 말리는 경우가 많았던 것 같은데, 5번에서 운이 엄청나게 좋았다고 생각한다. 한편으로 960점 수상자가 3명이나 되는걸 보면 속도전에서는 상대가 안 되는 것 같고, 그런 면에서 이번에 결국 은퇴할 수 있어서 다행이라고 생각했다. 

아무튼 PS 하면서 손에 꼽을 수 있을 정도로 예상하기 어렵고 짜릿한 우승이었다.