AtCoder Beginner Contest 130：D - Enough Array

問題

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

AtCoder Beginner Contest 130：C - Rectangle Cutting

問題

atcoder.jp

解法

与えられた長方形の重心を通るような面積を半分にする直線は，長方形の対角線である 2 本が考えられる．それ以外の点で半分にする直線は 1 本に定まる．O(1)．

解答

atcoder.jp

プログラミングバトル 本戦 - BCU30：B - Interval Addition

問題

atcoder.jp

解法

広義単調増加となっている部分列の個数が答えになる．無駄に最初から全体に +min(A) してから・・・などと考えると反例が出てくるので注意する（1 WA した）．

解答

atcoder.jp