あいさつ

こんにちは．最近何かと新しいことに挑戦しがち（先日の星ナビもその一環なのですが）なのですが，最近6,7年ぶりくらいに競技プログラミングに挑戦しています．今回はAtCoder Beginner Contest 130でした．私の解答例はこちら．※E, Fは解いてません．

A問題

特筆すべきことはありません．
X < A ? 0 : 10を出力します．

B問題

これも特に難しい点はないですね．
現在の座標をdとして，d <= Xの間だけカウントしつつdを更新し，満たさなくなれば終了します．O(N)です．

C問題

長方形の内部または周辺の点Pを通る直線で長方形を2つに分割する時，小さい方の最大値を求め，分割する方法が1つか複数かを判定しろという問題です．
問題文はややこしいですが，とりあえずど真ん中の点を通る直線を引けば必ず半分にすることができて，半分になった時に題意を満たすことは明らかです．W, Hが10^9までとりえるので，64bitで計算する必要があることに注意です．
分割する方法に関してですが，点がど真ん中以外の時は一位に定まり，ど真ん中の時は無数に存在します．サンプルケースが理解の助けになりました．点Pを(x, y)とすればif (x * 2 == W && y * 2 == H)のように判別できますね（自分はW / 2を計算してキャストの問題でWA出しました，反省）．

D問題

長さNの整数列の部分列で，和がK以上のものは何通りあるかという問題です．
累積和を使って考えたいというのが僕の方針で，実際それで解けましたが，実際にはしゃくとり法を使うといいっぽいです．なぜなら累積和は単調増加するので，超えたところから右は判定する必要がなく，右の超えた位置を保持しながら左を進めることで計算量を減らせます．具体的には，累積和を計算した配列をsums（最初は0），端点をleft, rightとすれば，

1
2
3
4
5
6
7
8
9
10
while (left <= n) {
    right = max(left + 1, pbuf);
    while (right <= n && sums[right] - sums[left] < k)
    {
        ++right;
    }
    pbuf = right;
    counter += n - right + 1;
    ++left;
}

のようにすれば，counterに答えが求まります．pbufは現在の右端の値を保持しておきます（maxを使っていてしゃくとり法として微妙な感じがありますが，通ったのでこれでよしとします）．自分の提出コードはもっと汚いですが，原理的にはしゃくとり法と同じことをやっているんだなあと思いました．数列の長さは最大10^5ですが，計算する累積和やKは10^10までとりえるのでオーバーフローに注意します．
E,Fも気が向いたら解いてみたいと思います．