ACM ICPC Daejeon 2014 - Two Yachts

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=639&page=show_problem&problem=4917

설명이 개판인 점은 양해 부탁한다 (풀이 쓸 시간이 없음.. ㅠㅠ)

어떠한 시간에 대해서 겹치는 구간이 100개인데, 이는 임의의 interval i 에 대해서, sj < si이며 자신과 교차하는 interval이 100개 이하라는 것으로 해석할 수 있고, 고로 모든 교차 쌍의 개수가 100N개 이하라는 결론으로 귀결된다.

요트를 모두 시작점 순으로 정렬하자. 만약에 요트가 단 하나라면, 간단한 dynamic programming을 통해서 O(N)에 해결할 수 있다. 문제는 요트가 두개라는 점인데, 일단 O(N^2) 점화식을 다음과 같이 세울 수 있다.

 * D[i, j] = 1번 요트는 현재 i번 스케줄 처리. 2번 요트는 현재 j번 스케줄 처리할 시 최소 비용.

 * D[i, j] = min(D[i+1, j] + W[i+1] - W[i], D[i, j+1] + W[j+1] - W[j])

 * D[i, j] = D[k, j] + W[k] (E[i] < S[k] 를 만족하는 최소의 K)

 * D[i, j] = D[i, k] + W[k] (E[j] < S[k] 를 만족하는 최소의 K)

문제를 해결할 때 O(N^2)는 안되고, O((100N)lg(100N)) 정도의 빠른 풀이를 생각해야 한다. 이를 위해서 D[i, j]를 교차쌍에 대해서만 관리해줄 수 있다. E[i] = (k >= i 인 모든 D[k, ?] + W[k] + W[?] 중 최댓값) 이라고 정의하면, 교차쌍을 벗어나는 모든 이벤트들을 고려할 수 있다. 고로, 점화관계에서 교차쌍을 벗어나지 않는 이벤트들은 위 점화식대로, 아니면 E[] 배열을 참고하면 된다. D[] 값을 채워줄 때마다 E 값 역시 채워져야 한다.

코딩 시, 같은 이벤트를 두개의 요트에서 두번 처리하고, 두배의 이득을 얻는 일이 없도록 주의하자.

https://gist.github.com/koosaga/19ad0f218e9c3940517a684ae15f1b5c