jhwest's Blog

자력으로 못 푼 문제라서 이렇게 블로그 포스팅으로 오래 기억에 남기려고 한다.

수직선 위에 $N$개의 빨간 점과 $M$개의 파란 점이 서로 다른 위치에 있다. 우리가 할 일은 빨간 점과 파란 점을 적당히 연결해서, 모든 점이 적어도 하나의 반대 색 점과 연결되어 있게 만드는 것이다. 두 점 $x$와 $y$를 잇는 비용은 당연히 $|x - y|$ 로 주어진다.

우선 빨간 점과 파란 점을 분리해서 두 개의 수직선 위에 이분그래프처럼 표현하고 최적해의 성질을 관찰해보자. 만약 최적해에서 두 선분이 교차한다면, 교차하지 않도록 풀어주어도 길이의 합은 증가하지 않는다. 그래서 우리는 항상 모든 선분들이 교차하지 않는 최적해가 존재한다고 가정해도 무방하다.

선분들을 적당히 이어놓고 이리저리 조작을 가해보면서 언제 더 답이 작아지는 지 다양한 시도를 해보자. 몇 가지 성질을 추가적으로 알아낼 수 있는데, 우선 선분들로 이루어진 길이 3 이상인 경로가 존재하면 가운데 간선을 제거해도 연결 조건을 여전히 만족한다. 이 사실로부터 우리는 최적해의 각 컴포넌트가 반드시 “성게” 모양이여야 한다는 것을 알 수 있다.

또 차수가 2 이상인 정점¹ $u$와 연결된 정점 $v$가 있을 때, $v$에게 있어서 $u$보다 더 거리가 가까운 반대 색깔의 정점 $w$이 있다면 $u$와 $v$의 연결을 끊고 $w$와 $v$를 연결해도 연결 조건은 여전히 만족하고, 길이의 합은 증가하지 않는다.

이 정도 성질을 얻어낸 것에 만족하고 풀이를 한번 떠올려보자. 우선 선분이 교차하지 않는다는 조건으로부터, 쉬운 $\mathcal{O}(n^2)$ DP 풀이를 얻는다. 두 문자열의 LCS를 구하는 알고리즘과 작동 원리가 같은데, $DP[i][j]$를 ($i$번째 빨간 점, $j$번째 파란 점까지 봤을 때 연결 조건을 만족하는 경우 최소 비용) 으로 정의하면,

\[DP[i][j] = \min\{Dp[i - 1][j], Dp[i][j - 1], Dp[i - 1][j - 1]\} + abs(A[i] - B[j])\]

정도의 점화식을 얻는다. 이 풀이를 개선해보려고 한다. 우선 $DP[i]$ 를 ($i$번째 점 이전까지만 봤을 때 연결 조건을 만족하는 경우 최소 비용)으로 정의하고², $i$번째 점을 $P$라고 하고 편의상 빨간색이라고 하자. $P$와 $Q$를 잇는다고 했을 때, 그 사이에 존재하는 점에 집중한다.

$P$와 $Q$ 사이에 파란 점이 존재한다면, 그 점은 반드시 $P$와 연결되어야 한다. $P$보다 왼쪽에 위치하는 점과 연결하게 된다면 선분이 교차하고, $P$보다 오른쪽에 위치하는 점과 연결할 바에는 $P$와 연결하면 길이의 합이 줄어들기 때문이다³. 이 말을 다시 해석하면, $P$가 만약 자신의 왼쪽에 있는 점과 연결된다면 $P$는 반드시 그 중 가장 오른쪽에 위치한 파란색 점과는 연결되어야 한다. $P$가 자신의 왼쪽에 있는 점과 연결되지 않는다면 $DP[i-1] + (P_i\textrm{와 가장 가까운 파란색 점 사이의 거리})$ 로 쉽게 표현이 되므로, 그렇지 않은 경우를 고려하자.

이제 $P$와 $Q$ 사이에 파란 점이 없다고 가정해도 된다. $P$ 바로 왼쪽의 빨간 점을 $l(P)$, $Q$ 바로 왼쪽의 파란 점을 $l(Q)$라고 하자. 위의 성질들을 사용해서, $l(Q) < Q < l(P) < P$ 의 위치관계를 가질 때 반드시 $l(P)$와 $l(Q)$이 연결되어야 함을 보일 수 있다⁴. 그러면 $l(l(Q)) < l(Q) < l(l(P)) < l(P)$의 위치관계일 때 $l(l(P))$와 $l(l(Q))$가 이어지고⁵, $\dots$⁶. 요약하면 $l^k(P) < l^{k-1}(Q)$ 가 되는 최소의 $k$에 대해서 $P$와 $Q$, $l(P)$와 $l(Q)$, $\dots$, $l^{k-1}(P)$와 $l^{k-1}(Q)$가 반드시 이어져야 한다. $k$는 $i - 2k + 1, \dots, i$의 빨간 점과 파란 점의 개수가 같아지는 최소의 자연수와 같고, 여기서 아래 점화식을 얻는다.

\[DP[i] = DP[i - 2k] + (P - Q) + (l(P) - l(Q)) + \dots + (l^{k-1}(P) - l^{k-1}(Q))\]

정리하면 $DP[i]$를 구성하는 모든 케이스는 위 두 가지 식에 의해서 전이된다. 각 식을 $\mathcal{O}(n + m)$에 계산할 수 있기 때문에 전체 문제를 $\mathcal{O}(n + m)$에 해결할 수 있다.

(*) 실패한 접근으로, MCMF 모델링을 하려는 시도를 했다. 이 생각을 하게 된 계기는 우선 유사한 문제에서 MCMF 모델링이 성공한 사례가 있기 때문이다(ex. APIO 2007. Backup). 하지만 저런 류의 문제는 보통 최적해의 간선의 개수가 고정되어 있어서 max flow의 값을 그 개수로 지정해줄 수 있는 반면, 이 문제는 모든 점이 `연결되어 있어야 한다는 조건 때문에 위치 관계에 따라서 사용하는 간선의 개수가 달라질 수 있어서 문제가 된다. 모델링이 어찌저찌 잘 된다고 하더라도, Augmenting path들이 복잡하게 생길 수도 있어서 2019 KAIST RUN Spring Contest F. Eat Economically 처럼 Priority queue 등으로 이를 빠르게 관리하는 것도 기대하기 힘들다.

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int INF = 1e9 + 10;

ll min_total_length(vector<int> R, vector<int> B) {
	int n = R.size(), m = B.size();
	vector<pair<int, int>> A;
	A.emplace_back(0, 0);

	int p = 0, q = 0;
	while (p != R.size() && q != B.size()) {
		if (R[p] < B[q]) {
			A.emplace_back(R[p++], 1);
		}
		else A.emplace_back(B[q++], 2);
	}
	while (p != R.size()) {
		A.emplace_back(R[p++], 1);
	}
	while (q != B.size()) {
		A.emplace_back(B[q++], 2);
	}

	vector<int> C(n + m + 1, INF), H(2 * (n + m) + 1, -1);
	vector<ll> Dp(n + m + 1), Rs(n + m + 1), Bs(n + m + 1);
	int r = -1, b = -1;
	for (int i = 1; i <= n + m; i++) {
		if (A[i].second == 1 && b != -1) {
			C[i] = min(C[i], A[i].first - b);
		}
		if (A[i].second == 2 && r != -1) {
			C[i] = min(C[i], A[i].first - r);
		}
		(A[i].second == 1 ? r : b) = A[i].first;
	}
	r = -1; b = -1;
	for (int i = n + m; i >= 1; i--) {
		if (A[i].second == 1 && b != -1) {
			C[i] = min(C[i], b - A[i].first);
		}
		if (A[i].second == 2 && r != -1) {
			C[i] = min(C[i], r - A[i].first);
		}
		(A[i].second == 1 ? r : b) = A[i].first;
	}
	int h = 0; H[n + m] = 0;
	for (int i = 1; i <= n + m; i++) {
		h += (A[i].second == 1) ? 1 : -1;
		Dp[i] = Dp[i - 1] + C[i];
		Rs[i] = Rs[i - 1] + (A[i].second == 1 ? A[i].first : 0);
		Bs[i] = Bs[i - 1] + (A[i].second == 1 ? 0 : A[i].first);
		if (H[n + m + h] != -1) {
			int x = H[n + m + h];
			Dp[i] = min(Dp[i - 1] + C[i], Dp[x] + abs(Rs[i] - Rs[x] - Bs[i] + Bs[x]));
		}
		H[n + m + h] = i;
	}
	return Dp[n + m];
}

성게의 중심만 가능하다. ↩
왜 이렇게 접근하는 것이 자연스럽냐고 하면 역시 직관의 차이인 것 같다. 나는 이 접근을 처음에 생각하지 못했다. ↩
여기서 $P_i$보다 오른쪽에 위치하는 점의 연결 조건은 고려하지 않는다. ↩
정확히는, 그 외의 케이스는 전부 $DP[i-1] + (P_i\textrm{와 가장 가까운 파란색 점 사이의 거리})$ 에서 처리가 된다. ↩
그렇지 않다면, $l(l(P))$와 $l(Q)$가 연결되는 경우만 가능한데 이러면 $l(Q)$와 $l(P)$의 연결을 끊고 $Q$와 $l(P)$를 연결하는 것이 $l(P)$의 위치관계 때문에 이득이다. ↩
이 과정을 계속 반복하다가 어느 순간 한 쪽 정점이 모두 연결되어 버리는 상황이 생길 수도 있다. 그 경우 남은 정점들은 모두 반대 쪽의 첫 번째 정점에 연결되어야 하는데, [\^5]에 의해 그렇게 되면 반드시 더 최적인 해가 존재한다. 따라서 그런 일은 생기지 않는다. ↩

IOI2017 Day1 Wiring

4012 컨벤션 센터

Problem

Test