【C#】AtCoder Beginner Contest 130 のD問題でのしゃくとり法の実装

ABC130 D問題でしゃくとり法の実装が必要だったので、勉強した。今までこういった問題は累積和で解けるものしか解いてこなかったぽいので、今回ハマってしまった。

atcoder.jp

D問題の概要

• 長さNの正正数列 a_0, a_1 ... a_n と整数Kが与えられる
• 連続する部分列であって、以下の条件を満たすようなものは何個あるか
• (条件) 連続部分列に含まれる全ての要素の値の和はK以上である。

解法

今回、部分文字列の和がK以上になるかどうか確認するために、累積和で実装しようかと思ったのですが、その場合計算量がO(N²)になってしまうので、他に方法がないかなと考えてました。

そこで、例えば0番目からi-1番目までの和がKを超えていたらi番目からN番目を含む部分文字列もKを超えるなと考えました。

こんな感じで、4番目の7を足した時点でK=10以上になっているので、その後ろの5,3 を足したときも部分文字列の和はK以上になることが明らかです。そのため、文字列の数(長さ)からKを超えた時のインデックスの値を引くと部分文字列の数を導く事ができます。これを下記の用に左側のインデックスを変更しながら計算していきます。

これを実装することで、ACできます。

実装

実装の全体は下記です。 github.com