問題概要：N個の薬品が並んでいる。各薬品の効用は-109 ~ 109。連続したK個の薬品の効用を0にする処理を任意回おこなったあとの薬品の効用の和の最大値を求める。
400点問題なのに2時間考えてまったくわかりませんでした。実行時間制限がなかったとしても解けてなかったと思います。sugim48さんの回答 ほぼそのまま参考にして本番後ACしたコードを最後に示します。また具体例をもとにアルゴリズムの動きを書き下した説明を以下に示します。
例としてK = 3で薬品が3 4 -8 2 -7 -5と並んだ場合を考えます。この解法では左側の薬品から順に部分配列を伸ばしていき、最後に増やした薬品を右端としたK個の薬品の効用を0にすべきかどうかを決めます。以下でその手順を見ていきましょう。
まず1個目を取り出して3。これではK個の薬品を取り出しようがないのでそのまま。この部分配列に対する答えは3。これをdp[1] = 3として記録します。
次に2個目を取り出して3 4。同様の理由でそのまま。この部分配列に対する答は7。これをdp[2] = 7として記録します。
次に3個目を取り出して3 4 -8。この部分配列に対する答は、「3 4 -8の3つの効用をゼロにするか、しないかのうち、良い方」です。今回はゼロにしたほうが得です。よってこの部分配列に対する答は0。これをdp[3] = 0として記録します。
次に4個目を取り出して3 4 -8 2。この部分配列に対する答は、「4 -8 2の3つの効用をゼロにするか、しないかのうち、良い方」です。4 -8 2の効用をゼロにしない場合は簡単で、dp[2]に2を足した値なので、2になります。4 -8 2の効用をゼロにする場合はちょっとややこしくて、4 -8 2だけでなくて4 -8 2のすぐ左側にある任意の数の薬品をもゼロにしてよい、と考えなければいけません。それを求めるにはこれまでのdpの値の最大値を記録する配列maを用意しておきます（詳細はコードを参照）。この場合は4 -8 2を0とするのがベストなので、3になります。2と3のうち良い方である3が答なので、dp[4] = 3として記録します。
次に5個目を取り出して3 4 -8 2 -7。この部分配列に対する答は、「-8 2 -7の3つの効用をゼロにするか、しないかのうち、良い方」です。上と同様の手順により、-8 2 -7をゼロにするのがベストなので、dp[5] = 7として記録します。
最後に6個目を取り出して3 4 -8 2 -7 -5。この部分配列に対する答は、「2 -7 -5の3つの効用をゼロにするか、しないかのうち、良い方」です。今回の場合は2 -7 -5の3つの効用をゼロにし、さらにその左側にある-8も巻き込んでゼロにするのがベストです。よってdp[6] = 7として記録します。
以上のアルゴリズムによるdp, maの値の変化を以下に示します。Bの値とdp, maの値との比較をしやすくするため、あえてdp, maの値は本来の位置よりひとつ左にずらしています。
| idx | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| B | 3 | 4 | -8 | 2 | -7 | -5 |
| dp | 3 | 7 | 0 | 3 | 7 | 7 |
| ma | 3 | 7 | 7 | 7 | 7 | 7 |
しつこく考えてなんとか理解できたつもりですが、本当に正しいか、また人が読んでわかる説明になっているかは自信ありません。
// 本番中は全く解けず // 0以下の数値がK以上連続して並ぶならそこはすべて0にできる、 // など考えていたが、何をしていいかわからなかった // // https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/submissions/2912994 // を参考に実装 // #include <algorithm> #include <cassert> #include <climits> #include <cmath> #include <cstdio> #include <cstring> #include <deque> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> using namespace std; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; #define REP(i,n) for(int i = 0; i < (int)(n); ++i) #define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i) #define ALL(c) (c).begin(), (c).end() #define SIZE(v) ((int)v.size()) #define pb push_back #define mp make_pair #define mt make_tuple int main(void) { cin.sync_with_stdio(false); int N, K; cin >> N >> K; vector<ll> Bs(N); REP(i, N) cin >> Bs[i]; // dp[i+1]: 配列の1番目からi番目までのサブ配列での答。 // ma[i+1]: dp[1] ~ dp[i+1]までの最大値。 // 気持ちとしては、 // 配列の1番目からi番目までのサブ配列において // サブ配列の右端から任意個の要素をゼロにできる、 // と条件を緩和したときの答になっている vector<ll> dp(N + 1); vector<ll> ma(N + 1); FOR(i, 1, N + 1) { dp[i] = dp[i - 1] + Bs[i - 1]; if (i >= K) { dp[i] = max(dp[i], ma[i - K]); } ma[i] = max(ma[i - 1], dp[i]); } cerr << "B : "; REP(i, N) cerr << Bs[i] << "\t"; cerr << endl; cerr << "dp: "; FOR(i, 1, N + 1) cerr << dp[i] << "\t"; cerr << endl; cerr << "ma: "; FOR(i, 1, N + 1) cerr << ma[i] << "\t"; cerr << endl; cout << dp[N] << endl; return 0; }
