IOI 멘토교육 20190608

돈 셋 : IOI 2018 Day 2

 

~10분

일단 모든 문제를 읽고, doll을 잡기로 결정했다.

 

84분 : doll 0점

doll을 계속 고민해봐도, 서브태스크 1, 2를 제외하고는 아무런 생각이 나지 않았다. 서브태스크 2의 구현마저도 엄청 복잡할 것 같았다. 그러다가 M=1인 서브태스크를 풀면 전체적인 감이 오지 않을까 하는 생각에 그걸 계속 고민했다. 스위치를 일렬로 늘어서게 하고 Y 방향을 트리거 쪽으로 오게 하는지 여부로 이진법 표현이 가능할 것 같았다. 그와 비슷한 형태를 계속 고민하다 예제가 나와서 제출했는데 0점을 받았다.

 

91분 : doll 2점

1시간 이상 고민했는데 소득이 없어서 일단 뭐라도 짜기로 했다. 서브태스크 1을 해결하고 2점을 받았다.

 

138분 : doll 20점

다시 M=1인 서브태스크를 고민하다가 이진법 표현이 가능한 형태가 나왔고, 그걸 짜서 18점을 추가로 받았다.

 

~150분

M=1인 서브태스크를 풀었는데도 전체적인 문제에 대한 감이 전혀 오지 않았고, 이진법 풀이는 이 서브태스크에만 적용할 수 있을 것 같았다. doll에서만 2시간 반 정도나 썼는데도 20점밖에 받지 못해서 이때 멘탈이 나갔다. 일단 다른 문제로 넘어갔다 와야겠다는 생각을 했고, highway를 잡기로 했다.

 

180분 : highway 11점

트리인 경우에, 일반성을 잃지 않고 S와 T 중 깊이가 깊은 걸 T, 아닌 걸 S라고 하자.

S를 알 때:

S를 루트로 하는 트리로 만든다.

T의 깊이를 쿼리 한 번으로 알아낸 후,

T의 깊이와 같은 깊이를 가지고 있는 정점들과 그 부모를 잇는 간선들에 대해서, 반은 A로, 반은 B로 설정해서 원래 최단경로 길이와 같은지 비교하며 이분탐색해서 T를 알아낸다.

S가 뭔지 모를 때:

S가 뭔지 모를 때에는 깊이가 k 이상인 간선의 가중치를 B로 설정하고, 원래 최단경로 길이와 같은지를 비교하면서 최소 k를 이분탐색한다. 이렇게 하면 T의 깊이를 알 수 있고, 아까처럼 이분탐색을 써서 T를 알아낸다. 이제 T를 알아냈으므로 T를 루트로 만든 다음 방금 케이스와 똑같이 풀면 총 세 번의 이분탐색으로 해결할 수 있다.

일단 S를 알 때의 경우를 짜서 11점을 받았다. 

 

195분 : highway 51점

S가 뭔지 모를 때의 경우도 짰고, 51점을 받았다. 그리고 meetings를 잡았다.

 

208분 : meetings 19점

어떤 마을에서 모임을 할 때 다른 마을에 사는 사람들의 비용과 부분합을 $O(N^2)$에 전처리하고 쿼리당 $O(N)$에 풀면 19점을 받을 수 있다.

 

234분 : meetings 36점

$H_i$가 1 혹은 2일 때는 모임을 1이 가장 많이 연속되어 있는 곳에서 하는 게 이득이다. 이를 적절한 전처리와 최댓값 세그먼트 트리를 사용하면 이를 쿼리당 $O(log N)$에 찾을 수 있다. 이걸 짜서 17점을 추가로 받았다.

 

273분 : doll 48점

doll로 다시 돌아와서 스위치를 아무렇게나 그려보다가, 스위치로 완전 이진 트리를 만드니 그냥 순서대로 트리거를 놓기만 하면 되는 것이었다! 스위치를 2N개보다는 적게 쓰겠지라는 생각에 점수 계산을 하지 않고 짰고, 서브태스크 6에서만 28점을 추가로 받았다.

 

~300분

100점을 받으려면 완전 이진 트리 말고 필요 없는 노드를 적절히 지워야 할 것 같았는데, 필요 없는 노드를 지우니 다시 시작 정점으로 돌아왔을 때 상태가 Y인 스위치가 생겼다. 이걸 해결하려다가 대회가 끝났다.

 

 

점수를 합산해보니 48 + 51 + 36 = 135점을 받았다. 아마 은메달 정도의 성적인 것 같다. doll에서 말린 것 치고는 괜찮은 점수지만, 아쉬움이 남는다. 처음에 doll에서만 대회 시간 반을 썼는데, 이 시간이 너무 길어진 것 같다. 1시간 정도 잡다가 안 되면 다른 걸 긁고 왔어야 했는데 말이다. 만약에 그랬다면 highway 51점과 meetings 36점을 더 일찍 받고 이진 트리 생각도 조금 더 일찍 나지 않았을까... 또 그랬다면 doll에서 더 많은 점수도 받을 수 있지 않았을까 하는 아쉬움이 남는다.