성적 (USACO Jan 07 Gold)

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

O(N^2lgN)

Ti / Pi 증가 순으로 정렬된 시험 결과들을 토대로 avg(D)를 정의하자. avg(D)는 그리디 전략으로 D개의 과목을 드랍했을 때 베시의 점수이며, (T(N-D+1) + .... T(N)) / (P(N-D+1) + ... P(N)) 이다.

이 때 베시가 더 좋은 점수를 낼 조건은 Sum(T) / Sum(P) > avg(D) 를 만족하는 크기 D의 집합이 있다는 조건이다. 비슷한 유형을 풀어보면 알겠지만, 이는 Sum(T - avg(D) * P)  > 0 을 만족하는 크기 D의 집합이 있다는 것과 동치이다.

Sum(T - avg(D) * P) > 0을 만족하는 집합이 있는지... 는 굳이 말 안해도 다들 알겠지만, 1 ~ N 과목들을 쭉 돌면서 가장 저 값이 큰 D개의 과목을 그리디하게 가져가면 된다. 이는 NlgN의 정렬을 통해서 풀 수 있으니. D 하나당 쭉 시도해보면 N^2lgN에 답을 구할 수 있다.

O(NlgN)

avg(D) 값 자체는 O(N)에 모두 계산 가능한 값들이니 지금 시간 overhead는 Sum(T - avg(D) * P) > 0을 만족하는 D짜리 집합이 있는지를 판별하는 부분이라는 것을 알 수 있다. 저 함수를 빠르게 계산하는 것이 중요한 포인트다.

저런 걸 쉽게 해주는 data structure가 있을까? 일단 D = 1이라 쳐보자. T - x * P > 0을 만족하는 애가 있는지를 판별하는 건, Convex Hull Trick 스타일의 자료구조를 쓰면 알 수 있다는 걸 확인할 수 있다. 선분 집합에서 f(x)를 최대로 하는 게 무엇인지를 보면 된다. 하지만 D는 N까지도 올라갈 수 있기 때문에 일단 지금 저런 자료구조를 찾는건 의미가 없어 보인다.

여기서 짚고 넘어갈 것은 적어도 Sum(T - avg(D) * P) = 0을 만족하는 집합은 무조건 있다는 점이다. [N - D + 1, N] interval 안에 있는 과목이 바로 그를 만족하는 집합이 될 것이다. 그러면 Sum(T - avg(D) * P) != 0인지만 판별하면 되는데..! 이 말은 가장 큰 D개의 성적 중에서 [N - D + 1, N] interval 안에 없는 과목이 있다는 것을 뜻한다.

이제 D개의 선분의 합을 구할 필요 없이 깔끔하게 처리할 수 있는 방법을 낼 수 있다. [N - D + 1, N] interval 안에 있는 과목 중 T - x * P를 최소로 하는 과목이. [1, N - D] interval 안에 있는 과목 중 T - x * P를 최대로 하는 과목보다 값이 작으면, 해당 과목은 가장 큰 D개의 성적 안에 포함됨을 알 수 있다.

고로 이러한 고찰을 통해서 우리가 도달한 결론은

[N - D + 1, N] 구간의 Min(T - avg(D) * P) < [1, N - D] 구간의 Max(T - avg(D) * P)

를 만족하면 D를 찍으면 된다는 것이다. 이제 저걸 구하는 자료 구조가 필요한데 저건 convex hull trick으로 될법한 쿼리들이다. 두가지 방법을 소개하겠다.

일단 convex hull trick을 쓰기 전에 avg(D) <= avg(D+1)이라는 점을 짚고 넘어가겠다. 이 점을 짚고 넘어가지 못하면 첫번째 방법은 로그가 하나 더 붙고, 두번째 방법은 코드가 몇십줄이 늘어난다.

1. Segment Tree + CHT

이건 요즘 내가 자주 쓰는 방법인데 merge sort tree의 요령으로 각 노드가 구간의 선분을 convex hull trick으로 가지고 있도록 한다. (convex hull trick을 구조체로 미리 구현해 두는게 핵심) initialize는 O(NlgN)이다. 대충 짜면 O(Nlg^2N)이 될 수도 있음.

이제 들어오는 쿼리는 모두 구간 선분 최솟값 등을 물어보는 쿼리이니 lgN개의 노드에 대해서 대답해주면 된다. 쿼리의 단조성 덕에 이진 탐색이 필요하지 않다. 쿼리당 lgN이라 복잡도는 O(NlgN)

2. Sweeping + BST + CHT

위 방법보다 훨씬 직관적이고 빠르게 동작하지만, 코딩이 복잡한게 흠이다. 질의로 들어오는 구간이 너무 깔끔하기 때문에, 다음과 같은 방법을 쓴다.

1. CHT에 i번째 선분을 넣는다.

2. avg(i) 쿼리를 때린다.

CHT에 선분을 넣을 때 주의해야 할 점은 기울기에 단조성이 없다는 점이다. 그러한 상황에서 온라인 쿼리를 처리하려면 std::set을 통해서 동적으로 convex hull trick을 가지고 있어야 한다. 코딩 방법에 대해서는 생략하도록... 하겠다.

쿼리를 넣는 거는 일반 컨벡스 헐 트릭과 비슷하다. 데큐를 쓰듯이 앞을 잘라가면서 올라가면 amortized O(NlgN)에 풀 수 있다.

여담으로 "그냥" 컨벡스 헐로도 풀 수 있다고 한다. 그쪽은 생각을 안해봤는데 코드는 훨씬 짧다고 알고 있다. 관심이 있으면 http://contest.usaco.org/TESTDATA/JAN07.schul.htm 를 참고.