[USACO 2008 November Gold] Toys

문제: http://z-trening.com/tasks.php?show_task=5000000691
해법: http://ace.delos.com/TESTDATA/NOV08.toy.htm

* 이 문제 20번 데이터 출력 파일이 잘못 되었습니다. 올바른 답은 106110559이 아닌, 105265954 입니다. 해법 페이지에 있는 소스코드로 20번 입력데이터를 돌려보면 알 수 있습니다.

우선, N1 > N2, C1 < C2로 가정하자. 만약 아니라면 소독 회사가 하나만 있다고 볼 수 있기 때문이다.
미리 장난감을 총 t개 산다고 정하자.
그러면 이제 장난감을 총 t개 산다고 할 때, 소독하는데 최소 비용을 구해야한다.
문제에서는 장난감을 사용한 뒤, 장난감을 소독 회사에 맡긴다고 되어있는데, 우리는 미래의 상황에 대해서 알기 때문에, 이를 다른 관점으로 볼 수 있다. 장난감을 소독 회사를 통해 과거에서 가져온다고 생각할 수 있다. 그렇기 때문에 보다 쉽게 문제를 해결할 수 있다.
이 방법은 그리디하게 가능하다.

Day x에 대하여, 우선순위
1. n ≤ x-N1 인 Day n에 장난감이 남아있으면 n이 작은 날부터 소독회사 1을 통해 장난감을 가져온다.
2. n ≤ x-N2 인 Day n에 장난감이 남아있으면 n이 큰 날 부터 소독회사 2를 통해 장난감을 가져온다. n이 큰 날부터 가져오는 것은 소독회사 1을 통해 가져오는 것이 더 저렴하므로, 그를 위해 n이 작은 장난감들을 남겨두기 위함이다.

그러면 t를 일일히 정하고 정한 t에 대해 위와 같이 그리디 알고리즘을 돌리면, O(sum Ti * N)이다. 그러면 70%의 점수를 얻을 수 있다.

100%의 점수를 모두 얻기 위해서는 문제의 특이한 성질을 이용해야하는데,
f(t) 를 총 장난감을 t개 살 때 전체 최소 비용을 구하는 함수라고 정의해보자.
그러면 f(t)의 개형은 대략 다음과 같이 나온다.

총 장난감을 t개만 샀을 때 답을 구하는게 불가능하면 f(t)의 값은 무한값이다.
즉, f(t)는 볼록 함수이다. 이는 직관적으로 알기는 힘들고 증명은 뒤에 가서 하겠다.
f(t)가 볼록 함수라는 것을 알았을 때, 우리는 이를 이분검색, 삼분검색을 이용해서 최소가 되는 t값을 알 수 있다.
이분검색이 삼분검색보다 연산횟수가 적으므로, 이분검색에 대해 설명하겠다.
볼록 함수는 그래프가 감소하다가 최소점을 지나 증가하므로 f(t+1) > f(t)인 최소 t를 구하면 된다.
즉,
i) f(t) < f(t+1) 이라면, e = m-1, t = m
ii) f(t) > f(t+1) 이라면, s = m+1
를 반복해주면 된다.
그러면 시간 복잡도는 O(lg(sum Ti) * N)이 되어서, 100점을 받을 수 있다.

이제 함수 f(t)가 볼록 함수라는 것을 증명하겠다.
g(t)를 소독회사에 의한 최소비용합 값이라 하자.
∴ f(t) = g(t)+c*t (c는 장난감의 구매 비용값)
g(t)는 감소함수다. … ①
|g(t+1)-g(t)| ≥ |g(t+2)-g(t+1)| … ②
우선 ①, ②가 맞다고 해보자.
g(t+1)-g(t) ≤ g(t+2)-g(t+1)
f(t+1)-f(t) = g(t+1)-g(t)+c
∴ f(t+1)-f(t) ≤ f(t+2)-f(t+1)
∴ f는 볼록함수. 

①, ②에 대한 증명은 아래 인용을 참고하자. 해법 글의 일부이다. 사실 나도 증명을 100% 완전히 이해한건 아니고, 직관이 섞인 부분이 꽤 있기 때문에 내가 글을 쓰는 것보다 해법 글을 읽고 이해하려하는 것이 나을거라고 생각한다. (그 글이 영어일지라도...(?))

g is clearly a decreasing function of t, since having more toys can't possibly hurt. To be convex means that the improvement in g from adding each new toy is no greater than the improvement from the last toy added. This is intuitively clear, since if we add a toy, then anything we could've done with this toy to cut down costs could also have been done with the last toy. This can be made rigorous. Adding a toy just means that, at certain points, we can choose the cheaper option to clean a toy. If adding a second toy gives us a bigger savings than the first toy, we could've just chosen the cheaper option at all the points we chose for the second toy, except instead when we added the first toy. So, adding a later toy can never help us more than adding an earlier toy. This shows that g is convex, so the algorithm we proposed works, and we are done.

Note: To be even more explicit, on day i suppose that we use a_i toys cleaned with the cheap method and b_i toys cleaned with the expensive method. Let a_i¹, a_i², a_i³ denote the a_i for t, t+1, and t+2 toys. It is necessary and sufficient to show that sum( a_i³-a_i² ) <= sum( a_i² - a_i¹ ).

Indeed, if (a₁¹,...,a_k¹) is a possible sequence of a_i values for t toys, and similarly for (a₁², ...) and (a₁³, ...), then (a₁¹-a₁²+a₁³, ...) is easily seen to be a possible sequence for t+1 toys, so it follows that sum( a_i¹-a_i²+a_i³-a_i¹) = sum( a_i³-a_i² ) <= sum( a_i²-a_i¹), since the a_i² are an optimal sequence of a_i values for t+1 toys. This is a more algebraic proof of the argument we just made.

 

Toys.cpp