볼록 껍질을 이용한 최적화 (Convex Hull Trick)

https://atcoder.jp/contests/abc228/editorial/2960

 

 

볼록 껍질을 이용한 최적화, 혹은 컨벡스 헐 트릭(CHT)은 위 그림처럼 여러 직선이 주어져 있을 때, 직선이 이루는 볼록 껍질을 구하여 x에 따른 최솟값을 구하는 최적화 기법이다. 따라서 평소라면 $O(n)$이 걸릴 최솟값 문제를, x가 속한 구간만 이분 탐색으로 찾으면 되므로 $O(\log n)$에 해결할 수 있게 된다. cht는 dp가 아니어도 충분히 사용될 수 있지만 dp의 최적화 기법으로도 자주 사용되기에 dp 카테고리에 작성하였다. cht를 적용하려면 다음과 같은 조건이 필요하다.

 

• 일차 함수 관계이거나, 일차 함수 형태로 변형 가능한 문제여야 한다.
• 직선들이 볼록 껍질을 구성해야 하므로, 그 기울기가 단조 증가 혹은 감소해야 한다. (ex. 양수로 구성된 배열의 누적합)

 

컨베이어 벨트 (BOJ 2821)

dp에 적용하지 않는 문제를 먼저 보자. 약간의 관찰로 병목이 일어나는 구간에 주목해야겠다는 생각을 해볼 수 있고, 결과적으로 다음과 같은 식을 얻는다. 여기에 마지막 자동차가 만들어지는 시간만 더하면 정답이 된다.

 

$$\sum_j \max_i (T[i]F[j] - T[i-1]F[j+1] )$$

($T[i]$: 작업 시간의 누적 합)

 

이를 나이브하게 구현하면 $O(n^2)$이므로 제한을 통과하지 못한다. 따라서 안쪽의 최댓값을 구하는 문제를 cht로 해결한다. F[j+1]을 묶어내면, 기울기가 T[i], 절편이 -T[i-1]이고 x좌표 값이 F[j]/F[j-1]인 일차함수 형태로 변형할 수 있다. T[i]는 작업 시간의 누적 합으로 단조 증가하므로, cht를 적용할 수 있다.

 

구현은 볼록 껍질의 원리를 알고 있다면 크게 어렵지 않다. 껍질을 구성하는 각 직선들을 모은 뒤, 교점의 x좌표를 미리 계산해 두고 x좌표가 들어오면 이분 탐색하여 어떤 직선을 선택해 계산하면 되는지 정해 주면 된다. 지금은 기하학 문제를 다루는 것은 아니고, 문제의 숫자들도 정수로 들어오기 때문에 교점의 x좌표는 단순 나눗셈으로 구해 주면 된다.

inter_x = lambda l1,l2: (l1[1]-l2[1])/(l2[0]-l1[0])
hull = []
for l in lines:
    while len(hull) >= 2 and inter_x(hull[-2], hull[-1]) >= inter_x(hull[-2], l):
        hull.pop()
    hull.append(l)

inter_x_list = []
for i in range(len(hull)-1):
    inter_x_list.append(inter_x(hull[i], hull[i+1]))

res = 0
for j in range(M-1):
    x = F[j] / F[j+1]
    idx = bisect(inter_x_list, x)
    max_l = hull[idx]
    res += max_l[0]*F[j] + max_l[1]*F[j+1]

 

 

나무 자르기 (BOJ 13263)

개인적으로 이 문제는 dp 점화식을 떠올리는 것이 더 힘들었다. 모든 나무를 다 베어야 하므로, 중간에 작은 번호의 나무로 되돌아갈 수도 있지 않을까 고민했었는데, $b_n$이 0이라는 것이 핵심이다. 즉 n번째 나무를 완전히 베는 순간부터는 cost가 전혀 들지 않으므로, n번째 나무로 최소한의 비용으로 도달하는 것을 목표로 문제를 변형할 수 있다. 따라서 dp[i]=(i번째 나무를 완전히 베기 직전까지의 비용)으로 놓고 dp를 돌릴 수 있다. 다음과 같은 (굉장히 표준적인) 식을 얻는다.

 

$$ dp[i] = \min_{1 \leq j < i} (dp[j] + a[i]b[j])$$

 

b[j]를 기울기, dp[j]를 절편, a[i]를 x좌표로 놓고 cht를 적용하면 되겠다. 이번에는 a[i]가 단조 증가하기 때문에, 굳이 이분 탐색할 필요 없이 (현재 a[i]가 속한 구간의 직선)의 인덱스만 차례로 증가시켜 주면 $O(n)$만에 해결할 수 있다.

inter_x = lambda l1, l2: (l2[1] - l1[1]) / (l1[0] - l2[0])
dp = [float('inf')]*N
dp[0] = 0
hull = [(b[0], 0)]
now = 0
for i in range(1, N):
    while now+1 < len(hull) and inter_x(hull[now], hull[now+1]) <= a[i]: now += 1
    best_line = hull[now]
    dp[i] = a[i]*best_line[0] + best_line[1]

    line = (b[i], dp[i])
    while len(hull) >= 2 and inter_x(hull[-2], hull[-1]) >= inter_x(hull[-2], line):
        if now == len(hull): now -= 1
        hull.pop()
    hull.append(line)

print(dp[N-1])