SCPC 2020 본선 후기

예선 후기는 쓰는 걸 까먹어서 없다. ^^;;

역대 예선 문제 풀이는 github.com/kdh9949/snups-scpc2020 여기에 다 올라와 있다. (6회 2차예선은 코드만 있다) 동아리 스터디 진행한다고 예선 문제 다 풀고 풀이 슬라이드도 만들었는데, 참여율이 저조하기도 하고 마지막에는 내가 힘들어서 그냥 자연스럽게 쫑났던 것 같다.

아무튼 1차 / 2차 예선 모두 만점으로 본선에 진출하였고, 올해는 2회 수상 제한에 걸린 채로 (3등상 2번 탔음) 나가는 첫 대회라서 별로 기대감 없이 치기로 했다.

---

대회 직전에는 뭘 공부할까 하다가 문자열 알고리즘이나 좀 공부하자 해서 Suffix Array, LCP, KMP 이런 걸 좀 외웠다.

그놈의 코로나 때문에 대회를 온라인으로 진행해야 해서 준비 과정이 좀 귀찮았다. SCPC는 무려 돈을 주는 대회다 보니 감시를 빡세게 하는 게 맞긴 하지만.. 그래도 참가자 입장에서 번거로운 건 어쩔 수 없었다. 책상 위에 간식을 뒀는데 물 빼고 다 치우라 그래서 슬펐다.

대회 시작 후 1번을 열었는데 너무 쉬웠다. 본선 진출자라면 아마 2차예선 2번을 풀었을 테니 매우 비슷하게 짜면 된다. 19년도 그렇고 올해도 그렇고 1번이 과도하게 쉬운 것 같다;;

그 다음에 2번을 열었는데.. 뭔 이상한 그래프 문제가 있었다. 처음에는 그래도 2번이니까 쉽겠지 하는 안일한 생각이었는데, 생각을 한 10분쯤 했는데 O(m^2) 풀이밖에 안 떠오르니까 슬슬 이상함을 느꼈다. 2번을 푼 사람이 좀 빨리 나왔으면 멘탈이 완전 날아갈 뻔했는데, 다행히도(?) 나한테만 어려운 건 아니었던 듯 하다. 중간에 뒤에 문제도 보고 왔는데, 3번은 구현량이 많은 문자열 문제 같았고 4번은 기하, 5번은 "5번"이었다. 2번을 거의 한 시간 가량 고민하다가 생각이 진짜 안 나서 그냥 m^2까지 긁고 (72점) 3번으로 가기로 했다.

3번은 한 5분 정도 머리를 굴리니 풀이의 대략적인 방향성을 정리할 수 있었는데, "주어진 문자열에 나타나는 모든 팰린드롬 부분문자열을 Manacher Algorithm으로 잘 뽑아서 열거한 뒤, 따로 또 주어진 문자열 3개 중 정확히 2개에 포함되는지를 Suffix Array + LCP 전처리로 빠르게 구해서, 이제 이 조건을 만족하는 사전순으로 k번째 오는 팰린드롬 부분문자열을 구하면 되는" 문제였다. 눈앞이 깜깜했지만 짤 수 있는 게 이것밖에 없었고, 1등상을 혹시라도 받고 싶으면 이거는 풀어야 할 것 같다는 생각으로, 매우 차근차근 구현해보기로 했다. 일부러 타자를 천천히 치면서 침착하게 구현했던 것 같다. 대회 직전에 LCP를 대충 공부해 놓은 덕분에 짤 수 있었다.

1시간 정도 걸려서 짜고, 30분 정도 디버깅을 한 후에 3번을 풀 수 있었고 (무려 First Solve 였다) 이제 2번을 다시 가서 풀지 4번이랑 5번으로 갈지 생각하다가, 4번 긁는 게 쉬운 줄 알고 (참고로 0점 초과를 받기 제일 힘든 문제다.) 4번으로 갔다. 2번으로 다시 갔으면 풀었을 것 같은데... 아쉬운 판단이다.

4번에서는 이상한 가정(틀렸다)을 하나 끼얹은 코드를 짜서 긁으려고 했다. 근데 이것도 제대로 못 짜서 삽질 좀 했다. 아마 내가 짠 이상한 코드는 예제 1이 안 나왔을 텐데, 대회 중에는 마음이 급해서 그것도 모르고 냈다가 0점을 2번 정도 맞고 "아닌가 보네..." 하고 5번으로 갔다.

5번은 트리에서 이상한 걸 하는 문제였는데, 이것도 잘 모르겠어서 이것저것 생각해 보다가 특수한 조건이 걸린 서브태스크가 있길래 그거라도 풀어보자 하는 생각으로 대충 뭔가를 짜서 냈는데, 점수가 긁혔다..? 지금도 왜 맞는지는 잘 모르겠는데, 아무튼 그게 O(N^2logN) 짜리 풀이였고 이제 이걸 O(NlogN)으로 최적화 할 수 있겠다 싶어서 남은 시간을 다 붓기로 했다.

그리고.. 남은 시간 동안 아무것도 못 했다. 그 풀이가 O(N) 트리DP를 각 정점마다 한 번씩 하는 거를 최적화하는 꼴이었는데, 처음 DP를 대충 짰더니 최적화를 하다가 코드가 완전 꼬여버렸다.. 아무튼 최종 점수는 100 / 72 / 300 / 0 / 77, 총 549점으로 대회를 마무리했다. 아마 수상 제한이 없었으면 또 3등상을 받았을 거 같은 점수다.

3번을 풀었다는 점에서는 잘했다 싶은데, 끝나고 나서 2번 풀이를 들으니까 2번을 못 푼게 많이 아쉽긴 하다. 1등상은 4번을 혼자 푼 gs12117님이 받으셨다. 역시gs신...

특별상으로는 "라이언 스마트빔" 이라는 무슨 빔 프로젝터를 줬는데, 아무리 봐도 악성재고라서 짬처리하는 것 같다. 집에서 쓸 일이 있을까...? 큰 모니터 대용으로 쓸 수 있다면 또 모르겠다. 근데 아직 안 꺼내봤다.

앞으로 SCPC를 아마 2번 더 나갈 수 있을 것 같은데, 1등상을 받을 확률이 높지는 않지만 없지도 않은 것 같다. 뭐 맨날 SCPC 문제 구리다고 뭐라 해도 대학생 대상으로 돈 많이 주고 혜택도 많이 주는 대회를 매년 열어준다는 점에서는 참 고마운 것 같다.