xxxasdfghjk999のブログ

iroiro

SoundHound Programming Contest 2018 Masters Tournament 本線 B - Neutralize

問題

解法

貪欲ができないか考えます.
ある薬品 $K$ を0にしたいときはK個を巻き込む必要があります. また, $K$ 個以上の区間を0にしたいときはこれを繰り返すことで実現することができます.
しかし, サンプルケースを見てみるとこれは厳しそうであることがわかります.
最適解が貪欲に求まりそうにないので, 最適解を仮定してDPをすることになります.
DPをするにあたって必要な保持状態は、まず

見ている薬の番号(1からN)

が必要です. 他に必要なものは,

見ているインデックスを右端としてK個選び, ０にしたかどうか(True or False)

です.
この２つを規定すると,
$dp[i][j] := (i番目までの薬品においての問題の最大値(j==0のとき右端から0にしている.))$

基底

$dp[0][0] = 0$
$dp[0][1] = 0$

帰納

$dp[i+1][0] =\max_{0 \leq j \leq i-K+1 , \space 0 \leq p \leq 1} dp[j][p]$
$dp[i+1][1] = \max ( dp[i][0] + b[i] , dp[i][1] + b[i] )$

帰納の上の式は, 右側から $K$ 個0にする必要があるために添字がK個小さいものまででの最大値に遷移します. ものものしい式となっており, いちいちこの最大値を探査していると時間が足りません. よって, dpを更新するたびに配列maxを用意しておき, 最大値を更新しておくと, 高速に計算することができます.
また, $i-K+1$ が0より小さいとき, $dp[i+1][0]$ は, 定義できません. このときは, maxに影響しないようにとても小さな数を入れておきます.
計算量は $O(N)$ です.

提出

Submission #3067414 - SoundHound Programming Contest 2018 Masters Tournament 本戦

感想

なかなかに大きい制約なので DPはなかなか発想できません.