Batch Scheduling

• 지문이 영어인데다가 잘 안읽힌다..
• 배치별로 나누면 같은 배치안에서는 똑같은 O값을 갖게 된다. 따라서 i…j 를 배치로 묶으면 그 배치안의 잡들의 코스트의 합은 그냥 Oi*(Fi+…+Fj) 가 된다.
• 그러면 이제 대충 DP 형태로 점화식을 세울수 있을것 같은 느낌이 든다.
• DP[i]를 i까지의 잡을 처리하는데에 드는 최소 코스트라고 하면, dp[i] = {j까지의 잡을 처리하는데 든 코스트} + {j번부터 i까지를 묶은 배치의 코스트} 형태로 표현이 될거 같다.
• DP[i] = min_{j<i}(DP[j-1] + O[i]*(F[j]+…+F[i])) 이런식인데.. (F[j]+…+F[i])는 누적합을 이용해서 간단히 구한다 쳐도, O[i]가 문제이다. T[0]+T[1]+…+T[i] 에다가 {배치의 갯수}*S를 해줘야 O[i]가 나오는데.. 이러면 배치의 갯수를 따로 저장하고 있어야 한다.
  • j번부터 i까지를 배치로 묶을때, dp[j-1]가 최소인 경우가 유리할수도 있고 j-1까지를 묶을 배치의 수가 적은것이 더 유리할수도 있기 때문에 배치의 수에 따른 최소 코스트를 모두 킵하고 있어야 한다.. 결국 DP테이블이 DP[i][s] 이런식의 2차원 DP가 된다..
• 하지만 이것을 역방향으로 DP식을 정리하는 방법을 생각해볼수 있다.
• DP[i]를 0~i번 까지가 한개의 배치로 묶일때의 0~N-1까지를 전부 처리하는 최소 코스트라고 생각하자. 즉 배치를 나누는 구분이 i번 이후에만 존재하는 경우이다. 원래는 0~j까지가 한개의 배치로 묶였을때의 최솟값이 DP[j]였을텐데, DP[i]는 이 값에서 0~j를 0~i와 i+1~j 의 두개의 배치로 나눈 경우이다. DP[i]가 DP[j]에 비해서 어떻게 값이 변동되는지 생각해보자. 일단.. i+1번 이후의 잡에 대한 O 값은 전부 S씩 늘어난다. 그래서 S*(F[i+1]+…+F[N-1]) 가 총 코스트에 추가된다. 대신 0~i까지의 잡의 O값은 T[i+1]+…+T[j]만큼이 줄어든다. DP[j]에서는 i까지의 코스트가 (F[0]+…+F[i])*(T[0]+…+T[j])로 계산되었는데 i에서 배치를 나누면 (F[0]+…+F[i])*(T[0]+…+T[i])로 계산할수 있다.
• 그럼 이제 식을 정리해보자. ST[x] = T[0]+..+T[x], SF[x] = F[0]+..+F[x] 로 누적합을 써서 표현하자.
  • DP[i] = min_{j>i} {DP[j] + S*(SF[N-1] - SF[i]) + SF[i]*(ST[i] - ST[j])} 로 1차원 형태로 깔끔하게 표현된다!
• 자 그리고 이제, i에 관한 텀을 기준으로 식을 다시 정리해보면
  • DP[i] = min_{j>i} {-ST[j]*SF[i] + DP[j] + S*(SF[N-1]-SF[i])+SF[i]*ST[i]} 형태이므로 볼록 껍질을 이용한 최적화를 이용해서 빠르게 계산할 수 있다. -ST[j]는 단조감소, SF[i]는 단조증가하므로 O(n)에 계산이 가능하다
• 이제 식이고 최적화 방법이고 다 나왔으니 그대로 구현만 하면 되기는 하는데.. 구현할때 실수할 여지가 많기는 하다. 일단 위의 식은 DP[n-1]에서 출발해서 DP[n-2],dp[n-3],…을 채워나가는 식인데, 식이 꼬이기 쉽다. 그리고 teflib의 convexhulltrick.dp_with_cht 함수에 그냥 넣을수도 없다. DP'[i]= DP[N-1-i] 이런식으로 테이블을 다시 정의하고 0에서부터 출발해서 채우도록 바꾸는게 차라리 쉬웠다
  • ST[0]=0, ST[x] = T[0]+…+T[x-1] 로 정의를 살짝 바꾸고 식을 다시 쓰면 아래처럼 된다. (SF도 마찬가지)
  • DP'[0] = ST[N]*SF[N]
  • DP'[i] = min_{j<i} {-ST[N-j]*SF[N-i] + DP'[j] + S*(SF[N-1]-SF[N-i])+SF[N-i]*ST[N-i]}
• 휴.. 이제 그냥 드디어 함수에 넣고 돌리면 된다.
• 이렇게 해서 돌리면 겨우 80ms 정도만에 통과된다. 볼록 껍질을 이용한 최적화관련 문제들 중에서는 너무나도 빠르게 통과되는데, 옛날 문제라서 N값이 겨우 10000 이하로 주어지기 때문이다. (요즘 나오는 문제들은 N의 최댓값이 보통 100,000 이상이다.) 그래서 cpp로 돌리면 CHT를 사용하지 않는 O(n^2) 솔루션도 통과된다는듯 하다. 난이도가 플래티넘3 밖에 안되는 것은 이런 이유인듯

"""Solution code for "BOJ 5498. Batch Scheduling".

- Problem link: https://www.acmicpc.net/problem/5498
- Solution link: http://www.teferi.net/ps/problems/boj/5498

Tags: [DP] [CHT]
"""

import sys
from teflib import convexhulltrick


def main():
    N = int(sys.stdin.readline())
    S = int(sys.stdin.readline())
    T_and_F = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]

    f_sum = [v := 0] + [v := v + f for t, f in T_and_F]
    t_sum = [v := 0] + [v := v + t for t, f in T_and_F]
    c = f_sum[-1] * S
    dp = [None] * (N + 1)
    dp[0] = t_sum[-1] * f_sum[-1]
    dp = convexhulltrick.dp_with_cht(
        cht=convexhulltrick.ConvexHullTrickForIncreasingQueries(),
        dp=dp,
        f_j=lambda j: t_sum[N - j],
        f_i=lambda i: -f_sum[N - i],
        g_j=lambda j: dp[j],
        g_i=lambda i: f_sum[N - i] * (t_sum[N - i] - S) + c,
    )
    print(dp[-1])


if __name__ == '__main__':
    main()

• Dependency:
  • teflib.convexhulltrick.dp_with_cht
  • teflib.convexhulltrick.ConvexHullTrickForIncreasingQueries