BOJ 1209 단조수열 만들기 : O(NlgN)

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

최근 CF에 똑같은 문제가 출제되었는데, 짱짱맨 분들이 O(nlgn)에 풀어주신 덕분에 오랜 난제(http://koosaga.myungwoo.kr/110) 가 해결됐다.

http://codeforces.com/blog/entry/47094?#comment-315161

단조감소는 생략한다. fi(X) = A[1..i]를 단조증가로 만들면서 Ai <= X 이하로 만드는 최소 횟수의 연산이라고 정의하자. (여담으로. 여기서 X의 가능한 경우가 O(N) 밖에 안된다는 관찰을 하면 바로 O(N^2)에 풀 수 있다.)

점화식은 :

• Min(Y <= X) |Ai — Y| if i == 1
• Min(Y <= X) (f(i-1) (Y) + |Ai — Y|) otherwise.

nlgn 풀이는 APIO2016 fireworks랑 굉장히 유사한데, 먼저 fi가 모든 기울기가 0 이하의 정수인 unimodal function이라는 것을 관찰하자. fi(X) 를 최소로 만든 X를 Opt(i) 로 정의한다. 이제 fi 를 관리하면서 최솟값을 계산할 것이다.

Case 1 : Opt(i-1) <= A[i]. 이 때 Opt(i) = A[i]고, A[i] 이하의 모든 x에서 기울기가 1 증가한다.

Case 2 : Opt(i-1) > A[i]. 약간 복잡한데, 일단 A[i] 이하의 모든 x에서 기울기가 1 감소, A[i] 이상의 모든 x에서 기울기가 1 증가한다. 이 함수에서 -1 -> 0으로 기울기가 변하는 지점이 Opt(i) 일 것이다. Fi(Opt(i)) = F(i-1)(Opt(i-1)) + Opt(i-1) - A[i] 라는 식이 나옴을 알 수 있는데 (아래 사진 참고), 그냥 Fx(Opt(x)) = 0으로 생각하고 이걸 연산 횟수에 더해주자.

점화식이 자명하므로 연산들은 모두 자명하다. 기울기가 0 이하의 정수인 unimodal function이라는 점이 석연치 않을 수 있는데, f1 이 그 성질을 만족하고, 위 연산을 적용하면서 그러한 성질이 변하지 않으므로, 수학적 귀납법으로 쉽게 증명할 수 있다.

APIO2016 fireworks처럼 pq로 기울기가 변하는 점들을 관리하면 문제를 풀 수 있다. 시간 복잡도는 O(nlgn)이고, 구현은 "극단적으로" 쉽다. 

https://github.com/koosaga/olympiad/blob/master/USACO/feb08_grade_fast.cpp