Toys (USACO Nov 08 Gold)

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

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

이 문제 데이터 오류가 있다. 대회 당시 워낙 어려웠던 문제라 이의제기가 안됐을 뿐... http://blog.myungwoo.kr/6

O(N^2Ti)

일단 관찰 하나가 필요한데, 그 날이 끝났을 때 굳이 소독을 어떻게 맡길지 결정할 필요는 없다. 장난감이 필요할 때마다, 그전 상황을 끼워맞춰 가는 식으로 최대한 이득을 보는 상황을 결정하는 것이 필요하다.

그 전날에 상황을 끼워맞출 수 있는 가짓수는 크게 세가지가 있는데

 * 1. 장난감을 새로 샀다고 생각

 * 2. 그 전에 썼던 장난감을 1번 소독소에서 가져왔다고 생각

 * 3.  그 전에 썼던 장난감을 2번 소독소에서 가져왔다고 생각

2번과 3번 사이에서 결정하는 것은 탐욕적인 선택이 가능하다. 일반성을 잃지 않고 N1 >= N2, C1 <= C2라 가정하자. (N1 >= N2, C1 > C2일 경우에는, 결정이 자명해진다.) 그전에 썼던 장난감 리스트 중에서, 1번 소독소에서 가져올 수 있는게 있으면 무조건 그쪽, 아니면 2번 이런 식으로 하면 된다.

하지만, 1번과 2/3번 사이에서 결정하는 것은 탐욕적인 선택이 불가능함을 알 수 있다. 새로 사는 것이 항상 좋다 / 나쁘다라고 하는 게 생각보다 골치아프다.. 이를 위해서 새로 산 장난감의 양을 고정시키자. 양을 고정시키고, 구매에 쓴 돈을 고정시키면, 새로 산 것에서 가져오는 것이 무조건 제일 이득이다. 고로, 새로 산 장난감의 양을 0 ~ Sum(Ti) 까지 고정시키면서 탐욕법을 돌리면 된다.

탐욕법에 대해서 조금 더 부연설명을 하자면, 1번 소독소에서 가져왔다고 생각할 수 있는 애들 (S1), 2번 소독소에서 가져왔다고 생각할 수 있는 애들(S2)의 집합을 deque로 구현한다. 1번 소독소에 원소가 있다면, 가장 오래 전에 넣은 것을 빼고, 2번 소독소에 원소가 있다면, 가장 최근에 넣은 것을 뺀다. 이렇게 하면 O(N)에 탐욕법을 돌릴 수 있다.

O(N(lgN + lgTi))

상당히 독특하게 최적화되는데, T만큼의 장난감을 샀을 때 탐욕법의 해답을 F(T)라고 하자. 이 때 F(T)는 볼록함수임을 증명할 수 있다.

* 1. G(T) = F(T) - Tc*T가 볼록함수이면, F(T) 역시 볼록함수이다.

* 2. G(T)는 감소함수이다. 공짜 장난감이 하나 더 추가되었는데 해답이 나빠질 수 없다.

* 3. G(T) - G(T+1) >= G(T+1) - G(T+2)이다. 장난감을 하나 더 추가했을 때, G(T+1)은 G(T)에 비해서 가장 이득을 얻을 수 있는 부분을 최적화시킬 것이다. G(T+2)가 G(T+1)에 비해서 가장 이득을 얻을 수 있는 부분이 이보다 컸다면, 이는 이미 G(T+1)에 의해서 진행되었을 것이다. 고로 해당 부등식이 만족되고 볼록함수이다.

3번의 증명이 별로 마음에 안 들텐데.. 관심이 있으면 완벽한 증명이 있는 http://contest.usaco.org/TESTDATA/NOV08.toy.htm 쪽을 보는 것도 좋을 것이다.

아무튼, 볼록함수의 최솟값은 이진 / 삼진탐색으로 구할 수 있다. 볼록한 성질을 만족하는 구간을 초기에 잘 구별해야 함에 유의하라.

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