멘토교육 4주차 (IOI 2016 Day 1) 후기

7월 6일 13시 1분부터 18시 1분까지 IOI 2016 Day 1을 돌았다. IOI 2016은 koosaga 님이 학생으로 출전하여 금메달을 따셨던 셋인데, koosaga 님의 Day 1 성적과 정확하게 똑같은 성적이 나왔다. koosaga 님의 후기와 점수판을 보니, Day 1은 변별이 별로 없어서, 금메달 상위권은 202점이나 205점도 있지만, 168점을 받아도 Day 2 결과에 따라 상이 결정되는 셋이었던 것 같다. 물론 이게 8년 전의 사람들의 실력이므로, 지금 같았으면 은메달 하위권 정도일지도 모른다. 멘토교육 4회 모두에서 금메달에 준하는 성적이 한 번도 나오지 않았고, 계속해서 은메달이 나왔지만, 앞으로의 집중 교육 기간 동안 노력하면 금메달 가능성도 있을 것이라고 생각한다.

세 문제를 모두 읽었다. 최근의 길고 복잡한 IOI 문제에 비해, 문제 지문이 매우 짧고 간단했다.

molecules: 주어진 집합에서 합이 $l$ 이상 $u$ 이하인 부분집합을 고르시오.

railroad: n개의 수 $(s_1, t_1), (s_2, t_2), ..., (s_n, t_n)$의 재배열 $(S_1, T_1), (S_2, T_2), ..., (S_n, T_n)$에 대해, $\sum_{i=1}^{n-1}\max(S_{i+1}-T_i, 0)$의 최솟값을 구하시오.

shortcut: 선형 그래프의 각 점에 길이 $d_i$인 간선으로 추가적인 정점이 연결되어 있을 때, 두 정점을 골라 길이 $c$인 간선을 추가한 경우 중 그래프의 지름이 최솟값을 구하시오.

문제를 읽자마자 보이는 섭태들이 상당히 있었다. molecules는 48점까지는 그냥 냅색 dp였고, 이를 bitset으로 64개씩 묶어 처리하면 71점이었다. railroad는 전형적인 비트 dp만 하면 34점이었다. shortcut은 모든 경우를 따져서 지름을 계산하면 23점이었다. railroad가 섭태 수가 적어서 쉽지 않을까 하고 생각을 해봤는데, 섭태3부터 잘 풀리지 않았다. 그래서 71점을 거저 주는 molecules가 쉬울 것이라 생각했다. 문제를 다시 꼼꼼히 읽으니, 71점까지의 풀이에서 사용하지 않은 조건 $u-l\geq w_{max}-w_{min}$을 볼 수 있었다. 이 조건이 의미하는 바를 생각해 보자, 임의의 배열에서 한 원소를 골라 최댓값 또는 최솟값으로 바꾸어도 무방함을 알 수 있었다. 이를 귀납적으로 확장하면, w를 오름차순 정렬한 배열에서 prefix와 suffix의 합집합만 조사하면 된다는 결론을 얻을 수 있었고, 투 포인터로 구현해서 대회 시작 1시간도 되기 전에 100점을 받았다.

이후 railroad와 shortcut을 조금씩 고민해 보았지만 진전이 없어서, 일단 railroad 34점과 shortcut 23점을 얻었다. railroad 섭태3에 대해 그럴듯한 풀이를 엄밀하지 않게 내서 구현해 봤지만 틀렸고, 실제로 반례가 금방 나왔다. 그리고 나서 shortcut의 선형 그래프에서 경우를 잘 따져서 $O(N^2)$개의 경우의 수를 각각 $O(N)$에 계산하는 풀이를 떠올려서 15점을 올리고자 코딩을 했다. 하지만 WA가 났고, 디버깅을 하다보니 대회가 2시간 정도밖에 남지 않아 있어서 railroad로 돌아왔다. railroad로 돌아와서 섭태3을 풀기 위해 다양한 노력을 했지만 풀리지 않았다. 따라서 점수는 높지만 풀 가능성이 적은 railroad 30점보다는, 디버깅만 하면 풀 수 있는 shortcut 15점에 시간을 투자하기로 결심했다. 랜덤 데이터를 만들어서 돌려보는 등의 시도로 디버깅을 하다보니, 코드에 많은 오류가 있음을 알 수 있었다. 제출할 때마다 '채점 중단'까지 나오는 테스트 케이스의 수가 4 -> 19 -> 24 이런 식으로 늘어나서 디버깅 방향이 올바름을 알 수 있었다. 마지막으로 잡아낸 오류를 naive하게 수정하자 시간복잡도가 $O(N^4)$가 되었지만, 나머지 풀이가 모두 맞는지를 확인하기 위해 그냥 제출했는데 놀랍게도 31점이 나왔다. 그래서 이 풀이에서 적절한 자료구조로 $O(N^3)$이나 $O(N^3\log N)$으로 만들면 38점이 나올 것이라고 확신했으나, 혹시나 해서 불필요한 문장을 지우고 제출해봤다. 놀랍게도 섭태4가 1.95초 정도에 돌아서 38점이 되었다.

(시간복잡도로는 틀렸지만 간신히 뚫은) 38점을 얻는 데도 이렇게 힘들었으니, 남은 1시간 이내의 시간은 shortcut 33점에 투자하면 풀이가 생각나더라도 조건분기와 구현이 힘들 것이라고 판단했다. 그래서 railroad 섭태3을 고민했고, 증명을 하지 않은 그리디 풀이를 냈다. 코딩과 디버깅을 반복하면서 풀이의 반례를 찾아냈고, 반례가 나올 때마다 이를 덮을 수 있는 근거없는 휴리스틱을 생각해 냈다. 대회 시간이 30분 정도밖에 남지 않아서 뚫는 것 외에는 방법이 없었기 때문이었다. 결국 대회 종료 직전에는 처음 19개의 테스트케이스에서 맞았습니다가 나왔지만, 20번째의 틀렸습니다는 어떻게 해도 고쳐지지 않았고 그대로 대회가 끝났다.

점수판을 확인해본 결과, molecules는 너무 쉬워서 동메달까지도 거의 다 100점을 받은 문제였고, railroad 34점 초과와 shortcut 38점 초과는 각각 20명 안팎이었다. 현재를 기준으로는, 두 문제 중 하나는 점수를 더 받아야지 금메달 가능성이 있는 축에 속할 것이다. 둘 다 비슷한 난이도였던 것 같긴 하지만, shortcut과 같은 문제의 경로 안/밖 따지는 등의 조건분기에 자신이 없어서 shortcut 71점을 아예 버린 것은 좋지 않았던 것 같다. 하지만 shortcut 38점을 따는데 사용한 디버깅 시간을 통해, 내가 얼마나 이런 조건분기에 약한지를 알게 된 후의 선택으로는 나쁘지 않았던 것 같다. 지금은 교육기간이니, 이런 조건분기와 구현도 빠르게 할 수 있는 능력을 기르는 것이 필요하겠다.