近年非常によく見る 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;
}

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

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

KUPC 2020 E - Sequence Partitioning

問題概要

制約

考えたこと

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

コード