区間の数え上げ 1 (paizaランク C 相当)

(はじめに)

この問題では、累積和と似たアルゴリズムである「しゃくとり法」について扱います。

しゃくとり法を用いることで、条件を満たす区間の数や、最も長い区間の長さを求めることができます。

この問題集を通してしゃくとり法の問題に触れ、少しずつしゃくとり法に慣れていきましょう。

まずは、問題を見てみましょう。

---

(問題)

以下の 10 個の整数からなる数列が与えられます。

1 5 9 1 20 5 3 6 5 4

この数列において、長さが 1 以上で総和が 15 以下の区間がいくつあるか求めてください。

---

(ヒント : しゃくとり法の考え方)

二重ループを用いて区間の左端から右端までを総当たりすれば、しゃくとり法を使わずとも答えを求めることができますが、練習としてしゃくとり法で解いてみましょう

二重ループで実装してしまうと、数列の長さがとても大きい場合、計算量が多く対応することができません。

そこで、しゃくとり法を用いることで、答えを求める際の計算時間を大きく短縮することができます。

実際に考えてみましょう。

しゃくとり法を簡単に説明すると、「区間の先頭と末尾を交互に進めながら条件を満たす区間の数や最大の区間を求める手法」です。

与えらえた 10 個の整数

1 5 9 1 20 5 3 6 5 4

をそれぞれ

a_0 a_1 a_2 a_3 a_4 a_5 a_6 a_7 a_8 a_9

とします。また、区間を [left, right) (0 ≦ left < right ≦ 9) と考え、その区間の総和を sum とします。

ここで、left, right は区間の「しきり」と考えるとわかりやすいです。

例えば、区間を [2, 5) とすると、その区間は以下のように表せます。

a_0 a_1 a_2 a_3 a_4 a_5 a_6 a_7 a_8 a_9
       ↑          ↑
      left        right

まず、left = 0 のとき、sum が 15 以下の間どこまで right を進められるか考えてみましょう。

例えば、[0, 1) のとき、sum = a_0 = 1 となり、5 以下なのでまだ右に進められます。行けるところまで進めてみましょう

また、right を進めたとき、sum に a_right を足していきます。

[0, 3) のとき、sum = a_0 + a_1 + a_2 = 15 となり、これ以上右に進めることができません。

 a_0 a_1 a_2 a_3 a_4 a_5 a_6 a_7 a_8 a_9
  1   5   9   1   20  5   3   6   5   4
↑         ↑
left       right

そしてこのとき、right - left = 3 となり、これはそれまでの条件を満たす区間の数 ([0, 1), [0, 2), [0, 3) の 3 つ) であるとわかります。

このことから

① left を固定し、条件を満たす間 right を 1 ずつ進めていき、right がそれ以上進めなくなったとき、
   right - left とすることでそれまでの条件を満たす区間の数を求めることができる

ということがわかります。

次に、right がこれ以上右に進めなくなったとき、left を 1 進めます。

そしてまた、right を条件を満たす間、行けるところまで進めます。

注意として、left を進める前に sum から a_left を引くことを覚えておいてください。

先ほど [0, 3) まで進めたので、sum から a_left を引き、left を 1 進めます。

そうすると、区間は [1, 3) となり、sum は (a_0 + a_1 + a_2) - a_0 = a_1 + a_2 となるので、ちゃんとその区間の和が求められていることが分かります。

 a_0 a_1 a_2 a_3 a_4 a_5 a_6 a_7 a_8 a_9
  1   5   9   1   20  5   3   6   5   4
   ↑      ↑
   left    right

このことから

② right がこれ以上右に進めなくなったとき、left を 1 進め、また ① に戻る

とわかります。

しかし、① と ② を繰り返していると、区間が [4, 4) となってしまいます。

このままだと、② から、right はもう進めないので left を進めて、[5, 4) となってしまい、この区間は求められません。

なので

③ left == right となったときは、right を 1 進める

とすると、

[4, 4) なので right を進めて [4, 5) にする (③)
right はこれ以上右に進めないので left を進めて [5, 5) にする (②)
[5, 5) なので right を進めて [5, 6) にする (③)
right を進めるところまで進める (①)

となり、窮地を脱することができました。

まとめると

① left を固定し、条件を満たす間 right を 1 ずつ進めていき、right がそれ以上進めなくなったとき、
   right - left とすることでそれまでの条件を満たす区間の数を求めることができる
② right がこれ以上右に進めなくなったとき、left を 1 進め、また ① に戻る
③ ただし、left == right となったときは、right を 1 進める

とすればよいことがわかります。

このように、区間の左端と右端が交互に動いていくことから、しゃくとり虫に似ているので、しゃくとり法と言われています。

これらのヒントを元に、この問題を解いてみましょう。