Neutralize [SoundHound Programming Contest 2018 Masters Tournament 本戦 B]

https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/tasks/soundhound2018_summer_final_b

前提知識

• セグメントツリーによるDP高速化

考察過程

1. 動的計画法で解く流れで考える
2. 消せる区間の特性を考えてみると、長さK以上なら自由に伸ばせることが分かる
3. dpを考えると「dp[i] := i番目まで確定させたときの最適解」しか無理そう
4. 2と3から、なんとなく漸化式を立ててみると、dp[i]としてdp[i-K], dp[i-K-1], dp[i-K-2], ...が採用できることが分かる。長さKで消した、長さK+1で消した、長さK+2で消した場合である。
5. なんとなく更新式を考えてみて、やってみるとサンプルが通るO(N^2)
6. これはセグメントツリーで高速化できるので、やって投げるとAC

解法

https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/submissions/2915353

動的計画法で解く。
dp[i] := i番目まで確定しているときの最大総和
dp[i]まで確定している時にdp[i+1]を確定していきたい。
選択肢としては、2つある。
「i+1番目をそのまま採用する」dp[i+1] = dp[i] + B[i]
「i+1番目を右端として区間を0にする操作をする」dp[i+1]=dp[i-len] （lenは0代入する区間の長さ）
二番目の選択肢はlenがK以上の取りうる値を探すので、O(N)かかる。
これを実装したO(N^2)が以下のようになる。

ll dp[201010];
dp[0] = 0;
    rep(i, 0, N) {
        dp[i + 1] = dp[i] + B[i];
        rep(j, 0, i - K + 2) chmax(dp[i + 1], dp[j]);
    }

　
DP配列を区間minのセグメントツリーに変えておけば、二番目の選択肢を高速化できる。
上のコードの[0,i-K+2)の区間minをセグメントツリーでかいけつするというだけ。

int N, K, B[201010];
//ll dp[201010];
SegTree<ll, 1 << 18> dp;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> B[i];
 
    /*dp[0] = 0;
    rep(i, 0, N) {
        dp[i + 1] = dp[i] + B[i];
        rep(j, 0, i - K + 2) chmax(dp[i + 1], dp[j]);
    }*/
 
    dp.update(0, 0);
    rep(i, 0, N) {
        ll res = dp[i] + B[i];
        chmax(res, dp.get(0, i - K + 2));
        dp.update(i + 1, res);
    }
 
    cout << dp[N] << endl;
}