ABC130 D - Enough Array - ツバサの備忘録

解法

$a_{i}$ を0-indexed( $a_{0}$ ~ $a_{N-1}$ ) で考えていきます。
ある区間 $[l,r)$ についての $a_{i}$ の総和 $\displaystyle \sum_{i=l}^{r-1}a_{i}$ が $K$ 以上となっているとき、 $r \leqq j \leqq N$ を満たす区間 $[l,j)$ については全て部分列の総和が $K$ 以上となります。
ということで、それぞれの $l$ について、 $\displaystyle \sum_{i=l}^{r-1}a_{i} \leqq K$ を満たす $r$ の最小値を求め、 $N-r+1$ の総和を求めれば答えとなります。
また、 $l$ に対する $r$ の最小値を求めた後、 $l+1$ に対する区間の右端の最小値を求めるとき、求める右端が $r$ 未満になることはもちろんありません。
ということで、あとは尺取り法を用いて、 $l,r$ のペアを求めていけばよいです。

感想

尺取り法はよくバグらせるので、二分探索も候補に入れるべきですかね…
ノータイムで考察できるのはうれしいですね。