Faker's algorithm

이 글 을 보고 작성하였다.

BOJ 1763 트리 색칠 이나 AGC 023 F. 01 on Tree 문제는 다음과 같은 최적화 문제로 표현할 수 있다:

• 트리의 모든 topological order $p$ 중에서, \sum_{p(i) < p(j)} a_i b_j 의 합을 최소화하여라.

예를 들어 트리 색칠은 $a_i = 1, b_j = C[j]$ 고 01 on Tree는 $a_i = V_i, b_j = 1 - V_j$ 라고 할 수 있다.

이 문제를 푸는 알고리즘은 다음과 같다. 만약에 어떤 루트가 아닌 노드의 $b_v / a_v$ 가 트리 전체에서 최대면, 최적해에서 $p$ 와 $v$ 가 인접하게 등장함을 증명할 수 있다. 구체적인 증명은, $[p \ldots w v]$ 의 꼴일 때 $v, w$ 를 바꿔서 손해를 볼 수가 없음. 그래서 저런 최대를 찾은 후 $(p, v)$ 를 contract시켜주는 식으로 답을 구할 수 있다. 이걸 priority queue + dsu 로 구현하면 $O(n \log n)$.

웰노운이라고 하면 웰노운이고 아니라고 하면 아닌 알고리즘인데, 생각하기는 정말 어렵다고 생각한다. 지금 봐도, 정당성은 쉽게 이해가 되지만 구체적인 직관이 뭔지 감을 잡을 수가 없다. 최적화하는 함수가 길어서 이름을 붙이기가 어려운데, 알고리즘의 발명과 아무 상관이 없어도 이름이 잘만 붙는 것 같아서 이 글에서는 이제 위 알고리즘을 Faker's algorithm이라고 정의하여 명명한다.

정확히 저런 함수가 아니라고 해도 Faker's algorithm을 적용할 수 있는 케이스가 알려져 있다. BOJ 9539 Escape 이나 BOJ 18596 Monster Hunter같은 문제가 그 예시이고 함수는 다르지만 똑같은 exchange argument로 해결이 가능하다. 사실 저 문제들의 자연스러운 풀이는 small-to-large를 사용하는 풀이라고 생각한다. Faker's algorithm을 적용할 수 있다는 것 자체가 조금 비직관적인 경우이다.

최근에 배웠던 건 Faker's algorithm을 사용하여 BOJ 18796. 이동하기 4 역시 해결할 수 있다는 것이다. 이 문제의 일반적인 해법은 convex hull에 속하는 직선만을 딴 후 그 안에서 그리디를 하는 것인데 convex hull을 따는 것도, 그리디가 되는 것도 모두 비직관적이라고 생각했다. 하지만 이 문제는 위에서 서술한 최적화 문제로 표현할 수 있고, 그렇게 하면 Faker's algorithm을 그대로 적용할 수 있다. 이해불가능한 마법 두개를 이해불가능한 마법 하나로 바꿀 수 있으니 괜찮은 거래라고 생각한다 (ㅎㅎ)

루트를 하나 달고, root - row 1 - row 2 - ... - row n, root - col 1 - col 2 - ... - col m 같은 식으로 체인을 달자. 그러면 topological sort에서 row k를 선택했다는 건 현재 위치에서 아래로 갔다는 뜻이고 column k를 선택했다는 건 현재 위치에서 오른쪽으로 갔다는 뜻이 된다. row k를 선택했을 때 비용은 앞에 column을 몇개 먹었느냐로 정의된다. (root - col 1 - col 2 - ... - col l) + (root - row 1 - row 2 - ... - row k) 의 $a_i$ 합이 $B[l+1]$ 이 되도록 가중치 세팅을 하면, $b_i = 1$ 인 $\sum_{p(i) < p(j)} a_i b_j$ 최소화 문제가 된다.

정확히 저렇게 세팅하는 건 안되지만 합이 $B[l + 1] + f(k)$ 같은 식으로 나오게 세팅하는 건 된다. 대충 col l에 대응되는 정점 $v$ 에 $a_v = B[l+1] - B[l]$ 을 세팅해 주면 된다. 이제 그냥 최소화 후 $- \sum f(k)$ 를 빼주면 된다. 여기서 $a_v$ 는 음수가 되어도 상관이 없음을 알 수 있다 (정확히는 모든 $(a_i, b_i)$ 벡터가 180도 미만의 범위 안에 있으면 됨). 이제 Faker's algorithm을 그대로 적용하면 $O(n \log n)$ 에 문제를 해결할 수 있다.

Faker's algorithm을 사용한 계산은 사실 convex hull을 사용하는 그리디랑 동치임을 이해하면 좋다. (구체적으로는 Faker's algorithm이 일반화된 버전이고 convex hull은 특수 성질을 사용하여 ad-hoc하게 단순화한 경우) 이동하기 4의 트리는 2개의 체인으로 이루어져 있다. 이 트리에서 돌리는 그리디는 $a_v / b_v$ 가 트리 전체에서 최소인 $v$ 를 잡아 부모와 merge하는 걸 반복하는 그리디이다. 만약 어떤 인접한 두 정점 $p - v$ 에 대해서 $a_p / b_p > a_v / b_v$ 라고 하자. $p$ 가 어떤 다른 부모와 merge하기 전에, $v$ 가 먼저 $p$ 와 merge할 것이라는 것을 알 수 있다. 고로 이 경우에는 $p$ 와 $v$ 를 처음부터 merge해 줄 수 있다. 이를 반복하면 한 체인에 대해서 $a_v / b_v$ 가 증가하게끔 체인을 수정해 줄 수 있다. $a_p / b_p$ 가 증가하는 체인 두개에서 그리디를 돌리는 건 merge sort와 동일하다. $a_v / b_v$ 가 증가하도록 체인을 수정하는 건 convex hull을 구하는 것과 동일하고, merge sort로 합쳐주는 건 convex hull을 구한 후 그리디하게 합치는 것으로 이해할 수 있다.

이러한 방식으로 Heavy is the Stone BOJ 18760. Heavy Stones 도 해결할 수 있다. 이 문제는 각 $k$ 에 대해서 root - 1 - 2 - ... - (k-1), root - n - (n-1) - ... - (k+1) 과 같이 path를 두개 만들어주면 정말 트리 색칠이랑 동일한 문제가 된다. 위 관찰을 사용하면 prefix/suffix 컨벡스헐을 빠르게 합쳐주는 자료구조 문제가 된다.

연습 문제:

• BOJ 문제집
• AGC 023 F. 01 on Tree
• Universal Cup. Train Seats