問題

https://atcoder.jp/contests/agc004/tasks/agc004_b

考え方

典型っぽい。ある変数を固定すると、最適な操作が見えてくる問題。

何を固定するか？

最小の秒数を $x$ 秒として二分探索
- 「 $x$ 秒で全色のスライムを集めることができるか？」というYes/No問題に切り替える
- しかし、結局最適なスライムの集め方の考察が必要で問題が進んでいない
魔法の回数を $k$ とする
- あるスライム $i$ を集めるときの最小のコストは $min\{a_{i-k}, a_{i-k+1}, \cdots, a_{i}\}$ で求められることになる
- 各スライムについて、上記の方法で最小コストを求めれば解ける

よって上記から魔法の回数を $k$ 回使うとすると、各スライムを集める秒数の最小値を求められることになる。区間 $[i-k,i]$ の秒数の最小値はセグメントツリーを用いることができるし、 $k$ の小さい値から考えることで自然に求めることもできる。セグメントツリーを使った場合は計算量は $O(N^2\ logN)$ となる。