SCPC 2020 2차예선 + 본선 후기

2차예선 후기

1,2번은 쉬운 문제라 빨리 풀고 3번을 잡았는데, \(O(N \lg N)\) 풀이를 구현해도 계속 시간초과가 났다. 스플레이 트리, 평방 분할, multiset 등 다양한 구현체를 계속 시도해보다가, 계속 TLE가 발생하길래 로컬에서 벤치마크를 시도했더니 100개 테스트 케이스를 돌리면 6초를 넘어서 한 15초 내외가 나왔다. 상수커팅이란 느낌이 들어서 좌표압축을 하고 압축된 좌표로 세그먼트 트리를 돌렸더니 7-8초 내외가 나왔다. 여기서 다시 좌표압축을 할 때 정렬하는 과정을 counting sort로 바꿨더니 3-4초로 줄었다. 이걸 제출해서 AC를 받았다. 문제는 삽질을 너무 많이 해서 3번을 AC 받은 시간이 오후 7시가 넘었다는 점.

 

그래서 일단 5번 부분점수 37점을 확보해서 본선 진출부터 확정지었다. 남은 시간 즉 두 시간이 안 되는 짧은 시간동안 5번 만점을 받으려고 무언가 DP를 구현해봤는데 볼록9각형에서 반례가 나와서 더 이상 진행이 불가능했다. 끝나고 다른 풀이를 읽어보니 그냥 DP를 하면 안 되고 이분탐색으로 특정 값 이하가 되도록 해야 한다고 하더라. 역시 DP는 연습이 정말 많이 필요한 분야다.

 

본선 후기

이번 SCPC는 코로나 때문에 온라인으로 했는데, 온라인으로 할 거였으면 그냥 원래 일정대로 방학 때 했으면 좋았을 것 같다.. 학사일정이 밀리는 바람에 본선이랑 시험기간이랑 겹쳐서 너무 힘들었다.

 

1번은 그냥 주는 문제라 10분만에 AC.

2번은 N=1,000 이하에 M=10,000 이하인 유향그래프가 주어지는데 나이브한 풀이는 O(M^2)으로 72점이고, Tarjan을 써서 SCC DAG를 구성하고 그 위에서 위상 순서대로 DP를 해주면 O(NM)으로 AC를 받을 수 있다. 핵심은 굉장히 빠르게 알아냈는데 경우의 수가 int 범위를 넘어갈 수 있다는 걸 생각하지 못했다.. 특정 SCC에 올 수 있는 방법 수가 2 이상이면 모두 동일하게 취급해서 2로 ceiling을 해 주면 AC가 나올 것을 2시간이나 헤멨다. 이 과정에서 제출횟수도 10번 가까이 날려먹었다. 쉬운 버그인데 계속 못 잡고 헤멘 건 아마도 바쁜 일정 때문에 연습부족이 원인이겠지ㅜ.

 

어쨌든 2번을 AC받고 나니 4시 반이 넘어서, 5시 20분에 대회가 종료될 때까지 4번 부분점수를 긁으려고 했지만 문제를 잘못 읽었고 실패했다. 문자열은 연습이 부족해서 3번은 터치하기 어려웠다. 이번에도 5등상을 받았고, 2번의 횟수를 채웠으니, 이제 1등을 하지 않으면 참가해도 상은 못 받는다... >^< 그래도 대회 시작할 때 2번을 처음 딱 봤을 때 이번에는 상을 못 받을지도 모르겠다는 생각을 했던 걸 돌이켜보면, 컨디션에 비해 잘 나온 성적이라고 생각한다. SCC는 SCPC 2017년 1차예선에 2-SAT이 나온 걸 보고 그때부터 꾸준히 오래 대비한 알고리즘인데, 내가 잘 아는 게 나와서 그나마 선방한 것 같다^^

 

커트라인은 5등상은 17x점 즉 1번 만점 + 나머지 부분점수 1문제 정도인 것 같고, 4등상은 나랑 같은 300점인 것 같다(아닌가?). 이것도 작년이랑 똑같다.

 

에필로그

사실 지금까지 알고리즘을 공부한다고는 했지만 학기중에는 바빠서 한 번도 한 적이 없고, 지난 겨울방학이나 여름방학 때도 다른 거 하느라고 사실 제대로 공부한 시간은 지금까지 누적 10개월이 안 될 것 같다(하루 6시간 이상 집중한 것 기준).. 하지만 가상화 커널개발, 창업대회, 딥러닝 대회 같은 다른 이상한 삽질을 많이 해 봤으니까 후회하진 않는다.

 

이제 남은 대회는 ICPC, 구글 코드잼 같은 팀 대회 내지는 글로벌 대회뿐이다. 아니면 가끔 산발적으로 열리는 국내 대회들을 참가하는 정도인데, 어느 쪽이든 일단 숨 좀 고르면서 쉬어야지...