区間内の個数 (文字列) 1 (paizaランク C 相当)

文字列 str を "bwwbwbbwbwbb" とします。

文字列 str の 3 文字目から 8 文字目までの 'b' の個数を累積和を用いて求めてください。

(ヒント)

文字列 str の i 文字目を str_i (1 ≦ i ≦ 10) とします。

まず、文字列 str の各要素が 'b' かどうかを格納する数列 b_0, b_1, ..., b_9 を以下のように考えてみます。

1 ≦ i ≦ 10 において
str_i が 'b' ならば b_(i-1) = 1
str_i が 'b' でないならば b_(i-1) = 0

例えば str = "bwbwwbwbwb" ならば b = {1, 0, 1, 0, 0, 1, 0, 1, 0, 1} となります。

ここで、数列 b の 1 の個数は、文字列 str の 'b' の個数と同じだとわかります。

つまり、数列 b で累積和を用いて、b_2 から b_7 までの総和を求めればよいです。

累積和をとった数列を s とすると、b_2 から b_7 までの総和は、s[8] - s[2] で求めることができます。

このヒントを元に、累積和で問題を解いてみましょう