ABC128 D - equeue

問題
提出コード

解法

から取り出した宝石をに再び詰めた後、再びその宝石を取り出すのは、ただ操作回数を無駄にしているだけなので、先に取り出す宝石の個数を決めた後、捨てる宝石を全て捨てるのが最適になります。
の左から取り出す宝石の個数を個、の右から取り出す宝石の個数を個とします。
このとき、捨てる操作は合計で回行うことができます。
左から個、右から個の宝石を取り出すとしたときに、残った回の操作で行う最適な「宝石を捨てる」操作は、

• 個の宝石を昇順でソートし、前から最大個、価値が負の宝石を選ぶ

となります。
この操作は、個選ぶのが最大、個選ぶのが最大、そして捨てる個数がたかだか個であり、この個数も最大で個です。取り出した宝石のソートおよび捨てる操作もでできるので、解説にもあるように、とすると、で最適解を調べることができます。

感想

計算量解析、考察ミスが怖くてじっくり時間をかけました。
ここら辺の証明等を高速に行いたいですね。