SoundHoundコン本戦-B:Neutralize

問題

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

考え方

[i,i+k-1] の閉区間をすべて 0 にする。という操作の性質をフルに用いる。

DPを考える。

dp[i] := [0, i] の最大値

と定義する。このとき操作を考えて、dp[i] の更新を考えると以下のようになる。

  • 区間 [j+1, i]\ (0 \le j \le i-k)0 にする。= max(dp[j])
  • b[i] を足す
  • 区間 [0, i] をすべて 0 にする。

区間の最大値はDPの値を区間maxのセグメントツリーで保持しておけば O(logN) で求めることができるので全体の計算量は O(NlogN) となる。

Submission #4300743 - SoundHound Programming Contest 2018 Masters Tournament 本戦 (Open)

どこに着目して考察するべきだったか

操作を考えるとDPの更新がどのようになるか。

何がバグっていたか

得た知見(典型ポイント)

類題

参考