Dispatching (APIO 2012)

http://koistudy.net/?mid=prob_page&NO=593

1. Naive ( O(N^2lgN) )

트리에 대한 기본적인 지식이 있으면 풀 수 있다.

서브트리의 경우의 수가 N개이니, N개의 각 경우에 대해서 내부에 있는 노드를 Greedy하게 더해서 경비병을 최대화 하면 된다.

내부 노드에 있는 cost들을 그때 그때 sort해주면 N^2lgN이다.

2. Naive (...) ( O(Nlg^2N) )

일단 그때 그때 sort해주기 보다는 priority_queue 등의 자료구조를 사용해서 서브트리에 있는 원소들을 재귀적으로 합쳐주자.

이 역시 O(N^2lgN)이 걸린다.

이 때 합치는 대상이 되는 힙을 "가장 원소 개수가 많은 힙" 으로 설정해주자.

약간의 커팅.... 은 무슨, 이걸로 시간 복잡도 O(Nlg^2N)이 완성된다.

https://translate.google.co.kr/translate?sl=auto&tl=ko&js=y&prev=_t&hl=ko&ie=UTF-8&u=http%3A%2F%2Fkagamiz.hatenablog.com%2Fentry%2F2013%2F02%2F08%2F232228&edit-text=&act=url

Heavy-Light Decomposition이라는 테크닉에서 아이디어를 따온 것이다. (이하 HLD라 칭한다.)

HLD를 간단히 설명하겠다.

트리의 루트에서 선을 리프 쪽으로 쭈우욱 긋자. 이 때 선을 긋는 기준은 서브트리 중 사이즈가 큰 놈만 선택한다.

줄이 그어져 있을 거고 선택받지 못한 서브트리들이 서서히 생겨날 것이다. 얘내들도 마찬가지로 선을 같은 기준으로 쭈우욱 긋자.

이렇게 트리 내부에는 여러 개의 선이 생겨 있을 것이다. 아래 사진은 각각의 선에 이쁘게 색칠을 해놓은 사진이다.

(불펌인데 이미지가 너무 좋아서 안 퍼올 수가 없었다. 원본은 http://blog.anudeep2011.com/heavy-light-decomposition/)

이제 임의의 두 정점을 잡고 둘 간의 경로를 생각해 보자.

둘 간의 경로에서 색깔이 바뀌는 횟수는 몇번일까? O(lgN) 번이다. 임의의 모든 경로에서.

못 믿겠으면 위 사진에서 세봐도 된다. 23개밖에 없어서 신빙성은 떨어지지만 (...) 진짜 O(lgN) 번이다.

증명은 무지 심플하다. 편의상 리프로 가는 경로만 소개하겠다.

루트에서 리프로 내려갈때 색깔이 바뀌었다는 건 서브트리의 사이즈가 기존의 반 이하로 줄었다는 것과 동치이다.

만약에 서브트리의 사이즈가 기존의 반 이상이라면, 애초에 선을 그었을 때 그 쪽으로 선을 그었을 것이기 때문에, 모순이다.

때문에 루트에서 리프로 내려가는 경로에서 색깔이 바뀌는 횟수는 많아야 O(lgN) 번이고, 다른 모든 경로들도 이보다 많아야 2배 정도 많기 때문에, 바뀌는 횟수는 O(lgN) 번이다.

이제 이 문제의 O(Nlg^2N) 솔루션을 증명하는 건 간단하다.

N개의 모든 원소들은 일단 해집합에 한번 들어가고 한번 나간다. 이 부분은 O(1) 번 진행된다.

그리고 이들은 합집합 연산 (즉, Heap에서 빠져 나왔다 다른 Heap에 들어가는 것)을 많아야 O(lgN) 번 한다.

때문에 N개의 원소들이 lgN 번 Heap에 접근하기 때문에 O(NlgN * lgN) = O(Nlg^2N)이다.

대부분 HLD 문제들은 저 chain을 직접 따로 구현하게 시킨 후 chain 안에 자료 구조를 넣는 등의 작업을 하지만, 재밌게도 이 문제는 암시적으로 chain을 만들기만 해도 쉽게 풀린다.

처음에 HLD로 풀릴라나 싶었었는데 당연히 아니겠지라는 생각에 깊은 생각을 안했던 것으로 기억이 난다. 앞으로는 문제를 조금더 생각하고 풀어야 할듯...

HLD에 대한 제대로 된 설명은 http://blog.anudeep2011.com/heavy-light-decomposition/ 에 굉장히 잘 나와있으니 참고하길!

3. RMQ ( O(NlgN) )

https://algospot.com/wiki/old/232/APIO2012

역시 깔끔하고 좋은 풀이이다.

일단 dfs를 돌릴때 리프부터 돌아가도록 하자.

먼저 리프에서 M 이하의 원소를 어찌어찌 고르고...

이걸 현재 노드에서 합쳐줘야 할 것이다.

일단, 리프에서 얘내들이 골라놓은 원소들의 합을 계산해 놓은 후,

이것이 M을 초과한다면 RMQ에서 지속적으로 가장 큰 놈을 해고시킨다. (-1로 set 해주고 원소 수 --해주면 된다)

재귀적으로 반복하게 하면 된다.

이 문제는 풀이들이 한결같이 아름다운 듯.