Palembang Bridges (APIO 2015)

당시 대회에서 실제로 맞닥뜨린 문제인데, O(NlgN) 풀이에 꽤 근접했지만 (ㅠㅠ) 결국 제대로 된 풀이를 만드는 데 실패하고 O(N^2lgN) 의 풀이를 짤 수밖에 없었다.

문제는 상당히 단순하다. 이것저것 description이 복잡하게 들어와 있지만 요약하자면

K = 1인 경우 N개의 (Ai,Bi) 쌍이 주어졌을 때 |Ai - X| + |Bi - X| 를 최소화 하는 X를 찾으면,

K = 2인 경우 N개의 (Ai,Bi) 쌍이 주어졌을 때 min(|Ai - X| + |Bi - X|,|Ai - Y| + |Bi - Y|) 를 최소화하는 X,Y를 찾으면 된다.

K = 1인 경우는 쉬운 그리디 알고리즘이 존재한다. 2N개의 원소가 들어있는 A + B 집합에서의 N번째 원소가 답이다. 복잡도는 O(NlgN) 으로 22점을 얻을 수 있다.

K = 2인 경우에 첫번째로 관찰해야 할 것은, 건물이 없는 곳에 (즉, A에도 B에도 속해있지 않은 위치 X에) 다리를 지을 필요가 없다는 것이다. 이를 관찰하는 것 역시 어렵지 않으며 이 때 X Y 모두 O(N) 개의 경우의 수가 있으므로 O(N^3) 알고리즘이 나오며 31점을 얻을 수 있다.

이제 편의상 X < Y라고 두었을 때 관찰해야 할 점은

Ai + Bi <= X + Y일 경우, min(|Ai - X| + |Bi - X|,|Ai - Y| + |Bi - Y|) = |Ai - X| + |Bi - X|

Ai + Bi > X + Y일 경우, min(|Ai - X| + |Bi - X|,|Ai - Y| + |Bi - Y|) = |Ai - Y| + |Bi - Y|

라는 것이다.

직관적으로 당연하게 여기는 사람들도 있는 듯 하지만 난 그렇지 않아서 증명했다. 9개의 케이스 ( (X < A, A <= X < B, X < B)^2 ) 를 나누면 쉽게 증명 가능하다.

나는 여기서 X + Y를 고정하지 않으면 문제를 풀지 못할거라 생각을 했고, 결국 이 풀이를 포기했는데 실제로는 굳이 그럴 필요가 없다. (이후 풀이는 윤모 국대님... 에게 상당한 도움을 받아서 작성했다. 보실라나..)

여기서 상당히 그리디한 접근이 필요한데, 다음 알고리즘은 항상 최적값을 찾는다. 편의상 Ai + Bi 값 순으로 원소가 정렬되어 있다고 가정하자.

* 1 <= i <= N 범위에서 [1,i] 는 A로 가고 [i+1,N] 은 B로 가는 상황을 항상 만들 수 있으며, 답은 이 중 하나이다.

* 이 때, [1,i] 에서 K = 1일 때의 문제를 풀고 (A), [i+1,N] 에서 K = 1일 때의 문제를 독립적으로 푼 후 (B) 합치면, 그 때의 답보다 우월하거나 같은 답을 항상 만들 수 있다.

먼저, A와 B가 어떻게 나오던간에 [1,i] 구간에 있는 원소는 무조건 A로 보내고, [i+1,N] 구간에 있는 원소는 무조건 B로 보내도록 하자. 물론 이것보다 좋은 답이 다른 i에서 나올 수도 있겠지만 그것을 굳이 우리가 증명할 필요는 없다.

또한, A + B가 항상 Ai + Bi <= A + B <= Ai+1 + Bi+1 에 있다고 가정했을 때의 최적해를 C, D라고 하자. 이 최적해는 A와 B로 보내는 것이 항상 자연스러울 것이며 궁극적으로 우리가 구하고자 하는 목표이기도 하다.

이 때, C와 D는 A와 B와 다를 수 있다는 사실 하나만으로 해당 답보다 열등하거나 같다는 사실을 감안하면, 앞의 알고리즘의 정당성을 증명할 수 있다.

[1,i] 에서 K = 1일 때 문제를 바꾸면서 푸는 것은 Plane Sweeping과 Indexed Tree를 동반하면 어렵지 않다. 이의 역순 역시 동일하다. 이 방법을 사용하면 O(NlgN)에 문제를 해결할 수 있다.