ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

SoundHound Programming Contest 2018 Masters Tournament 本戦 B - Neutralize

問題
提出コード
ある区間を0にしつつ、うまいこと累積和を計算していきます。
今回は、DPを使って考えました。
i+1 ~ i+Kが0の区間だった場合、i+1~i+Kは無視してよく、i+Kに、iまでの累積和が存在することと同じになります。
ということで、今iについてみているとき、i+Kも平行してみてあげることで、O(N)で計算をすることができるようになります。
dp[i] = 最初からi番目までの、和の最大値
とすると、答えはdp[N]です。
まずは、i+Kを同時に見るために、1 ~ Kの部分について、仮の累積和を先に記録しておきます。
そして、1~Kが0だった場合も考慮しなければならないので、K番目の部分には、先ほどの累積和と、0のうち大きな値を記録しておきます。
次に、2つ平行してDPを行っていきます。

  • dp[i] = max(dp[i],dp[i-1] + b[i])
    これは、i番目が、0の区間の対象外であったパターンです。i-1番目まではすでに決まっているので、素直にb[i]を足します。その後、もともとあった値と比較して、大きい方を記録します。

  • dp[i+K] = max(dp[i+K],dp[i])
    これは、i+1番目からi+K番目までが0であったパターンです。
    この上の処理を終えた時点でdp[i]が確定するので、この作業が行えます。

  • dp[i+K+1] = max(dp[i+K+1],dp[i+k])
    これは、K+1個以上0が続くパターンについて考慮するものです。
    i+K+xとしてxについて探索しなくて済むのは、1つ先だけ見ておくことで、2つ以上先のパターンは、i+1の場合のこの式が考慮してくれるからです。

ということで、この式をもとにDPを実行すれば、答えが求まります。