SoundHoundコン本戦-B:Neutralize
問題
https://atcoder.jp/contests/soundhound2018-summer-final-open/tasks/soundhound2018_summer_final_b
考え方
の閉区間をすべて にする。という操作の性質をフルに用いる。
DPを考える。
の最大値
と定義する。このとき操作を考えて、 の更新を考えると以下のようになる。
区間の最大値はDPの値を区間maxのセグメントツリーで保持しておけば で求めることができるので全体の計算量は となる。
Submission #4300743 - SoundHound Programming Contest 2018 Masters Tournament 本戦 (Open)
どこに着目して考察するべきだったか
操作を考えるとDPの更新がどのようになるか。