水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

SoundHound Programming Contest 2018 Masters Tournament 本戦 (Open):B - Neutralize

問題

beta.atcoder.jp

解法

問題を読むと DP という気持ちになるので,以下のように DP を定義する:

dp(i, f) := i 番目の要素まで見たときの最大値(f が true の時,効用を0にすることが可能で,f が false の時,効用を0に出来ない)

f を true にするとき,dp(i + K, true) とすればよい.f が true の間は無限に効用を0にすることが出来る(連続して選ぶ K 個の区間を1つずつずらしていくことと同じであるので).

解答

beta.atcoder.jp

最初から DP だとは分かったが,どこまで効用を0にするのが最適かを前処理で計算して無理やり DP 内で使おうとしたなどして 3 WA してしまった.素直に DP を書いてあげればすぐに通るはずだった.

f:id:babcs2035:20181028193456p:plain