케이크 (JOI Spring Camp 2013)

http://oj.uz/problems/view/JOI13_cake

이런 문제를 내는 사람이나 푸는 사람이나 신기하다.

Preliminaries

1. 저 그대로의 폼으로는 딱 봐도 답이 안 나오는 구조다.. 거꾸로 들어가야 한다. 어떤 원소 T를 먼저 고르고 들어갔을 때, 마지막으로 먹는 원소는 무엇인가?

답은 T가 아닌 가장 작은 수임을 쉽게 알 수 있다.

최솟값을 고르고 들어갔을 때는 O(N)에 계산하는 예외처리를 해주자. 나머지 경우에는 항상 최솟값이 마지막으로 남을 것이다. 최솟값이 a[0]에 저장되어 있다면 선형에 대해서 문제를 풀어주면 된다. 이건 std::rotate를 쓰면 되니까 O(N)에 원이 선형으로 풀렸다.

2. 그래서 마지막에 먹는 걸 누가 먹는지 알았는데, 나머지는 어떻게 알까? 나머지는 또 그걸 제외한 최솟값에 영향을 받는다. [1, N-1] 구간에서 a[T]가 최소라면, i < T에서는 [T, N-1]이 누구 껀지 정해지고 i >= T에서는 [i, T]이 누구 껀지 정해진다. T는 브루트포싱으로 O(N)에 구한다. 이렇게 재귀적으로 내려가 주기만 해도 random data에서는 O(NlgN)이 되지만 그렇지 않기 때문에 아직 O(N^2)이다. (quicksort를 생각하셈)

두가지 사실만 가지고 naive하게 짜면 : http://oj.uz/submission/17539

3. 그냥 잡다한 최적화를 해주자. 먼저 최솟값 구하는 건 RMQ로 구할 수 있고, 또한 짝수 항 홀수 항만 골라 주는 것 역시 부분합으로 가능하다. 잡다한 최적화를 더해주면 : http://oj.uz/submission/17544

핵심은 T의 값을 구하는 함수인 expand()를 어떻게 줄이느냐이다.

O(Nlg^2N)

expand() 함수를 짤 때, 왼쪽 interval과 오른쪽 interval이 있고 두개를 비교해가면서 조각을 잘라먹는다. 이때 http://amugelab.tistory.com/entry/Dispatching-APIO-2012 에서 언급한 트릭을 써먹을 수가 있다.

크기가 작은 interval의 크기에 비례하는 expand() 함수를 생각해 보자. 편의상 왼쪽 interval이 작다고 생각하겠다. T에서 왼쪽으로 서서히 이동해 나가는데, T-1번째 원소를 먹기 위해서는 오른쪽에서 얼마나 가져가야 하는지, T-2번째 원소를 먹기 위해서는 얼마나.. 이걸 세 줄수가 있다. 이진 탐색을 통해서 오른쪽 구간에서 O(lgN)번 RMQ 쿼리를 날린다. sparse table 형태로 O(NlgN) / O(1) rmq가 구성되어 있다면 왼쪽 interval의 크기를 S라 했을때 SlgN에 문제가 해결된다. 위 글에서 언급했듯이 이는 O(Nlg^2N)이다.

N이 커서 시간 안에 뜰지는 모르겠다. 확실한건 코딩이 썩 쉽지 않아 보이니 실전에서 이걸로 TL뜨면 개손해.

O(NlgN)

여기서 조금 웃기는 짓을 하는데, expand() 함수에서 이러한 최적화를 해보자.

* [L, R] 구간이 있을 때, 마지막으로 고르게 될 연속된 구간을 빼고, 연속된 구간을 빼고, 연속된 구간을 빼면서 계산을 한다.

무슨 말인지 감이 안 와닿을거 같다... [L, T-1] / a[T] / [T+1, R] 이라고 하자. 편의상 [L, T-1] 구간의 최솟값 < [T+1, R] 구간의 최솟값이라 하자. a[U] = [L, T-1]의 최솟값이라 하면 [L, U] 구간은 O(1)에 얼마나 먹는지 알아맞출 수 있다. 이걸 구간을 점차 줄여가면서 계속.. 하면 된다. http://oj.uz/submission/17549

이 아이디어를 구현하면 놀랍게도 100점이 나오는데, 다음과 같이 증명할 수 있다.

* T를 루트로 하고, [L, T-1]의 maximum / [T+1, R]의 maximum을 자손으로 하는 트리를 생각해 보자. 저 알고리즘은 트리의 T번 노드에서 한번 왼쪽 -> 쭉 오른쪽, 한번 오른쪽 -> 쭉 왼쪽으로 가는 경로를 쭉 내려가면서 계산을 한다. 이를 모든 노드에 대해서 진행했다면 이것의 합은 트리의 euler tour이니까 O(N)번 이러한 프로세스가 진행되었다. 에지 하나 타고 내려가는데 드는 시간은 O(lgN)이니까 곱하면 O(NlgN).

여담으로 이러한 식으로 구성된 트리를 Cartesian Tree라고 한다. https://en.wikipedia.org/wiki/Cartesian_tree