Convex Hull Optimization

Convex Hull Optimization이란, Convex Hull Trick이라고도 알려져있으며 특정 점화식 꼴을 가지는 동적계획법에서 시간을 줄이는 방법이다. IOI2002에 처음 나왔다고는 하나, 제대로 알려지기 시작한 것은 APIO2010 특공대 문제 이후라고 생각한다. 때문에 APIO2010 특공대 문제를 예시로 Convex Hull Optimization 설명을 시작하겠다.

 

$S_i = \sum_{k=1}^{i} x_k$ 를 정의하자. 단, $S_0 = 0$

 

DP 배열을 아래와 같이 정의한다.

$D_i$ = 1번부터 $i$번 병사까지 특공대를 나눌 때 전투력 합의 최대값. 단, $D_0 = 0$

 

이 때, 점화식은 아래와 같이 된다.

$D_i = \max(D[j] + A(S_i-S_j)^2 + B(S_i-S_j) + C)$

 

최종 답은 $D_N$이 되며 계산 시간복잡도는 $O(N^2)$이다.

 

이를 시간복잡도 $O(N)$에 해결하기 위해 점화식을 전개해보자.

$D_i = \max((-2AS_j)S_i + (AS_j^2 - BS_j + D_j)) + AS_i^2 + BS_i + C$

 

$AS_i^2 + BS_i + C$는 $j$와 무관한 $i$에 대한 상수이므로 $\max$ 함수 밖으로 뺄 수 있다. 그리고 $\max$ 함수 안에서는 $S_i$에 대한 다항식으로 표현했다.

 

$f_j(x) = (-2AS_j)x + (AS_j^2 - BS_j + D_j)$라고 정의하면 $A < 0$, $S_j > 0$이기 때문에 기울기가 양수인 일차함수가 된다. 때문에 $\max(f_j(S_i))$를 그래프로 그려보면 아래 그림처럼 볼록 껍데기의 부분 모양이 나온다.

 

 

$i$가 하나 증가할때마다 $\max$ 함수안에 일차 함수가 하나씩 더 추가되는 꼴이다. 이 문제에서 일차함수 $f_j(x)$의 기울기는 $j$가 커짐에 따라 커진다. 즉, 나중에 추가되는 일차 함수의 기울기가 크다. 따라서 볼록 껍데기를 스택을 통해 관리해줄 수 있다.

 

이제 $D_i$를 그래프와 직선 $x = S_i$의 교점의 $y$ 좌표를 구하는 것으로 계산할 수 있다. 이는 이분탐색을 통해 해결할 수도 있지만, $i$가 증가함에 따라 $x = S_i$도 증가하므로 이 또한 전체 $O(N)$ 시간안에 해결할 수 있다.

 

* 두 직선의 교차점의 x 좌표를 실수형 변수로 직접 구해서 해결하는 코드

#include <bits/stdc++.h> using namespace std; #define MAXN 1000006 typedef long long lld; int N, A, B, C; int V[MAXN], S[MAXN]; int stk[MAXN], scnt; double xpos[MAXN]; lld D[MAXN]; double get_cross(int p, int q) { lld a1 = -2LL*A*S[p], b1 = (lld)A*S[p]*S[p] - (lld)B*S[p] + D[p]; lld a2 = -2LL*A*S[q], b2 = (lld)A*S[q]*S[q] - (lld)B*S[q] + D[q]; return (double)(b1 - b2) / (a2 - a1); } int main() { scanf("%d%d%d%d", &N, &A, &B, &C); for (int i=1;i<=N;i++) scanf("%d", V+i), S[i] = S[i-1] + V[i]; int pt = 1; for (int i=1;i<=N;i++){ // j = 0일 때 계산 D[i] = (lld)A*S[i]*S[i] + (lld)B*S[i] + C; if (scnt){ while (pt < scnt && xpos[pt+1] < S[i]) pt++; // j > 0인 j에 대해 점화식 우항이 최대인 j를 구힘 int j = stk[pt]; D[i] = max(D[i], D[j] + (lld)A*(S[i]-S[j])*(S[i]-S[j]) + (lld)B*(S[i]-S[j]) + C); // 그래프에 일차함수 하나 추가 while (scnt > 1 && xpos[scnt] > get_cross(stk[scnt], i)) scnt--; stk[++scnt] = i; xpos[scnt] = get_cross(stk[scnt-1], i); if (pt > scnt) pt = scnt; }else{ stk[++scnt] = i; xpos[scnt] = -1e18; } } printf("%lld\n", D[N]); }

 

* 128비트 정수형을 이용하여 실수형 변수 사용을 피하는 코드

#include <bits/stdc++.h> using namespace std; #define MAXN 1000006 #define sz(v) ((int)(v).size()) typedef long long lld; typedef __int128_t lll; int N, A, B, C; int V[MAXN], S[MAXN]; lld D[MAXN]; struct LINE{ int a; lld b; lld get(int x)const{ return (lld)a*x+b; } lll operator * (const LINE &ot)const{ return (lll)a*ot.b-(lll)ot.a*b; } }; lll ccw(const LINE &a, const LINE &b, const LINE &c){ return a*b + b*c + c*a; } int main() { scanf("%d%d%d%d", &N, &A, &B, &C); for (int i=1;i<=N;i++) scanf("%d", V+i), S[i] = S[i-1] + V[i]; vector<LINE> stk = {{0, 0}}; for (int i=1,pt=0;i<=N;i++){ while (pt+1 < sz(stk) && stk[pt].get(S[i]) <= stk[pt+1].get(S[i])) pt++; D[i] = stk[pt].get(S[i]) + (lld)A*S[i]*S[i] + (lld)B*S[i] + C; LINE me({-2*A*S[i], (lld)A*S[i]*S[i]-(lld)B*S[i]+D[i]}); while (sz(stk) > 1 && ccw(stk[sz(stk)-2], stk.back(), me) >= 0) stk.pop_back(); pt = min(pt, sz(stk)-1); stk.push_back(me); } printf("%lld\n", D[N]); }

 

이 문제에서는 추가하는 일차함수의 기울기가 점점 커지고 교점을 찾는 $x$ 좌표가 점점 커지기 때문에 코딩하기 매우 편하다. 만약 교점을 찾는 $x$ 좌표가 경향이 없다면, 이분탐색을 통해 해결하면 된다. 만약 추가하는 일차함수의 기울기에 경향이 없다면, Li Chao Tree를 이용하여 해결할 수 있다. 이 경우 연습 문제로 ACM ICPC World Finals 2011 F번 문제(해법)가 있다.

 

* 교점을 찾는 $x$ 좌표에 경향이 없어서 이분 탐색이 필요한 경우 (BOJ 14240 부분 수열의 점수)

#include <bits/stdc++.h> using namespace std; #define MAXN 200005 #define sz(v) ((int)(v).size()) typedef long long lld; typedef __int128_t lll; int N; lld P[MAXN], S[MAXN]; lld D[MAXN]; struct LINE{ LINE(int n): a(-n), b(n*P[n]-S[n]) {} int a; lld b; lld get(lld x)const{ return a*x+b; } lll operator * (const LINE &ot)const{ return (lll)a*ot.b-(lll)ot.a*b; } }; lll ccw(const LINE &a, const LINE &b, const LINE &c){ return a*b + b*c + c*a; } int main() { scanf("%d", &N); for (int i=1;i<=N;i++){ int v; scanf("%d", &v); P[i] = P[i-1]+v; S[i] = S[i-1]+(lld)i*v; } lld ans = 0; vector<LINE> stk = {LINE(0)}; for (int i=1;i<=N;i++){ int s = 0, e = sz(stk)-2, t = sz(stk)-1; while (s <= e){ int m = s+e >> 1; if (stk[m].get(P[i]) <= stk[m+1].get(P[i])) s = m+1; else e = m-1, t = m; } D[i] = stk[t].get(P[i]) + S[i]; ans = max(ans, D[i]); LINE me(i); while (sz(stk) > 1 && ccw(stk[sz(stk)-2], stk.back(), me) <= 0) stk.pop_back(); stk.push_back(me); } printf("%lld\n", ans); }