SCPC 2019 본선 후기

오늘은 대망의(!) SCPC 본선이 있던 날. 지난 두 번의 대회에서 상을 못 받았고 지쳐가고 있었지만, 솔직히 방학 때만 벼락치기로 하면서 상 받기를 기대하는 나란 참...! 어쨌든 이번 예선 결과가 좋아서 나름 기대를 하고 대회장에 갔다. 가서 과자부터 집어다 쌓아놓으려고 했는데, 어쩐 일인지 올해는 초콜릿 바가 없어서 아쉬웠다. 아쉬운대로 일단 쿠키랑 음료를 가져다 놓았다.

 

늘 그렇듯이 1시 반에 대회가 시작되었다. 당연히 1번 문제부터 잡았다.

 

1번 문제는 이분 탐색으로 \(O(N \lg{N})\)으로 해결되는 게 당연한 문제인데 std::vector에다가 std::find를 쓰는 바람에 \(O(N^2)\)가 되어 계속 시간초과가 났었다. 90명이나 풀었는데 왜 난 안 되지...? 하다가 일단 28점에서 만족하고 2번으로 넘어갔다.

 

2번 문제를 봤는데 순간 당황했다. 예선에 나왔던 휴리스틱 유형들이랑 다르게 Local Search로 될 것 같지가 않았다. 심각하게 고민하다가, 그냥 Convex Hull 구할 때처럼 왼쪽 아래 끝점을 잡아서 각도로 스위핑하면서 전부 다 이어줘 봤더니 186점이 나왔다. 방향이 맞은 것 같아서 세 점이 한 직선 위에 있지 않다는 조건을 이용해서 Convex Hull의 모든 점에 대해 반복하도록 고쳐봤는데, 177점?! 이 되었다. 뭔가 이상하긴 한데, 쉽게 고칠 수 있을 것 같아 일단 다른 문제를 봐야겠다고 생각했고, 3번으로 넘어갔다.

 

3번 문제는 어려운 수학 문제인줄 알았는데 조금 생각해보니까 답이 무조건 \(2^k\) 꼴임을 알 수 있었다. 특정한 제한조건을 \(u \rightarrow v\)라고 하면, 이 조건은 트리에서 \(u\)와 \(v\)의 최소공통조상(LCA)을 루트로 하는 서브트리에만 영향을 끼친다는 걸 알 수 있다. 트리에 대한 LCA는 Sparse Table로 \(O(N \lg{N})\)에 전처리하면 하나의 쿼리를 \(O(\lg{N})\)에 구할 수 있다. LCA를 구한 다음, LCA를 루트로 하는 서브트리에서 왼쪽 서브트리, 오른쪽 서브트리(만약 있다면), 그리고 \(\text{LCA}(u, v)\) 이 3가지 중 어디서 어디로 가는 화살표인지를 잘 따져서, 경우의 수를 깎아내리면 된다. 모순이 발생하는 경우가 있는데 이때는 그냥 그 이후가 전부 불가능하므로 루프를 멈추면 된다. 모순을 제대로 처리하지 못해서 WA를 여러 번 받았다.

 

3번 AC를 받고 2번을 돌아와서 보니 새로운 솔루션이 더 좋을 때 갱신을 하긴 하는데 실제 배치만 갱신하고 얼마나 좋은지는 갱신을 안 해줘서 점수가 되려 떨어지는 버그가 발생한 거였다. 점수를 갱신하는 한 줄짜리 코드 넣고 바로 AC.

 

다시 1번을 잡았는데, 로컬에서 N = 100,000인 데이터를 넣어보니까 22초가 걸렸다. QueryPerformanceCounter API를 써서 루틴별로 시간을 재 봤더니 std::find가 포함된 루프가 21초 이상 잡아먹고 있었다. 설마 std::find가 문제인가? 하고 std::lower_bound로 고쳐서 냈더니 바로 AC. 확실히 C++ STL 사용법을 더 익혀야 겠다는 생각이 들었다.

 

여기까지 하니까 대회시간 4시간 중에 2시간 44분이 지나 있었다. 일단 4번, 5번 설명을 대충 읽어봤는데, 어느 하나도 남은 시간동안 만점을 받기는 어려워 보였다. 그래서 그냥 4번과 5번의 가장 낮은 부분점수를 긁었다. 4번은 바로 긁었는데, 5번은 뭔가 수학적으로 생각을 잘못했는지 계속 TLE에 0점이 뜨다가 9번째 제출만에 가까스로 30점을 받았다. 본선은 제출제한이 100회라 그냥 막 제출하다 보니 더 그랬던 것 같기도..

대회가 끝나고

대회가 끝나고 출제위원장이신 김성렬 교수님께서 풀이를 개략적으로 설명해 주셨다. 4번은 무려 \(O(N)\) 그리디라고 한다. (찔러볼걸...) 원래 그리디 문제에 약하다는 느낌은 갖고 있었지만, 이번에 구멍이라는 걸 확실히 깨닫게 되어 다행이다. CLRS 그리디 연습문제나 파야겠다. 5번은 3D 문제지만 잘 생각해보면 2D 문제로 바꿀 수 있다고 한다. 2D 문제면 아마 세그먼트 트리를 붙이고 개고생을 하면 어찌어찌 풀릴 것이다. 제한시간도 10초나 됐기 때문에... 다만 대회 시간 내에 발상과 구현과 디버깅까지 하는 건 정말 힘들 것 같다. (1시간 50분인가 지났는데 스코어보드에 만점이 등장하는 걸 보고 정말 으...)

 

대회가 끝나고 뭔가 상을 받을 것 같기는 했는데 솔직히 불안했다. 시상식이 시작될 때까지 가슴이 벌렁벌렁 하다가, 스크린에 이름이 딱 뜨는데, 와! 기분이 좋았다. 총점은 100+200+300+23+30 = 653점으로, 5등상을 수상했다. 5등상 커트라인이 616점이라고 하는데, 어쨌든. 사실 그보단 4등상 커트라인이 궁금하다. UPDATE(19/07/31): 4등상 커트라인이 653점이라고 한다...(ㅜ.ㅜ) 실수 안 하고 빨리 풀었으면 4등상을 받았을지도...? 어쨌든 실력이 그 정도는 된다는 거니까 뭐. 나쁘지 않다^^ (상 받은 게 어디야...)

 

아! 아무튼 대회 끝나고 치킨 맛있게 먹었다. 내년에도 화이팅.