SoundHound Programming Contest 2018 Masters Tournament 本戦: B - Neutralize

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

問題概要

N要素の数列Aが与えられる。Aの中から連続するK個の要素を選んでその値を全て0にするという操作を何度でも行えるとき、最終的なAの全要素の和の最大値を求めよ。

N <= 2×10⁵

-10⁹ <= Aの要素 <= 10⁹

解法

まず「連続するK個を選んで」は「連続するK個以上を選んで」と言い換えられる。一度K個連続で潰したあとひとつずらしてまた潰せば(K+1)個連続で0にできるからである。

また操作の順番は最終的な結果に影響を及ぼさないので、左の要素から順に操作を行うかどうか決めていってよい。もしその要素を残すのであれば合計にその要素の値を組み入れて次の要素へ進む、潰すのであれば合計はいじらずK個以上先の要素へスキップする、という感じ。

ここまでを踏まえるとDPできそうな感じになる。K個以上先へのスキップという遷移を愚直にやるとO(N²）かかるのでNGだが、「直前でスキップした結果今見ている要素にたどりついたのであれば、1つ飛ばしのスキップが可能」（さっきの潰した区間をさらに1伸ばすイメージ）という風にみなせば「残して1個進む」「K個スキップする」「直前でスキップしてるので今の要素をスキップして1個進む」の3種類の遷移だけ考えればよくなるので（インデックス、直前にスキップしたか）を状態にとるDPができてO(N)になる。

感想

DPにたどり着くまで時間がかかって全然解けなかったのでかなり焦った

遷移は変な工夫しないでも遅延セグ木とかでできそう　もらうDPなら普通のセグ木でもいける？

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;

immutable long INF = 1L << 59;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto K = s[1];
    auto A = N.iota.map!(_ => readln.chomp.to!long).array;
    auto B = new long[](N+1);
    foreach (i; 0..N) B[i+1] = B[i] + A[i];

    auto dp = new long[][](N+1, 2);
    foreach (i; 0..N+1) fill(dp[i], -INF);
    dp[0][0] = 0;

    foreach (i; 0..N) {
        dp[i+1][0] = max(dp[i+1][0], max(dp[i][0], dp[i][1]) + A[i]);
        dp[i+1][1] = max(dp[i+1][1], dp[i][1]);
        if (i+K <= N)
            dp[i+K][1] = max(dp[i+K][1], dp[i].reduce!max);
    }

    max(dp[N][0], dp[N][1], 0).writeln;
}