宝箱 [第四回 アルゴリズム実技検定 O]

https://atcoder.jp/contests/past202010-open/tasks/past202010_o

前提知識

• 動的計画法
• SegTree

解説

https://atcoder.jp/contests/past202010-open/submissions/21475159

色々思案する必要がある問題であるが、必要な知識はセグメントツリーのみである。

どう取り組んでいくか

初見では取り組みにくい問題に見えると思う。
こういう区間が与えられるような問題で使えるテクとして、区間を右端でソートして、順次考えていくというものがある。
これは何かというと、区間を右端でソートして順次使っていくことによって、「ここまでの範囲までは状態が確定している」というのを
作り出す狙いがある。
よくわからないかもしれないが、使うDPを見ると何となく雰囲気が分かる。

DP定義

dp[R] := R番目までの宝箱の状態が確定しているときのY-Xの最大値
これを更新していくことを考えるとき、区間[L,R]をRが小さい順に処理することで、
とある区間[L,R]を処理した後はRがそれ以下のものはすべて処理されているので、それによる状況変化を考慮しなくてよくなる。

こうすると、[L,R]を使ってdpを更新すると、
dp[R] = max(dp[R], dp[L - 1] + (a[L] + a[L+1] + ... a[R]) - X)
という感じに更新していく感じになる。
区間の総和は累積和を使えばいいので問題にはならない。

遷移は十分だろうか？

実はこれで遷移は十分ではない。
鍵屋に依頼したときにその範囲に既に開錠済みの宝箱が含まれている可能性を考慮できていない。
これは以下のような遷移で実現する

dp[R] = max(  
    dp[R],  
    max(  
        dp[L] + (a[L + 1] + ... + a[R]),  
        dp[L + 1] + (a[L + 2] + ... + a[R]),  
        dp[L + 2] + (a[L + 3] + ... + a[R]),  
        ...  
        dp[R - 1] + a[R]  
    ) - X  
)  

途中までは開錠しているから、それ以降について開錠された金額をYとして採用するような感じである。
このmaxをうまく変形することで高速に扱えるようにする。
なお累積和を使うので以下の配列を導入する。
b[i] = a[0] + a[1] + ... + a[i]

dp[R] = max(  
    dp[R],  
    max(  
        dp[L] + (b[R] - b[L]),  
        dp[L + 1] + (b[R] - b[L + 1]),  
        dp[L + 2] + (b[R] - b[L + 2]),  
        ...  
        dp[R - 1] + (b[R] - b[R - 1])  
    ) - X  
)  

このように変形すると、b[R]は固定なので外に出すことができる。

dp[R] = max(  
    dp[R],  
    max(  
        dp[L] - b[L],  
        dp[L + 1] - b[L + 1],  
        dp[L + 2] - b[L + 2],  
        ...  
        dp[R - 1] - b[R - 1]  
    ) + b[R] - X  
)  

ここまでくると、dp[x]-b[x]について[L,R-1]の最大値を取ったものとして要求が固まるのでこれはセグメントツリーを使えば実現が可能になる。
これを使えばこちらの遷移も実現できるので最後にdp[N]を答えればAC

int N, M, A[201010];
SegTree<ll, 1 << 18> dp1, dp2;
ll B[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) cin >> A[i];
    rep(i, 1, N + 1) B[i] = B[i - 1] + A[i - 1];
    map<int, vector<pair<int, int>>> ranges;
    rep(i, 0, M) {
        int l, r, c; cin >> l >> r >> c;
        ranges[r].push_back({ l, c });
    }

    dp1.update(0, 0);
    rep(R, 1, N + 1) {
        dp1.update(R, max(dp1[R - 1], dp1[R]));
        fore(p, ranges[R]) {
            int L = p.first;
            int cst = p.second;
            ll tot = B[R] - B[L - 1];
            dp1.update(R, max(dp1[R], dp1.get(0, L) + tot - cst));
            dp1.update(R, max(dp1[R], dp2.get(L, R) + B[L - 1] + tot - cst));
        }
        dp2.update(R, dp1[R] - B[R]);
    }

    cout << dp1[N] << endl;
}