けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

KUPC 2020 E - Sequence Partitioning

近年非常によく見る DP 高速化系問題!!

問題概要

長さ  N の 3 つの数列  A, B, C が与えられる。

いま、数列  A をいくつかの連続する部分列に分割することを考える。 分割  D に対して、スコアを、各区間についての以下の値の最小値として定める。

  • その区間の  A の総和と、区間の先頭の  B の値と、区間の末尾の  C の値の総和

制約

  •  1 \le N \le 2 \times 10^{5}

考えたこと

「最小値の最大化」なので、二分探索が有効そう。というわけで、「区間全体のスコアを  x 以上にできるか」という判定問題を解くことを考える。

とりあえず、区間  \lbrack i, j) のスコアを  f(i, j) として、次のような DP が組める。

  •  {\rm dp}\lbrack i \rbrack = 最初の  i 個の要素について、適切に区間分割することで、各区間のスコアを  x 以上にできるかどうかのブール値

とする。DP 遷移は次のようにできる。

 {\rm dp}\lbrack i \rbrack |=  {\rm dp}\lbrack j \rbrack ( j \lt i かつ  f(j, i) \ge x に限り)

これを愚直にやると  O(N^{2}) の計算量となるので高速化する。

スコア f(i, j) を上手に

数列  A の累積和を  S とすると、

 f(j, i) = (S_{i} + C_{i-1}) + (B_{j} - S_{j})

となる。DP 遷移においては  {\rm dp}\lbrack j \rbrack = true となるような  j だけを考えたい。よって

  •  g(j) =  0 ( {\rm dp}\lbrack j \rbrack = true)、 -∞ ( {\rm dp}\lbrack j \rbrack = false)

として、

 f'(j, i) = (S_{i} + C_{i-1}) + (B_{j} - S_{j} + g(j))

が最大となるような  j を求めてあげれば、DP 遷移ができそう。つまり

  •  \max_{j= 0, \dots, i-1} f'(j, i) \ge x ならば  {\rm dp}\lbrack i \rbrack = true
  • それ以外は  {\rm dp}\lbrack i \rbrack = false

と判定できる。適宜累積和を用いれば  O(N) でできる。二分探索も含めて、計算量は  O(N \log V) (登場する値の最大値を  V とする)。

コード

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    int N;
    cin >> N;
    vector<long long> A(N), B(N), C(N), S(N+1, 0);
    for (int i = 0; i < N; ++i) cin >> A[i], S[i+1] = S[i] + A[i];
    for (int i = 0; i < N; ++i) cin >> B[i];
    for (int i = 0; i < N; ++i) cin >> C[i];

    const long long INF = 1LL<<60;
    auto check = [&](long long x) -> bool {
        vector<bool> dp(N+1, false);
        dp[0] = true;
        vector<long long> ms(N+1, -INF);
        ms[1] = B[0] - S[0];
        for (int i = 1; i <= N; ++i) {
            if (ms[i] + S[i] + C[i-1] >= x) dp[i] = true;
            if (i == N) break;
            long long score = B[i] - S[i];
            if (!dp[i]) score -= INF;
            ms[i+1] = max(ms[i], score);
        }
        return dp[N];
    };

    long long left = -INF, right = INF;
    while (right - left > 1) {
        long long x = (left + right) / 2;
        if (check(x)) left = x;
        else right = x;
    }
    cout << left << endl;
}