IOI16 Aliens

최대 $k$ 개의 사진을 찍을 수 있을 때, 모든 흥미로운 위치를 포함하기 위한 최소 영역의 크기를 찾아야 한다.

일단 필요 없는 점을 제거하거나 $x$ , $y$ 좌표가 서로 바뀌어도 동치라는 사실을 바탕으로 $x_i<x_{i+1}$ , $y_i<y_{i+1}$ , $x_i\leq y_i$ 를 만족하도록 흥미로운 위치를 정렬한다.

이 문제를 풀때 방해되는 것이 $k$ 가 사진의 장수를 제한하고 있다는 것이다.

방해되는 $k$ 를 치우기 위해 $k$ 값이 변화할 때 cost의 변화를 그려보면 위 그래프와 같이 감소하면서 볼록하다는 것을 관찰할 수 있다.

이 그래프에서 $x$ 좌표가 $k$ 값일 때 $y$ 좌표가 답이 된다.

그러나 아직 그래프의 각 점들의 좌표를 알 수가 없다.

여기서 이상한 생각을 할 수 있는데…

그래프의 접선의 기울기를 주면 (정확히는 접선이 아니지만 접선이라고 하자)

접점의 좌표를 알 수 있다는 것이다.

이것은 접선의 기울기를 $-c$ 라고 하면 $f(k)+ck$ 의 최솟값을 구하는 것과 같다.

$f(k)+ck$ 는 원래 문제에서 사진을 찍는 비용에 $c$ 원을 추가한 것과 같다.

접점 (k, )는 Convex Hull Trick을 이용하면 $O(n)$ 에 구할 수 있다.

이제 접선의 기울기가 감소하므로 최소( $-m^2$ )부터 최대( $0$ )까지 이분탐색을 통해 $x=k$ 인 점을 찾을 수 있다.

주의할 점은 여러 점들의 접선의 기울기가 같을 때는 그중 한 점의 좌표만 나온다는 것이다.

시간복잡도는 $O(n\log m)$ 이다.

코멘트