SCPC 2021 2차 예선, 본선 후기

2차 예선

 

1차 예선 문제들을 보고 이제는 "상수 최적화 프로그래밍 대회 (SCPC)"을 좀 벗어나려고 하는줄 알았는데, 2차 예선으로 그렇지 않다는 것을 똑똑히 보여주었다.

 

1, 2, 3번 문제 모두 상수 최적화 여부에 따라 정답/시간 초과가 갈렸다.

4번 문제는 가장 작은 테스트케이스만 통과시키려고 짠 완전탐색 코드가 시간복잡도상 통과하면 안될 중간 테스트케이스까지 통과하는 (??) 일도 있었다.

 

결국 각종 문제로 123번 문제를 애매하게 푼 사람들은 결국 저 5번 문제를 얼마나 많이 긁었는지 여부에 따라 본선 진출 여부가 갈렸다. 내 2차 예선 점수는 100+200+154+209+33 = 696점이었는데, 만약 5번 문제를 손도 안댔다면 본선에 진출하지 못했을 것이다.

 

논란의 여지가 꽤 있는 문제셋이었다고 생각한다.

---

본선

https://anz1217.tistory.com/134

SCPC 2021 본선 키트

 

이번엔 장패드와 티셔츠를 안줬다. 왤까?

 

아무튼 이번에도 온라인으로 본선을 치뤘다. 치팅 위험이 매우 큰 방식이기 때문에 작년과 같이 꼼꼼한 체크가 있었지만, 분위기 자체는 작년처럼 빡빡하지 않았었던것 같다.

 

문제가 작년보다 더 어려워 졌다. 중후반 문제의 난이도는 아마도 비슷했다고 생각하지만, 앞 문제의 난이도가 매우 올랐다. 원래 1번 문제는 본선을 갔다면 못 풀 수 없는 난이도로 주어졌는데, 이번에는 시작부터 모두의 멘탈을 부수고 시작했다.

 

타임라인

1번 문제를 봤다. 문제를 대충 읽었을 때는 꽤 할만하다고 생각했는데, 가면 갈수록 정리가 안되는 것을 느꼈다. 뭔가 규칙을 찾기위해 공책에 한 3장정도 깜지를 쓰면서 1시간 정도 노가다를 하다가 이건 좀 아닌것 같아 다른 문제를 먼저 보기로 했다.

 

2번 문제를 봤다. 2차 예선의 "그 산탄총"이 다시 나오는 걸보고 집에 가고 싶어졌다. 이번엔 푸는 방법도 감이 오지 않았고, 작은 테스트케이스들을 풀자니 또 상수 최적화에 고통받을거 같아 일단 다음 문제를 보기로 했다.

 

3번 문제를 봤다.

문제를 천천히 읽어보는 중에 "그냥 Suffix Array 만들면 끝나는거 아닌가?" 하고 틀릴각오로 제출했는데, 만점이었다 (??)

SCPC에서 SA를 \(O(n\log^2 n)\)으로 짜면 시간초과고, \(O(n\log n)\)으로 짜야 통과되는 문제를 본 적이 있는데, 이번엔 웬일로 로그제곱으로도 만점이 나오는걸 보고 조금 당황했다.

 

1:51 3번 만점

 

4, 5번은 예전하고 난이도가 비슷하다면 아마 손도 못댈 것이라는 생각이 들었다. 그래도 그나마 만점자가 있는 1번을 다시 풀어보기로 했다.

결국 뭔가 잘 끼워맞춘 추한 Case Work로 정리를 할 수 있었다. 다 잘 나오는것 같이 보여서 제출하니 이게 맞다고 한다. 그래도 한시름 놓을 수 있었다. 이 쯤에서 아마 특별상은 받을 수 있을 것이라 생각했다.

 

2:36 1번 만점

 

일단 부분문제를 가능한 많이 긁고, 남는 시간은 2번에 투자해야겠다고 생각했다.

4번 문제를 봤다.

\(O(n^3)\) dp로 풀 수 있는 작은 테스트케이스가 있었고, 그대로 제출해서 부분 점수를 얻을 수 있었다.

 

2:50 4번 143점

 

끝나고 나서 든 생각인데, 4번도 만점을 받을만 해 보여서 차라리 4번을 좀 봤더라면 풀 수 있지 않았을까 하는 아쉬움이 남았었다.

 

5번은 부분점수가 출력하는 값에 따라 식으로 주어지는 걸 보고 생각을 그만두었다.

 

남는 시간은 2번 부분문제를 차례대로 긁다가 끝났다.

 

3:23 2번 50점

3:30 2번 70점

 

결국 200-70-250-143-0, 총 663점으로 본선을 마무리했다.

점수 컷을 따져보니 특별상은 무난하게 받을 수 있는 점수였다.

 

졸업과 입사까지 얼마 남지 않기도 해서 더 이상 대회를 나가지 않기로 했기 때문에 이번 SCPC가 학생으로서 마지막 대회 출전이 된다.

 

마지막 대회를 좋은 성적으로 끝낼 수 있어서 매우 만족스러웠다.