SoundHound Programming Contest 2018 Masters Tournament 本戦 - B - Neutralize

https://atcoder.jp/contests/soundhound2018-summer-final/tasks/soundhound2018_summer_final_b

概要

長さNの数列{a}が与えられる。K<=NのKが与えられる。
あなたは次の操作を好きな回数だけ行うことができる。

• 連続するK項を選び、それらの値をすべて0にする。

この時数列{a}の和の最大値を求めよ。

制約：1 <= K <= N <= 2 * 10^5, -10^9 <= A[i] <= 10^9

考え方

1. K項を0にするを、適宜ずらすことでK項以上0にすることができる。
2. 貪欲の解法を考えると、いろんな反例が思いつく。(K個以上の負になる区間があったら見つけ次第操作していいかというとそうでもない　考察参照)
3. こういう問題は動的計画法に限る。
4. DPを考えると、O(N^2)になるが、これは適宜にメモをすることでO(N)まで落ちる->AC!

考察

貪欲的な解法として、前からor後ろから見て、K個の区間で初めて負になる区間から順に取りのぞく、というものがあると思われる。
しかし、これは以下のようなケースの時に反例となる。

-5, 2, 2, 3, -10, 10000, 10000, 10000
K=3

この時、最初のの{-5, 2, 2}は-1となり、次の3を加えると正になるので{-5, 2, 2}で0にするのが最適のように見えるが、実は{-5, 2, 2, 3, -10}を0にすると全体的に最善となる。

このように、一目で貪欲でできないと思われる問題は、全探索とその派生の動的計画法を考えるのが鉄則である。
これの全探索は明らかにO(N)に収まらないので、いい感じに動的計画法できないかを考える。
次のようにDPを定めてみる。

• dp[i] := 前からi個目(1-idx)の要素までの最大値。
• dp[0] = 0
• (i > 0) dp[i] = max(dp[i-1] + a[i], dp[0からi-K]までの最大値)

遷移の式の説明としては、数列のi個目の数字まで見た時の最適解は、次の2つから得られる。

• i-1個までの最適解+a[i-1](a[]の添え字は0-idxとする)

これは今見てる数字a[i-1]を0にせずにそのまま足すという操作に相当する。

• 0~i-Kまでの最適解の最大値　

今のある数字を0にする。そのため今の見てる数字を末尾として含んだ連続したK個の数字は全部0でなければならない。そのため数列のi-K個目まで見た結果と同じである。(今見てる数字を末尾とした連続したK個はすべて0にするので、答えには寄与しない)

このとき、愚直に「0~i-Kまでの最適解の最大値」を求めると遷移ごとにになるが、これは簡単なメモ操作でで求まる。具体的には、dpを計算しながら、別の配列を用意して今までのdpのうちの最大値、というのを実装すればよい。(自分のコードではdpmaxである)

自分のソースコード：
Submission #15873371 - SoundHound Programming Contest 2018 Masters Tournament 本戦

dp[0] = 0;
for (int i = 1; i <= N; i++) {
	if (i - K >= 0) {
		//最初のK項
		dp[i] = max(dp[i - 1] + n[i - 1], dpmax[i - K]);
	}
	else {
		dp[i] = dp[i - 1] + n[i - 1];
	}
	dpmax[i] = max(dpmax[i - 1], dp[i]);
}
cout << dp[N] << endl;

一言

典型を取りこぼした。定期的に見回って落とさんようにするぞするぞ。

Special Thanks

http://baitop.hatenadiary.jp/entry/2018/07/29/204143
このサイト様を大いに参考にしました。