멘토교육 3주차 (IOI 2018 Day 2) 후기

7월 4일 13~18시에 IOI 2018 Day 2를 돌았다. 성적은 역시 좋지 않게 나왔고, Github에 업로드된 점수판이 없어서 등수를 정확하게 확인은 못했지만 은메달 상위인 것 같다. IMO 국대 떨어진 것이 참 다행인 것 같다. IMO 국대 됐으면 둘다 별로 좋지 않은 메달을 받고 끝났을 거 같은데, IMO가 떨어졌으니 IOI에 집중을 해서 금메달까지 실력을 올릴 가능성이 조금이라도 있는 것 같다. 내년에 IMO에 도전해야 하므로, 내년에 IOI 참가 여부는 선택사항이라 하더라도 올해 정보 실력은 어느 정도 이상 끌어올려야만 내년에 집중할 수 있을 것이다.

 

  대회 시작 후 20분 동안 문제를 모두 읽었다. doll은 조건을 만족하는 회로를 구성해야 해서 일반적이지 않고 어려울 거 같아서, highway와 meetings를 먼저 고민하기 시작했다. highway는 경로의 길이부터 구해두고 단순한 이분 탐색을 하면 18점까지는 풀 수 있었다. 18점은 너무 작은 점수여서 51점까지 올릴 수 있을지 생각해 봤고, 섭태3에서 직선 그래프의 중점을 가지고 분할 정복을 했기 때문에 자연스럽게 센트로이드가 떠올랐다. 센트로이드와 섭태2, 3 풀이를 무지성으로 결합하면 쿼리 개수가 대략 $\frac{1}{2}\log^2N$ 정도인 풀이가 나왔다. 쿼리 제한 개수 60을 만족하기에는 부족했기 때문에 highway로 넘어갔다.

  meetings는 처음에 생각을 잘못해서 sparse table을 이용하면 임의의 x와 [L, R]에 대해 해당하는 비용을 $O(\log N)$에 구할 수 있다고 생각했다. 그래서 섭태1, 2를 풀었다고 생각하고 넘어갔고, 섭태3은 그냥 금광 세그 문제였다. 문제가 2023년도 2차 선발고사 4번 팀 만들기 문제의 풀이(나는 루트 풀이밖에 모른다)를 응용하면 풀릴 것 같아서 좀더 고민했고, 실제로 L이나 R이 증가하면 x도 증가한다는 관찰을 해냈다. 하지만 [L, R]이 모두 포함관계일 수도 있어서 이 관찰은 쓸모가 없었다. 팀 만들기 문제에서는 하나씩 골라서 최대여야 하므로 버킷을 쪼개고 버킷에 속하지 않는 것들은 따로 처리하는 것이 가능했지만, 이 문제에서는 x가 변하면 수열 전체에 영향을 주므로 그 풀이가 불가능했다. 설사 가능하다 하더라도 N이 커서 루트에 로그가 하나라도 붙으면 절대 풀 수 없었고, 루트 풀이도 통과될 가능성이 희박했다. 대회 시작 후 2시간이 지났는데도 0점이자, 해결한 문제들을 구현하기 시작했다. sparse table 풀이가 잘못되었음을 깨달았지만, 고민하다가 한 생각 가운데 최대인 것 왼쪽과 오른쪽 중 하나는 다 최댓값의 비용을 지불해야 한다는 사실을 알고 구현했다. 그래서 3번 36점을 받았고, 2번 18점도 빠르게 긁었다.

  doll은 읽었을 때는 난해해 보였는데, 생각을 시작하자 각 trigger 마다 switch 를 이진트리 형태로 끼워주면 되는 것이어서 별로 어렵지 않았다. 단순히 포화이진트리로 만들어도 $S\leq2N$은 나와서 점수를 얻을 수 있었다. 좀 더 고민하자, 이진트리에서 두 리프가 모두 스위치인 경우에는 제거해도 된다는 사실을 알 수 있어서 100점 풀이가 나왔다. 대회 종료 1시간 전쯤에 doll AC를 받았다.

  highway는 섭태4부터는 진전이 없다고 생각해서 meetings 섭태4를 먼저 고민하기로 했고, 혹시라도 meetings 섭태4를 풀고 시간이 남으면 센트로이드를 시험삼아 구현해 보기로 마음먹었다. meetings 섭태4는 금광 세그를 20번 돌리면 될 거 같았다. h번째 금광 세그에서는, h 이하인 최대 접두사와 접미사 및 h 이하로 구성된 연속부분수열 중 h+1과의 차이의 합의 최댓값을 저장해 두면 될 것 같아서 구현했다. 그런데 WA가 나다가 좀 고치니까 TLE가 나서, 금광 세그 구조체 대신 포인터를 전달하는 등의 최적화를 하자 WA가 났다. 마침 이때가 대회 종료 2분 전이어서 그냥 풀이가 틀렸거나 구현이 틀린 걸 알고 대회가 끝났다.

  koosaga님의 블로그의 풀이를 보니, highway 섭태4는 센트로이드 같은 어려운 알고리즘을 쓰는 게 전혀 아니고, 그냥 경로가 지나는 간선 하나만 이분 탐색으로 구하면 끝나는 것이었다. meetings 섭태4는 내 풀이가 틀렸는지는 고민해 봐야 할 것 같지만, 점수판에서 60점이 별로 없는 걸로 보아 어려운 듯하다. highway 섭태4 같이 어렵지 않은 문제를 놓치는 일이 없도록 실력을 쌓아야겠다. highway 섭태4에서 내가 고민한 풀이를 다시 생각해 보면 정말 어리석다는 사실을 깨달을 수 있었다. 쿼리를 통해 알 수 있는 것은 비용의 변화량, 즉 칠한 간선 중 경로 위에 있는 것의 개수이다. 실제로 경로 위의 간선을 찾으면 경로의 앞부분과 뒷부분이 결정되서 풀 수 있게 된다. 그런데 나는 그 간선에 대한 정보를 정점(센트로이드)으로 바꾸려고 하느라 더 복잡했을 뿐 아니라, 경로가 정점을 기준으로 어떻게 나오는지를 관찰하는 것은 당연히도 간선을 기준으로 자르는 것보다 비효율적이다. 분할정복을 트리로 확장하려고 하다가 아무 생각 없이 센트로이드가 떠오른 것인데, 앞으로는 항상 특정 알고리즘이나 아이디어가 사용되는 근본적인 이유가 타당한지를 살펴야 할 것이다.

(7월 4일 21:21 업데이트) meetings 섭태4는 naive 하게 구현하면(h번 금광세그를 갱신하기 위해 h-1번 금광세그를 호출하면) 시간복잡도 자체가 너무 커져서 TLE가 당연히 나는게 맞았다. WA는 단순히 구현 실수인 것 같고, 디버깅 하기 전의 TLE 코드는 상수 커팅으로 되는게 아니었던 것이다. 공식 에디토리얼을 보니, naive 하게 하지 말고 반복되서 계산되어야 하는 구간들을 전처리해 두면 시간 내에 풀 수 있다고 한다.