SoundHound Programming Contest 2018 Masters Tournament 本戦 (Open):B - Neutralize
問題
解法
問題を読むと DP という気持ちになるので,以下のように DP を定義する:
dp(i, f) := i 番目の要素まで見たときの最大値(f が true の時,効用を0にすることが可能で,f が false の時,効用を0に出来ない)
f を true にするとき,dp(i + K, true) とすればよい.f が true の間は無限に効用を0にすることが出来る(連続して選ぶ K 個の区間を1つずつずらしていくことと同じであるので).
解答
最初から DP だとは分かったが,どこまで効用を0にするのが最適かを前処理で計算して無理やり DP 内で使おうとしたなどして 3 WA してしまった.素直に DP を書いてあげればすぐに通るはずだった.