Harbingers (CEOI 2009)

https://www.acmicpc.net/problem/3319

한동안 글을 한꺼번에 썼었는데 나눠 쓰는 게 여러모로 나을 듯 하다. 앞으로 그런 방향으로 바꿔나가려고 함.

언제봐도 신기한 harbingers 문제를 다시 리뷰하려고 한다.

O(N^2)

dp[i] = Min(dp[j] + (depth(i) - depth(j)) * V[i]) + S[i] for all j = (ancestor of i) 이다.

Special Cases : Line O(NlgN)

일직선에서 이 문제는 아주 유명한 컨벡스 헐 트릭이다. (depth(j), func(j)) 라는 형태의 일차함수가 순서대로 들어오고, V[i] 쿼리를 이진 탐색으로 처리해 주면 된다. 이해가 안가면 여기서 멈추고, http://dyngina.tistory.com/28 글을 참고하기를 권한다. O(NlgN).

O(NlgN)

일직선이 아니면 data structure가 여기저기서 널뛰기하는 바람에 관리하기가 쉽지 않은 것이 단점이다. 단순히 dfs하면서 문제를 해결한다고 하면, 각 노드를 돌 때마다

* 1. 자료구조 query

* 2. 자료구조 삽입 (= 스택의 뒤를 뺀 후, 현재 직선 삽입)

* 3. 재귀적으로 dfs

* 4. 자료구조 원상복귀

를 해주면 된다.

일단 먼저 저걸 해도 O(N^2) 라는 점을 상기하기 바란다. 자료구조 삽입 과정에서 스택의 뒤를 빼는 게 amortization이 되지 않는다. 고로 스택의 뒤를 뺄 때도, 이진 탐색으로 위치를 잡은 후 한꺼번에 스택의 사이즈를 조정해서 날려야 한다. 자료구조 원상 복귀를 어떻게 잘 했다면 이제 여기까지는 괜찮다.

이제 자료구조 원상 복귀가 멘붕이라고 생각할수 있지만, 실제 그렇게 어렵지 않다. 삽입 과정에서 바뀐 것은 1. 스택의 사이즈 2. 스택 맨 뒤 1개의 원소이다. 스택의 사이즈를 원상태로 복귀하고, 스택 맨 뒤 1개의 원소를 다시 복구하면 된다. 물론 뒤에 있는 노드들도 자기 마음대로 data structure를 갖고 놀았겠지만, 재귀 호출을 빠져나오면서 원상태로 돌려놓는다는 걸 보장해준다는 것을 알 수 있다. 이렇게 call stack과 convex hull stack을 갖고 잘 놀면 (...) O(NlgN)이 나온다.