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

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

AtCoder AGC 008 B - Contiguous Repainting (青色, 400 点)

操作を逆順に見るとよいという、すごく良い例題!大好き!!!

問題へのリンク

問題概要

 N 要素からなる数列  a_1, a_2, \dots, a_N が与えられる。今、以下の操作を好きな回数だけ行う。

  • 長さが  K の区間を選んで、区間全体を白く塗るか、黒く塗る

操作を行った後に黒く塗られたマスの値の総和がスコアになる。スコアの最大値を求めよ。

制約

  •  1 \le K \le N \le 10^{5}

上書き操作について言えること

「操作を好きな回数だけ行ってできるもののうち〜〜〜〜〜」な問題では、まずは操作によってどんなものができるのか、それをわかりやすく言い換えることが肝になる。

その流れは何点問題であっても変わらない。高難易度になったら、その部分の考察が難しくなるのみ。

さて、今回の操作の特徴として「上書き操作である」ということが挙げられる。これ以外にも例えば「binary 列に対して True との OR をとる」のような操作も上書き操作になる。

このような上書き操作ではしばしば、

  • 操作列を後ろから考えると性質が見えやすい

という傾向にある。なぜなら後ろから考えれば

  • 一度操作を行った箇所は二度と変更されない

という風に考えることができる。

この問題の場合

この問題にその考察を当てはめてみる。そうすると出来上がるものは


  1.  N マスのうち、ある連続する  K マスについてはすべて「黒」かすべて「白」で塗られていなければならない

  2. それ以外のマスについては何色でもよい


ということがわかる。なぜなら、まず最初の一発目にやった操作は絶対にうわ書きできないので、1 番目の条件は必須である。2 番目の条件については、

  • 最初の一発目は K マス選んで「黒」か「白」に塗る。
  • それ以外のマスは、既に塗られている区間から 1 マスだけはみ出す形で「黒」か「白」に順に塗っていく

とすれば実現できる。以上より、操作列によって出来上がるものをわかりやすく言い換えることに成功した。

最後の詰め

それぞれの連続する長さ  K の区間について「黒」「白」に塗った場合の最大スコアを求めれば良い。

連続  K マス以外のついては、単純に

  • 0 以上なら黒く塗る
  • 負なら白く塗る

でよい。また各場合について高速にスコアを求めるために、予め

  • 単純な累積和
  • 0 以上の部分だけ足す場合の累積和

を求めておくと良い。

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

int main() {
    int N, K; cin >> N >> K;
    vector<long long> a(N), S1(N+1, 0), S2(N+1, 0);
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
        S1[i+1] = S1[i] + a[i];
        S2[i+1] = S2[i] + (a[i] >= 0 ? a[i] : 0);
    }
    long long res = -(1LL<<60);
    for (int i = 0; i + K <= N; ++i) {
        int left = i, right = i + K;
        long long tmp = (S2[left] - S2[0]) + max(0LL, S1[right] - S1[left]) + (S2[N] - S2[right]);
        res = max(res, tmp);
    }
    cout << res << endl;
}