분수 Objective function의 최대화

다음과 같은 문제를 생각해 보자.

크기 N의 수열이 있을 때, 길이 K 이상인 구간 중 최대 평균을 계산하라.

식을 전개해 보자. 주어진 입력의 부분합을 Si 라고 하면, j - i >= K 일 때 (Sj - Si) / (j - i) 를 최대화해야 한다. 하지만 그렇게 쉬워 보이지 않는다. 어떻게 해야 할까?

1. 답에 대한 이진 탐색

어떠한 문제의 가능한 최대 / 최솟값을 계산하기 위해서, 문제를 결정 문제로 바꿔서 이진 탐색을 하는 방법이 잘 알려져 있다. 

예를 들면, "가능한 답 중 최댓값을 계산하라" 는 문제를, "X 이상이 이 문제에서 가능한 답인지를 판단하라"는 문제로 바꾸면, 가능한 답 중 최대인 X를 이진 탐색으로 판별할 수 있다. 만약에 최댓값을 계산하는 것은 어렵지만, X 이상이 가능한 답인지를 판단하는 것이 쉬운 이러한 테크닉은 최댓값의 계산이 어렵지만, X 이상이 가능한 답인지를 판단하는 것이 쉽다면, 문제를 해결할 수 있다.

이 문제에서 이 방법을 적용시켜 보자. 평균이 X 이상인 길이 K 이상인 구간을 판별하는 문제로 변환을 했을 때, 이 문제를 O(N) 정도에 해결하면 된다는 것을 알 수 있다. 식을 전개해 보자. 주어진 입력의 부분합을 Si 라고 하면, j - i >= K이며, (Sj - Si) / (j - i) >= X인 (i, j) 쌍의 존재를 찾는 문제가 된다. 식을 풀면, Sj - jX >= Si - iX이며 j - K >= i 인 (i, j)를 찾아야 한다는 사실을 알고 있다. j를 증가시키면서, j - K 이하의 모든 i에 대해서 Si - iX의 최솟값을 가지고 다니면 쉽게 문제를 풀 수 있다.

2. 기하학적 접근

모든 i에 대해서 (i, Si)에 점들을 찍어 보자. 우리가 찾고 있는 것은 x 좌표 차이가 K 이상인 최대 기울기의 선분을 찾는 것이다. 이를 효율적으로 할 수 있을까?

(j, Sj) 를 고정시켰다면, i <= j - K 구간에 있는 모든 점 중 (j, Sj) 와 연결했을 때 기울기가 최대인 선분은 접선이다. 이는 컨벡스 헐 내부에서 이분 / 삼분 탐색을 함으로써 알 수 있다. 고로, 위에서 prefix minimum을 가지고 다녔듯이, prefix에 대한 컨벡스 헐을 가지고 다니면 O(nlgn) 정도에 문제를 해결할 수 있다.

분수 objective function을 최대화하는 문제들은 다음과 같은 문제들이 있다. 첫 문제 빼고는 다 기하학적 접근이 가능한 문제이다.

 * APIO 2017. Merchants

 * COCI 2014/2015 Prosjek

 * USACO Mar 2014 Gold Sabotage

 * ICPC 2009 Seoul. GC Ratio

* NEERC 2012. Caravan Robbers