問題
atcoder.jp
解法
ある区間 [l, r] の和が K 以上であるとき，区間 [l, r + 1], [l, r + 2], ... , [l, N] のそれぞれの和も当然 K 以上なので，各 l について最初に区間の和が K 以上となる r が分かればよい．この l, r は尺取り法によって求めることができる．具体的には，まず l = 1 のとき r を愚直に最初から探していく．次に l = 2 とし，区間 [l = 2, r] の和が K 以上でなければ r を区間の和が K 以上になるまで動かす．これを l = N まで繰り返していく．各要素高々 2 回しか見ていないので O(N)．
解答
atcoder.jp
