けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

SoundHound 2018 本戦 B - Neutralize (400 点)

操作:上書き 操作 DP ナップサックDP AtCoder unrated公式コン AtCoder400点 操作後の結果の最適化問題 数列 操作:区間 最大スコア 区間 最適化問題

本番では回避したん。こういうのをサッサササッとバババババーンと解けるようになりたい。

問題へのリンク

問題概要

N 個の数列 a_{0}, a_{1}, \dots, a_{N-1} が与えられる。以下の操作を好きな回数だけ行って得られる数列の総和を最大化せよ。

  • 連続する K 個の区間の数列を一斉に 0 にする

制約

  • 1 \le K \le N \le N

考えたこと

基本的に負の数をなるべく 0 にして行きたい。

途中どんな操作を行おうとも、最後の何回かの操作が支配的になるタイプの操作。ゆえに区間が重なるように操作をすれば、「長さが K 以上となる区間を 0 にする」という操作も行えると考えてよい。

  • 負の数の区間が K 以上なら、そこをまとめて 0 にすればよさそう
  • 負の数の区間が短いとちょっと面倒

なんかうまく Greedy にやるの難しそうなので DP を考えてみる。

  • dp[ i ][ (最初が 0 かどうか) ] := i 番目以降についての操作による最大値 (先頭が 0 かどうかで場合分け)

という風にすればよさそう。

chmax(dp[ i ][ 0 ], dp[ i + 1 ][ 0 ] + a[ i ])
chmax(dp[ i ][ 1 ], dp[ i + K ][ 0 ])
chmax(dp[ i ][ 1 ], dp[ i + 1 ][ 1 ])
chmax(dp[ i ][ 0 ], dp[ i + 1 ][ 1 ] + a[ i ])

という感じ。

#include <iostream>
#include <vector>
using namespace std;

template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }

int N, K;
vector<long long> b;
long long dp[210000][2];
const long long INF = 1LL<<60;

int main() {
  cin >> N >> K;
  b.resize(N); for (int i = 0; i < N; ++i) cin >> b[i];
  for (int i = 0; i < 210000; ++i) dp[i][0] = dp[i][1] = -INF;
  dp[N][0] = 0;
  for (int i = N-1; i >= 0; --i) {
    chmax(dp[i][0], dp[i+1][0] + b[i]);
    if (i+K <= N) chmax(dp[i][1], dp[i+K][0]);
    chmax(dp[i][1], dp[i+1][1]);
    chmax(dp[i][0], dp[i+1][1] + b[i]);
  }
  cout << max(dp[0][0], dp[0][1]) << endl;
}