[ABC353] G - Merchant Takahashi

[Q] G - Merchant Takahashi

2年に1回くらい見かけるConvex Hull Trick。拾えてうれしい。

考察
0. DP[index][今いる町] = 最大益
のDP[N][N]テーブルを使えば、答えはDP[N-1][0 ~ N-1]の最大値で求まる。
ところがO(N^2)でTLEしてしまう。どうにか高速化する必要がある。

1. 初期値を考える。
   まず町0にいるとしてDP[0] = 0でよい。町1 ~ Nまで無理やり移動すると、
   DP[1] = DP[0] - C
   DP[2] = DP[0] - 2C
   DP[3] = DP[0] - 3C…
   という損益が考えられる。コストだけかかって無駄に移動した状態。

2. 次に、町2に行くと利益P得られるとする。
   DP[2] = DP[0] -2C + P
   
   さて、町2から無理やり町0~Nまで無理やり移動したと考えると、
   DP[0] = max(DP[0], DP[2] - 2C)
   DP[1] = max(DP[1], DP[2] - C)
   DP[2] = DP[2] - 2C + P
   DP[3] = max(DP[3], DP[2] - C)…
   といった遷移が考えられる。
   DP[2]からほかの町への遷移コストは、cost = ax + bの一次式で表せる。
   Convex Hull Trickが使えそう。

3. 与えられたT, Pの情報は都度処理することを考える。
   Convex Hull Trickでquery()すれば、O(loglogN)で都度DP[T]のmaxが求まる。
   新たに
   y = Cx + b: [0 ~ T)
   y = -Cx + b: [T ~ N)
   の2辺情報を追加していけばいい。

4. 入力例1を考える

N=6 C=3 M=4

最初の状態は
DP[0] = 0
DP[1] = -3
DP[2] = -6
DP[3] = -9
DP[4] = -12
DP[5] = -15
これは
y = -3x + 0: [0, 6)
の一次式で表せる。

M1: T=4, P=30の移動を行う。
DP[0] = 6  // DP[4] - 12
DP[1] = 9  // DP[4] - 9
DP[2] = 12 // DP[4] - 6
DP[3] = 15 // DP[4] - 3
DP[4] = 18 // +30
DP[5] = 15 // DP[4] - 3
これは
y = -3x + 6: [0, 5)
y = 3x + 30: [4, 6)
の2つの一次式で表せる。

M2: T=1 P=10
DP[0] = 16 // DP[1] - 3
DP[1] = 19 // +10
DP[2] = 16 // DP[1] - 3
DP[3] = 15 // DP[1] - 3よりもDP[3]のほうが大きい
DP[4] = 18 // DP[1] - 6よりもDP[4]のほうが大きい
DP[5] = 15 // DP[1] - 9よりもDP[5]のほうが大きい
これは
y = 3x + 16: [0, 2)
y = -3x + 22: [1, 6)
の2つの一次式で表せる。

DP[0] = 31
DP[1] = 34
DP[2] = 37
DP[3] = 40
DP[4] = 37
DP[5] = 34

DP[0] = 46
DP[1] = 49
DP[2] = 46
DP[3] = 43
DP[4] = 40
DP[5] = 37
答えはDP[1] = 49

Q. Convex Hull Trickって線分の条件も与えられるの？
A. できる。線分の Convex Hull Trick でググる。こちらをコピペしてAC。

実装

int main() {
  cincout();
  
  ll N, C, M;
  cin >> N >> C >> M;
  CHT<ll> cht(0, N); // query()ではminが得られる。今回maxが欲しいので、+-反転させる。
  
  cht.add_segment(C, 0, 0, N); // -CではなくC。コストがかかるほどプラスに傾けるとする。
  rep(i, M){
    ll T, P;
    cin >> T >> P;
    --T;
    ll r = cht.query(T) - P; // 利益Pが得られるほどマイナスにする。
    cht.add_segment(-C, r + C * T, 0, T + 1); // 0~Tまでの線分
    cht.add_segment(C, r - C * T, T, N); // T~Nまでの線分
  }
  ll ans = oo;
  rep(i, N){
    chmin(ans, cht.query(i));
  }
  cout << -ans << endl;
}

https://atcoder.jp/contests/abc353/submissions/53373407