Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

SoundHound 2018 Masters 本戦-B 「Neutralize」 (400)

B 「Neutralize」 (400)

なんか悔しい。

問題リンク

概要

 N個の要素からなる数列 bがある。これに以下の操作を好きなだけ行う。

  • 連続した K個を選び、それらをすべて0にする。

この操作を行った後の、数列の総和の最大値を求めよ。

制約

  •  1 \leq K \leq N \leq 2 \times 10^5
  •  - 10^9 \leq b_i \leq 10^9

解説

まず考えたのが貪欲法で、「 [i, i + K) の総和が負なら操作を適用する」を i = 1 \sim Nまで実行するというもの。 実行自体はBITを使えば計算量 O(N \log N) でできるのだが、残念ながらこれは嘘解法。 具体的には、 N = 4, K = 3 (-4, 1, 5, -9) のような場合に最初の要素を消すことができない。

ここで諦めて解説を見た。editorialはちょっとよく分からなかったが、人々のブログがとても分かりやすかった。以降その解説。


一部が既に操作済みの領域に対して操作を行えることを考えると、この操作は実質「連続した K以上の要素を選び、それら全てを0にする」とみなして問題ない。

そしてこの問題の主軸となる解法はDPである。具体的には

  •  dp_i = (b_1, \dots, b_i) の場合の最適解

という値を更新していくことを考える。なお1-indexedで便宜上 dp_0 = 0とする。

 (b_1, \dots, b_{i - 1}) b_iを追加するとき、大きく以下の2つの場合に分けられる。

  •  b_iを消さずにそのまま追加する。
  •  b_iを末尾とする、連続した K個以上の要素を消す。

それぞれの場合の総和を考えてみる。

前者は b_iを追加するだけなので dp_{i - 1} + b_i

後者は連続する K + j個の要素を消した場合の総和が dp_{i - K - j}。これを j \geq 0について全て考えるので、 max(dp_0, \dots, dp_{i - K})

あとはこれに従って dpを更新していけばいいのだが、愚直にやると後者の最大値を求めるのに計算量 O(N) かかってしまい、全体の計算量は O(N^2) となってしまう。これの対策として考えうる方針は主に2つある。

  1. BITで区間最大クエリを O(\log N) で処理する。
  2.  ma_i = max(dp_0, \dots, dp_i) なる配列を同時に更新する。

以下の実装例では、後者の方針に従っている。

実装例

#include <iostream>
using namespace std;
using ll = long long;

int main() {
    ll N, K;
    cin >> N >> K;
    ll b[N + 1];
    for (int i = 1; i <= N; ++i) {
        cin >> b[i];
    }

    ll dp[N + 1], ma[N + 1];
    dp[0] = ma[0] = 0;
    // dp[i] = 1 ~ iにおける最適解
    // ただしdp[0] = 0
    // ma[i] = max(dp[0], ... ,dp[i])

    for (int i = 1; i <= N; ++i) {
        // そのまま追加した場合
        dp[i] = dp[i - 1] + b[i];

        // b[i]を消したい場合
        if (i >= K) dp[i] = max(dp[i], ma[i - K]);

        // maの更新
        ma[i] = max(ma[i - 1], dp[i]);
    }

    cout << dp[N] << endl;
    return 0;
}

感想

  • 困ったらDP。
  • もっと粘ってれば解けたかというと、五分五分という印象。
  • 色々なDPのパターンをこなしていきたい。