【paiza問題集解説】累積和メニュー

【区間の和】区間の和 4

STEP: 1 区間の和 1

区間の和 1

ここは問題の解説ではなく、累積和 (cumulative sum) についての説明です。ここでは視覚的にわかるように累積和の作り方を説明します。

数列の『ある区間和を求めなさい』という問題が出る
数列を使って累積和を作る
累積和を使って区間和を求める

というステップで問題を解きます。「累積和」は区間和を求める時などの前準備のもので、『これさえ作っちまえばあとはこっちのもんよ！』というくらい汎用性の高いツールです。そのツールの作り方と使い方をここで学習します。

例）A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

ちなみにこの数列の数を全て足すと 55 になりますよね。この数列を使って累積和で 55 を導き出してみます。

まずは新しく cum_sum というリストを作ります。その初期値を [0] にします。

cum_sum = [0]

これとリストA を使って累積和を作ります。

要素番号	0	1	2	3	4	5	6	7	8	9	10
cum_sum	0	1	3	6	10	15	21	28	36	45	55
リストA	1	2	3	4	5	6	7	8	9	10

cum_sum[0] = 0
cum_sum[1] = cum_sum[0] + A[0]
cum_sum[2] = cum_sum[1] + A[1]
(中略)
cum_sum[10] = cum_sum[9] + A[9]

これをプログラムにすると、

A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
cum_sum = [0] * 11  # 先にゼロマップを作る方法
for i in range(10):
    cum_sum[i+1] = cum_sum[i] + A[i]
print(cum_sum)

[0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55]

という感じになります。
この数列を「累積和」と言います。１つ１つの数値を指すこともあります。
このリストの最後の 55 が、1 から 10 の総和です。45 が、1 から 9 の総和です。

ここまでが「前準備」と言われるところです。

今度はこの累積和を使って区間和を求めてみます。びっくりするほど簡単です。😊

数列 1 2 3 4 5 6 7 8 9 10 の、5 番目から 8 番目の区間和を求める場合。

5 番目というのは 5 です。8 番目は 8 です。
5 + 6 + 7 + 8 = 26
この 26 を累積和を用いて求めます。

リストA		1	2	3	4	5	6	7	8	9	10
cum_sum	0	1	3	6	10	15	21	28	36	45	55

1 ～ 8 までを足した数が 36 です。
5 ～ 8 までを足した数を求めたいので、1 ～ 4 までの数は不要です。
よって、1 ～ 8 まで足した 36 から 1 ～ 4 までを足した 10 を引くと、5 ～ 8 を足した数が求められます。

cum_sum[8] - cum_sum[4]
↓
36 - 10
↓
26

プログラムにすると、

A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
cum_sum = [0] * 11
for i in range(10):
    cum_sum[i+1] = cum_sum[i] + A[i]

sum_range = cum_sum[8] - cum_sum[4]
print(sum_range)

26

この累積和が役立つのは、線形で繰り返し区間和を求める時です。例えば 1 ～ 100、2 ～ 101、……の区間和を何百回何百万回と繰り返して求める時、ループごとに毎度 1 ～ 100、2 ～ 101、と足し算をしていくことになります。時間がかかります。これを ed - st-1 と引き算するだけで一発で区間和を求めてしまいます。サイコーです。
これがランダムな数列だったとしても、区間がランダムだったとしても関係なく、一度累積和を作ってしまえば ed - st-1 でお好きな区間和を何度でも一発で求めてしまいます。めがみ…。
これを人の手でやったとして、予め累積和さえ作っておけばどれだけ早く区間和が求められるかが容易に想像できるでしょう。

小学生でも超簡単に扱えるアルゴリズム。ネコにも優しい世界です。

それでは早速、問題の STEP 1 を累積和を使って区間和を求めるプログラムを組んでみましょう！もちろんこのプログラムを参考にしながらでも構いませんよ！

STEP: 2 区間の和 2

区間の和 2

A = list(map(int, input().split()))

len_A = len(A)
cum_sum = [0] * (len_A + 1)
for i in range(len_A):
    cum_sum[i+1] = cum_sum[i] + A[i]

sum_range = cum_sum[7+1] - cum_sum[2]
print(sum_range)

先頭に 0 を追加する累積和は、与えられた数列と比べて要素が１つ後方にずれています。問題では a_0 からと書かれていますので、A[i] の累積和が cum_sum[i+1] となります。
よって、a_7 は cum_sum[8]、a_2 は cum_sum[3] となります。

STEP: 3 区間の和 3

区間の和 3

X, Y = map(int, input().split())
A = list(map(int, input().split()))

len_A = len(A)
cum_sum = [0] * (len_A + 1)
for i in range(len_A):
    cum_sum[i+1] = cum_sum[i] + A[i]

sum_range = cum_sum[Y+1] - cum_sum[X]
print(sum_range)

範囲が入力で与えられています。直接数を充てていた所をこの入力に置き換えるだけです。

FINAL問題【区間の和】区間の和 4

【区間の和】区間の和 4

N, X, Y = map(int, input().split())
A = list(map(int, input().split()))

cum_sum = [0] * (N+1)
for i in range(N):
    cum_sum[i+1] = cum_sum[i] + A[i]

sum_range = cum_sum[Y+1] - cum_sum[X]
print(sum_range)

数列の個数が与えられています。len_A の代わりにこれを使うだけで完成です。

【連続する N 個の和の最大値】連続する N 個の和の最大値 4

STEP: 1 連続する N 個の和の最大値 1

連続する N 個の和の最大値 1

例１

A = [1, 5, 9, 7, 5, 3, 2, 5, 8, 4]

len_A = len(A)
cum_sum = [0] * (len_A + 1)
for i in range(len_A):
    cum_sum[i+1] = cum_sum[i] + A[i]

max_ = -float('inf')
for i in range(3, len(cum_sum)):
    max_ = max(max_, cum_sum[i] - cum_sum[i-3])

print(max_)

例２

A = [1, 5, 9, 7, 5, 3, 2, 5, 8, 4]

len_A = len(A)
cum_sum = [0] * (len_A + 1)
for i in range(len_A):
    cum_sum[i+1] = cum_sum[i] + A[i]

max_ = -float('inf')
for i in range(len(cum_sum) - 3):
    max_ = max(max_, cum_sum[i+3] - cum_sum[i])

print(max_)

例１と例２の違いは範囲の取り方です。ターゲットとしているのが、例１は累積和、例２は不要な累積和です。

以降は例２の書き方でプログラム例を作っていきます。

STEP: 2 連続する N 個の和の最大値 2

連続する N 個の和の最大値 2

A = list(map(int, input().split()))

len_A = len(A)
cum_sum = [0] * (len_A + 1)
for i in range(len_A):
    cum_sum[i+1] = cum_sum[i] + A[i]

max_ = -float('inf')
for i in range(len(cum_sum) - 3):
    max_ = max(max_, cum_sum[i+3] - cum_sum[i])

print(max_)

数列が入力として与えられる以外、１つ前の「連続する N 個の和の最大値 1」と変わりありません。

STEP: 3 連続する N 個の和の最大値 3

連続する N 個の和の最大値 3

N = int(input())
A = list(map(int, input().split()))

cum_sum = [0] * (N+1)
for i in range(N):
    cum_sum[i+1] = cum_sum[i] + A[i]

max_ = -float('inf')
for i in range(len(cum_sum) - 3):
    max_ = max(max_, cum_sum[i+3] - cum_sum[i])

print(max_)

入力値が与えられるほうが楽でいいですが、リアルでは自分で数列の個数を取得しなければいけないので、 len() を使う書き方もちょっぴり覚えておいてください。

FINAL問題【連続する N 個の和の最大値】連続する N 個の和の最大値 4

【連続する N 個の和の最大値】連続する N 個の和の最大値 4

N, K = map(int, input().split())
A = list(map(int, input().split()))

cum_sum = [0] * (N+1)
for i in range(N):
    cum_sum[i+1] = cum_sum[i] + A[i]

max_ = -float('inf')
for i in range(len(cum_sum) - 3):
    max_ = max(max_, cum_sum[i+3] - cum_sum[i])

print(max_)

for i in range(len(cum_sum) - 3): の所の len(cum_sum) - 3 は、N-2 としてもOKです。
N は数列A の個数なので、0 の分、要素数が１つ多い累積和の要素数から 1 を引いて N-2 とする必要があります。

ここでは学習の為にわかりやすい len(cum_sum) - 3 の書き方をしていきますが、気兼ねなく N-2 で書いていっても構いません。学習段階ですのでお好きなほうでどうぞ。

【区間内の個数】区間内の個数 4

STEP: 1 区間内の個数 1

区間内の個数 1

A = [1, 5, 9, 7, 5, 3, 2, 5, 8, 4]
B = [i%2 == 0 for i in A]

len_B = len(B)
cum_sum = [0] * (len_B + 1)
for i in range(len_B):
    cum_sum[i+1] = cum_sum[i] + B[i]

sum_range = cum_sum[8] - cum_sum[2]
print(sum_range)

これまでは「数の累積和」で計算してきましたが、今回は「個数の累積和」を求めます。数が個数に変わっただけなのですが、条件である偶数の数に変換する必要があります。それが二行目の文です。

A を B にすると、

A = [1, 5, 9, 7, 5, 3, 2, 5, 8, 4]
B = [0, 0, 0, 0, 0, 0, 1, 0, 1, 1]

となります。この数列B の 0 から数えて 2 番目から 7 番目の範囲にある 1 の個数を累積和を使って求めます。

B = [0, 0, 0, 0, 0, 0, 1, 0, 1, 1]
cum_sum = [0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 3]

あとはこれまでやってきたような引き算で個数が求められます。

cum_sum[8] - cum_sum[2]
↓
1 - 0
↓
1

この例では面白くもなんともありませんが、この様に累積和を用いて区間内の個数を求めることができます。

STEP: 2 区間内の個数 2

区間内の個数 2

A = list(map(int, input().split()))
B = [i%2 == 0 for i in A]

len_B = len(B)
cum_sum = [0] * (len_B + 1)
for i in range(len_B):
    cum_sum[i+1] = cum_sum[i] + B[i]

sum_range = cum_sum[8] - cum_sum[2]
print(sum_range)

数列A が入力で与えられた以外は変わりありません。

STEP: 3 区間内の個数 3

区間内の個数 3

X, Y = map(int, input().split())
A = list(map(int, input().split()))
B = [i%2 == 0 for i in A]

len_B = len(B)
cum_sum = [0] * (len_B + 1)
for i in range(len_B):
    cum_sum[i+1] = cum_sum[i] + B[i]

sum_range = cum_sum[Y+1] - cum_sum[X]
print(sum_range)

範囲が入力で与えられた以外は変わりありません。

FINAL問題【区間内の個数】区間内の個数 4

【区間内の個数】区間内の個数 4

N, X, Y = map(int, input().split())
A = list(map(int, input().split()))
B = [i%2 == 0 for i in A]

cum_sum = [0] * (N+1)
for i in range(N):
    cum_sum[i+1] = cum_sum[i] + B[i]

sum_range = cum_sum[Y+1] - cum_sum[X]
print(sum_range)

数列の数の個数が入力で与えられた以外は変わりありません。
数列や範囲が変わっても累積和の作り方や求め方に変化が無いのが特徴です。

【区間内の個数 (文字列) 】区間内の個数 (文字列) 4

STEP: 1 区間内の個数 (文字列) 1

区間内の個数 (文字列) 1

A = 'bwwbwbbwbwbb'
B = [c == 'b' for c in A]

len_B = len(B)
cum_sum = [0] * (len_B + 1)
for i in range(len_B):
    cum_sum[i+1] = cum_sum[i] + B[i]

sum_range = cum_sum[8] - cum_sum[2]
print(sum_range)

数が文字に変わっただけで、これまでと書き方に変わりはありません。ただ、先頭の文字が 1 番目から始まりますので添字の書き方に注意してください。と言ってもこちらのほうがわかりやすいんですけどね。😽

     b  w  w  b  w  b  b  w  b  w  b  b
B = [1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1]

B       =    [1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1]
cum_sum = [0, 1, 1, 1, 2, 2, 3, 4, 4, 5, 5, 6, 7]

cum_sum[8] - cum_sum[2]
↓
4 - 1
↓
3

STEP: 2 区間内の個数 (文字列) 2

区間内の個数 (文字列) 2

A = input()
B = [c == 'b' for c in A]

len_B = len(B)
cum_sum = [0] * (len_B + 1)
for i in range(len_B):
    cum_sum[i+1] = cum_sum[i] + B[i]

sum_range = cum_sum[8] - cum_sum[2]
print(sum_range)

１つ前のプログラムのコピペから書き換えても構いません。その場合、どこを書き換える必要があるかを認識しながら書き換えてみてください。

STEP: 3 区間内の個数 (文字列) 3

区間内の個数 (文字列) 3

X, Y = map(int, input().split())
A = input()
B = [c == 'b' for c in A]

len_B = len(B)
cum_sum = [0] * (len_B + 1)
for i in range(len_B):
    cum_sum[i+1] = cum_sum[i] + B[i]

sum_range = cum_sum[Y] - cum_sum[X-1]
print(sum_range)

FINAL問題【区間内の個数 (文字列) 】区間内の個数 (文字列) 4

【区間内の個数 (文字列) 】区間内の個数 (文字列) 4

N, X, Y = map(int, input().split())
A = input()
B = [c == 'b' for c in A]

cum_sum = [0] * (N+1)
for i in range(N):
    cum_sum[i+1] = cum_sum[i] + B[i]

sum_range = cum_sum[Y] - cum_sum[X-1]
print(sum_range)

プログラムを書き換えるのも結構勉強になると思いませんか？「書き換える」という行為はある程度、内容を理解していないと出来ないものです。プログラミングにおいてコピペは悪ではないのです。コピペだからこそ、このプログラムで本当に正しいのかどうか、隅々まで内容を精査する必要があるからです。エラーが起これば尚更です。

【二次元累積和】二次元累積和 7

STEP: 1 二次元累積和 1

二次元累積和 1

二次元になると途端に難易度が上がるのはどんな場合も同じです。
今度は二次元累積和を学習します。

まずは二次元累積和にするとどんな風になるのかを見てみましょう。

1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1

この行列を二次元累積和にすると・・・

1  2  3  4  5  6
2  4  6  8 10 12
3  6  9 12 15 18
4  8 12 16 20 24
5 10 15 20 25 30

となります。
これは例えば 12 は、左上から 12 までの長方形の範囲の中の数がすべて足されたものです。

1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1

どこの数に注目してもそのようになっています。

今度はこの範囲に注目します。

1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1

パッと見てこの範囲の総和が 9 ということがわかりますが、これを二次元累積和で求めてみます。

1  2  3  4  5  6
2  4  6  8 10 12
3  6  9 12 15 18
4  8 12 16 20 24
5 10 15 20 25 30

まず該当する部分はここです。このうちの右下の 30 が、この行列全体の総和です。1 が 6×5 個で 30 です。
(一次元)累積和ではこの数から不要な数を引いた数が区間和となりました。二次元累積和もここから不要な数を引くと範囲の総和である 9 が求められます。

1  2  3  4  5  6
2  4  6  8 10 12
3  6  9 12 15 18
4  8 12 16 20 24
5 10 15 20 25 30

で囲われた範囲が不要な部分です。よって 30 から ??? を引きます。

1  2  3  4  5  6
2  4  6  8 10 12
3  6  9 12 15 18
4  8 12 16 20 24
5 10 15 20 25 30

12 と 15 に注目します。
12 は左上からの長方形の範囲の総和です。
15 は左上からの長方形の範囲の総和です。

まず 30 から 12 を引きます。

1  2  3  4  5  6
2  4  6  8 10 12
3  6  9 12 15 18
4  8 12 16 20 24
5 10 15 20 25 30

30 - 12 = 18

次に 18 から 15 を引きます。

1  2  3  4  5  6
2  4  6  8 10 12
3  6  9 12 15 18
4  8 12 16 20 24
5 10 15 20 25 30

18 - 15 = 3

この時、

1  2  3  4  5  6
2  4  6  8 10 12
3  6  9 12 15 18
4  8 12 16 20 24
5 10 15 20 25 30

の範囲が２度引かれてしまっていますので、１度だけ足して帳尻を合わせます。

3 + 6 = 9

これをプログラムにしてみます。

A = [[1] * 6 for _ in range(5)]

cum_sum = [[0] * 7 for _ in range(6)]
for y in range(5):
    for x in range(6):
        cum_sum[y+1][x+1] = cum_sum[y+1][x] + cum_sum[y][x+1] - cum_sum[y][x] + A[y][x]

sum_range = cum_sum[5][6] - cum_sum[2][6] - cum_sum[5][3] + cum_sum[2][3]
print(sum_range)

今度はこのプログラムを参考にしながら二次元累積和を作ってみます。変数のせいで長く難しそうに見えますが、わかれば大したことありません。むしろこれだけの事をやっているのに数行で済んでしまっています。

まずは二次元累積和用にゼロマップを作ります。

cum_sum = [[0] * 7 for _ in range(6)]

次の三行の二重ループで二次元累積和を次々作っていきます。

for y in range(5):
    for x in range(6):
        cum_sum[y+1][x+1] = cum_sum[y+1][x] + cum_sum[y][x+1] - cum_sum[y][x] + A[y][x]

リストA

1 1 1 1 1 1
1 1 1 1 1 1

cum_sum

0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

まずはリストA の左上のこの部分にだけ注目します。
二次元累積和のゼロマップの一番上の一列と、一番左の一列は、計算用のダミーです。これは読み進めると意味が分かります。

リストA の左上から右下へ向かって順に計算していきます。

リストA

1 1 1 1 1 1
1 1 1 1 1 1

cum_sum

0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

cum_sum の 0 の所が、リストA の 1 の累積和になる場所です。ここの求め方は次のとおりです。

cum_sum の 0 の左の数を足す。cum_sum[y+1][x]
cum_sum の 0 の上の数を足す。cum_sum[y][x+1]
cum_sum の 0 の左上の数を引く。 cum_sum[y][x]
リストA の 1 を足す。A[y][x]

これが cum_sum の 0 の所 cum_sum[y+1][x+1] = で、ここが結果、1 になります。
数値が 0 ばかりでわかりにくいですが、これを進めていくと二次元累積和が完成します。この手順を繰り返し、完成した二次元累積和を見て確認してみてください。

リストA

1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1

cum_sum
0  0  0  0  0  0  0
0  1  2  3  4  5  6
0  2  4  6  8 10 12
0  3  6  9 12 15 18
0  4  8 12 16 20 24
0  5 10 15 20 25 30

cum_sum[y+1][x+1] = cum_sum[y+1][x] + cum_sum[y][x+1] - cum_sum[y][x] + A[y][x]

上の 5 のところは、4 + 0 - 0 + 1 = 5 です。
9 のところは、6 + 6 - 4 + 1 = 9 です。
30 のところは、25 + 24 - 20 + 1 = 30 です。

y+1 とか x とかどの位置見てるのかなど結構混乱しますので、落ち着いて書いていってくださいね。

プログラム最後の部分、

sum_range = cum_sum[5][6] - cum_sum[2][6] - cum_sum[5][3] + cum_sum[2][3]

ここは最終的に、作った二次元累積和を使って求める範囲の総和を計算で割り出しています。これです。👇

0  0  0  0  0  0  0
0  1  2  3  4  5  6
0  2  4  6  8 10 12
0  3  6  9 12 15 18
0  4  8 12 16 20 24
0  5 10 15 20 25 30

sum_range = 30 - 12 - 15 + 6
↓
sum_range = 9

ちなみに足し算引き算の順番はご自由に。この書き順でわかりにくかったら順番を入れ替えて自分なりにわかりやすくしてみてください。👍

大体でもわかったら、問題をやってみましょう。いきなりプログラムを書くにはまだ敷居が高いと思いますので、上のプログラムをコピペして目で追いながら書き換えて組み上げてみてください。
そして 100点をとったそのプログラムをどこかにメモしてとっておくと、忘れてしまったときにそのメモをちょいと見返せば思い出す助けになるでしょう。y+1 とか x とかややこしいですからね！

STEP: 2 二次元累積和 2

二次元累積和 2

A = [list(map(int, input().split())) for _ in range(5)]

cum_sum = [[0] * 6 for _ in range(6)]
for y in range(5):
    for x in range(5):
        cum_sum[y+1][x+1] = cum_sum[y+1][x] + cum_sum[y][x+1] - cum_sum[y][x] + A[y][x]

sum_range = cum_sum[4][4] - cum_sum[1][4] - cum_sum[4][1] + cum_sum[1][1]
print(sum_range)

コピペなら各所数値を書き換えるだけで済むのですが、それでも混乱してしまいますね。

STEP: 3 二次元累積和 3

二次元累積和 3

a, b = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(5)]

cum_sum = [[0] * 6 for _ in range(6)]
for y in range(5):
    for x in range(5):
        cum_sum[y+1][x+1] = cum_sum[y+1][x] + cum_sum[y][x+1] - cum_sum[y][x] + A[y][x]

sum_range = cum_sum[b+1][4] - cum_sum[b+1][3] - cum_sum[a][4] + cum_sum[a][3]
print(sum_range)

添字と同じ並びの書き方がされています。よって {a, 3} ～ {b, 3} は縦長の長方形になります。

二次元累積和にすると位置が +1 ずれますので、変数に +1 を付けて調整します。あとは落ち着いて正しく添字を書けばクリアするはずです。

STEP: 4 二次元累積和 4

二次元累積和 4

a, b, c, d = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(5)]

cum_sum = [[0] * 6 for _ in range(6)]
for y in range(5):
    for x in range(5):
        cum_sum[y+1][x+1] = cum_sum[y+1][x] + cum_sum[y][x+1] - cum_sum[y][x] + A[y][x]

sum_range = cum_sum[c+1][d+1] - cum_sum[c+1][b] - cum_sum[a][d+1] + cum_sum[a][b]
print(sum_range)

今度は {a, b}, {c, d} なので、添字は [a|c][b|d] となります。
これを念頭にまた落ち着いて正しく添字を書いていけばクリアするはずです。

STEP: 5 二次元累積和 5

二次元累積和 5

N = int(input())
a, b, c, d = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]

cum_sum = [[0] * (N+1) for _ in range(N+1)]
for y in range(N):
    for x in range(N):
        cum_sum[y+1][x+1] = cum_sum[y+1][x] + cum_sum[y][x+1] - cum_sum[y][x] + A[y][x]

sum_range = cum_sum[c+1][d+1] - cum_sum[c+1][b] - cum_sum[a][d+1] + cum_sum[a][b]
print(sum_range)

今度は入力 N が追加されましたが、二次元累積和本体の問題ではありませんので楽勝だったことでしょう。

STEP: 6 【二次元累積和】二次元累積和 6

【二次元累積和】二次元累積和 6

N, M = map(int, input().split())
a, b, c, d = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]

cum_sum = [[0] * (M+1) for _ in range(N+1)]
for y in range(N):
    for x in range(M):
        cum_sum[y+1][x+1] = cum_sum[y+1][x] + cum_sum[y][x+1] - cum_sum[y][x] + A[y][x]

sum_range = cum_sum[c+1][d+1] - cum_sum[c+1][b] - cum_sum[a][d+1] + cum_sum[a][b]
print(sum_range)

行と列が任意の数になっただけですので、列の部分の N を M に書き換えるだけですね。😊

FINAL問題【二次元累積和】二次元累積和 7

【二次元累積和】二次元累積和 7

N, M, Q = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]

cum_sum = [[0] * (M+1) for _ in range(N+1)]
for y in range(N):
    for x in range(M):
        cum_sum[y+1][x+1] = cum_sum[y+1][x] + cum_sum[y][x+1] - cum_sum[y][x] + A[y][x]

for _ in range(Q):
    a, b, c, d = map(int, input().split())
    sum_range = cum_sum[c+1][d+1] - cum_sum[c+1][b] - cum_sum[a][d+1] + cum_sum[a][b]
    print(sum_range)

今まで１回計算するだけでしたが、今度は Q 回計算するプログラムを書きます。と言っても、少し手を加えるだけで出来上がってしまいます。

FINAL問題だけあって、この形でプログラムを書く問題が各所ちりばめられています。
このプログラムもメモして、もしくはメモした以前のプログラムからこちらに更新してとっておくとよいでしょう。

【1 次元上のいもす法】1 次元上のいもす法 4

STEP: 1 1 次元上のいもす法 1

1 次元上のいもす法 1

「いもす法 (Imos Lab)」についてはリンク先をご覧ください。

問題文に書かれているヒントで、しくみはおおかた掴めたかと思います。ですので、ここは問題のプログラム例を用いながら説明していきます。

queries = [[1, 3], [1, 8], [3, 8], [3, 6], [7, 9]]

cum_sum = [0] * (1+10+1)
for l, r in queries:  # いもす法
    cum_sum[l] += 1
    cum_sum[r+1] += -1

for i in range(11):  # 累積和
    cum_sum[i+1] += cum_sum[i]

print(max(cum_sum))

入力が与えられていないので、手入力で用意します。今後の問題の入力形式を考慮して二次元リストで作りました。
問題に『横に並んだ 10 個のマスがあり、最初、マスには全て 0 が書かれています。』とあるので、要素数 10 のゼロマップを作ります。

A = [0] * 10

ここにいもす法で直接増減を書き加えるので、いもす法用に 0 を１つ加えます。

A = [0] * (10+1)

最後に累積和をとるので、累積和用に 0 をさらに１つ加えます。
※ 解説最後に注釈あり。

cum_sum = [0] * (1+10+1)

合わせて 0 が 12 個の数列が出来上がります。

queries = [[1, 3], [1, 8], [3, 8], [3, 6], [7, 9]]

for l, r in queries:  # いもす法
    cum_sum[l] += 1
    cum_sum[r+1] += -1

いもす法のプログラムはいたってシンプルで、入力値を添字に当てはめて、それぞれ 1 を増減するだけです。-1 する所は r の次なので r+1 となります。これを繰り返していくと、

l, r = 1, 3

要素番号	0	1	2	3	4	5	6	7	8	9	10	11
cum_sum	0	1	0	0	-1	0	0	0	0	0	0	0

↓

l, r = 1, 8

要素番号	0	1	2	3	4	5	6	7	8	9	10	11
cum_sum	0	2	0	0	-1	0	0	0	0	-1	0	0

↓

l, r = 3, 8

要素番号	0	1	2	3	4	5	6	7	8	9	10	11
cum_sum	0	2	0	1	-1	0	0	0	0	-2	0	0

↓

l, r = 3, 6

要素番号	0	1	2	3	4	5	6	7	8	9	10	11
cum_sum	0	2	0	2	-1	0	0	-1	0	-2	0	0

↓

l, r = 7, 9

要素番号	0	1	2	3	4	5	6	7	8	9	10	11
cum_sum	0	2	0	2	-1	0	0	0	0	-2	-1	0

いもす法が終了したら、今度はこの数列をこのまま累積和にします。

for i in range(11):  # 累積和
    cum_sum[i+1] += cum_sum[i]

要素番号	0	1	2	3	4	5	6	7	8	9	10	11
cum_sum	0	2	0	2	-1	0	0	0	0	-2	-1	0

↓

要素番号	0	1	2	3	4	5	6	7	8	9	10	11
cum_sum	0	2	2	`4`	3	3	3	3	3	1	0	0

いもす法用に用意した要素番号 11 まで累積和が届くように、きちんと 0 ～ 10 までループを回します。

最後に、最大値を見つけ出して画面に出力したら完了です。

※ 累積和用にと先頭に 0 を加えましたが、今回のプログラムでは必要ではありません。
混乱を避ける為にこれまでの流れに合わせて位置合わせをしてわかりやすくする為に 0 を付け足したまでです。この解説を見て完全に理解したならば、paiza の解説の通りにしてもよいですし、今はまだ 0 を付けたほうがわかりやすいというならばこの方法でもいいでしょう。

このプログラム例をそのままコピペ提出しても意味無いので、プログラム例をじっとみつめて内容を把握し、また記憶し、ゼロから自分の手で打ち込んでプログラムを完成させてみてください。しくみと流れが理解できれば難しいことはないでしょう。ちょっと思い出せなくなってしまった時には、その時にまたプログラム例を覗いて思い出しながら組み上げてみてください。

STEP: 2 1 次元上のいもす法 2

1 次元上のいもす法 2

cum_sum = [0] * 12
for _ in range(5):
    L, R = map(int, input().split())
    cum_sum[L] += 1
    cum_sum[R+1] += -1

for i in range(11):
    cum_sum[i+1] += cum_sum[i]

print(max(cum_sum))

範囲が入力で与えられましたので、プログラム例の様に書き換えます。

入力例が簡素だと、合っているのかがわかりにくいですね。😅

STEP: 3 1 次元上のいもす法 3

1 次元上のいもす法 3

N = int(input())

cum_sum = [0] * 12
for _ in range(N):
    L, R = map(int, input().split())
    cum_sum[L] += 1
    cum_sum[R+1] += -1

for i in range(11):
    cum_sum[i+1] += cum_sum[i]

print(max(cum_sum))

入力値 N が追加されましたので、ループに充てます。

増減分も変わらず、「いい加減わかったよ！」と余裕が出てきたら、異なる書き方も考えてみてください。

FINAL問題【1 次元上のいもす法】1 次元上のいもす法 4

【1 次元上のいもす法】1 次元上のいもす法 4

N, Q = map(int, input().split())

cum_sum = [0] * (N+2)
for _ in range(Q):
    L, R = map(int, input().split())
    cum_sum[L] += 1
    cum_sum[R+1] += -1

for i in range(N+1):
    cum_sum[i+1] += cum_sum[i]

print(max(cum_sum))

N が Q になり、N が個数に変わりました。N 個にいもす法用と累積和用として +2 すれば、これまでのプログラムが流用できます。

また、STEP 1 で先頭の 0 は不要と補足しましたが、その場合のプログラムの書き方は以下の様になります。

N, Q = map(int, input().split())

cum_sum = [0] * (N+1)  # 変更箇所
for _ in range(Q):
    L, R = map(int, input().split())
    cum_sum[L-1] += 1  # 変更箇所
    cum_sum[R] += -1  # 変更箇所

for i in range(N):  # 変更箇所
    cum_sum[i+1] += cum_sum[i]

print(max(cum_sum))

この書き方でもう一度 STEP 1 からやってみてください。😊

【2 次元上のいもす法】 2 次元上のいもす法 6

STEP: 1 2 次元上のいもす法 1

2 次元上のいもす法 1

二次元では少々、いもす法の作り方がわかりにくいかと思います。ただ、やろうとしていることまではわかるでしょう。
今回もプログラム例に沿って解説していきます。

cum_sum = [[0] * 7 for _ in range(7)]
locs = [[1, 1, 3, 3], [2, 2, 4, 4], [3, 3, 5, 5], [1, 3, 3, 5], [3, 1, 5, 3]]

# いもす法
for sx, sy, ex, ey in locs:
    cum_sum[sy][sx] += 1
    cum_sum[sy][ex+1] -= 1
    cum_sum[ey+1][sx] -= 1
    cum_sum[ey+1][ex+1] += 1
    
# 二次元累積和
for y in range(6):
    for x in range(6):
        cum_sum[y+1][x+1] = cum_sum[y][x+1] + cum_sum[y+1][x] - cum_sum[y][x] + cum_sum[y+1][x+1]

max_= -float('inf')
for row in cum_sum:
    max_ = max(max_, max(row))

print(max_)

※ これまでの流れに沿ったプログラムの書き方と解説をする為、paiza のヒントとは異なる方法をとっています。

一行目がゼロマップです。累積和用といもす法用に 0 を追加しています。
二行目は 1 を加算する範囲のリストです。以降の問題の入力形式に合わせた書き方をしています。

次に、いもす法の処理をします。

for sx, sy, ex, ey in locs:
    cum_sum[sy][sx] += 1
    cum_sum[sy][ex+1] -= 1
    cum_sum[ey+1][sx] -= 1
    cum_sum[ey+1][ex+1] += 1

y x	0	1	2	3	4	5	6
0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	0
2	0	0	0	0	0	0	0
3	0	0	0	0	0	0	0
4	0	0	0	0	0	0	0
5	0	0	0	0	0	0	0
6	0	0	0	0	0	0	0

↓

sx, sy, ex, ey = 1, 1, 3, 3

y x	1	4
0	0	0
1	1	-1
2	0	0
3	0	0
4	-1	1
5	0	0
6	0	0

↓

sx, sy, ex, ey = 2, 2, 4, 4

y x	1	2	4	5
0	0	0	0	0
1	1	0	-1	0
2	0	1	0	-1
3	0	0	0	0
4	-1	0	1	0
5	0	-1	0	1
6	0	0	0	0

↓

sx, sy, ex, ey = 3, 3, 5, 5

y x	1	2	3	4	5	6
0	0	0	0	0	0	0
1	1	0	0	-1	0	0
2	0	1	0	0	-1	0
3	0	0	1	0	0	-1
4	-1	0	0	1	0	0
5	0	-1	0	0	1	0
6	0	0	-1	0	0	1

↓

sx, sy, ex, ey = 1, 3, 3, 5

y x	1	2	3	4	5	6
0	0	0	0	0	0	0
1	1	0	0	-1	0	0
2	0	1	0	0	-1	0
3	1	0	1	-1	0	-1
4	-1	0	0	1	0	0
5	0	-1	0	0	1	0
6	-1	0	-1	1	0	1

↓

sx, sy, ex, ey = 3, 1, 5, 3

y x	1	2	3	4	5	6
0	0	0	0	0	0	0
1	1	0	1	-1	0	-1
2	0	1	0	0	-1	0
3	1	0	1	-1	0	-1
4	-1	0	-1	1	0	1
5	0	-1	0	0	1	0
6	-1	0	-1	1	0	1

↓ いもす法の処理完了

y x	1	2	3	4	5	6
0	0	0	0	0	0	0
1	1	0	1	-1	0	-1
2	0	1	0	0	-1	0
3	1	0	1	-1	0	-1
4	-1	0	-1	1	0	1
5	0	-1	0	0	1	0
6	-1	0	-1	1	0	1

いもす法の処理はここまでです。わけわかりませんね。😅

次に、いもす法で処理したものから二次元累積和をとると次のようになります。

for y in range(6):
    for x in range(6):
        cum_sum[y+1][x+1] = cum_sum[y][x+1] + cum_sum[y+1][x] - cum_sum[y][x] + cum_sum[y+1][x+1]

y x	1	2	3	4	5
0	0	0	0	0	0
1	1	1	2	1	1
2	1	2	3	2	1
3	2	3	`5`	3	2
4	1	2	3	2	1
5	1	1	2	1	1
6	0	0	0	0	0

↓ いもす法の処理後に付けた色をそのままに、行と列に分けて累積和をとってみます。問題のヒントにある二次元累積和の処理方法がこのやり方です。
変化を目で追って確認してみてください。

y x	1	2	3	4	5	6
0	0	0	0	0	0	0
1	1	0	1	-1	0	-1
2	0	1	0	0	-1	0
3	1	0	1	-1	0	-1
4	-1	0	-1	1	0	1
5	0	-1	0	0	1	0
6	-1	0	-1	1	0	1

行 →→→→→→→→→→→→→→→→→→→→→→→

y x	1	2	3	4	5
0	0	0	0	0	0
1	1	1	2	1	1
2	0	1	1	1	0
3	1	1	2	1	1
4	-1	-1	-2	-1	-1
5	0	-1	-1	-1	0
6	-1	-1	-2	-1	-1

列 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓

y x	1	2	3	4	5
0	0	0	0	0	0
1	1	1	2	1	1
2	1	2	3	2	1
3	2	3	5	3	2
4	1	2	3	2	1
5	1	1	2	1	1
6	0	0	0	0	0

y x	1	2	3	4	5
0	0	0	0	0	0
1	1	1	2	1	1
2	1	2	3	2	1
3	2	3	`5`	3	2
4	1	2	3	2	1
5	1	1	2	1	1
6	0	0	0	0	0

一致していることを確認してみてください。

いもす法の +1 と -1 の取り方がわかりにくいですよね。
+1 する所と -1 する４箇所は対角になっていますので、色の配置で覚えてしまいましょう。あとは添字に当てるだけです。

STEP: 2 2 次元上のいもす法 2

2 次元上のいもす法 2

cum_sum = [[0] * 7 for _ in range(7)]

sy, ey = 3, 3
for _ in range(5):
    sx, ex = map(int, input().split())
    cum_sum[sy][sx] += 1
    cum_sum[sy][ex+1] -= 1
    cum_sum[ey+1][sx] -= 1
    cum_sum[ey+1][ex+1] += 1
    
for y in range(6):
    for x in range(6):
        cum_sum[y+1][x+1] = cum_sum[y][x+1] + cum_sum[y+1][x] - cum_sum[y][x] + cum_sum[y+1][x+1]

max_= -float('inf')
for row in cum_sum:
    max_ = max(max_, max(row))

print(max_)

x の位置が入力で与えられます。y は 3 で固定されていますので、sy ey をそれぞれ 3 で初期化しておけば、変数を書き変えずに済みます。

STEP: 3 2 次元上のいもす法 3

2 次元上のいもす法 3

cum_sum = [[0] * 7 for _ in range(7)]

for _ in range(5):
    sx, sy, ex, ey = map(int, input().split())
    cum_sum[sy][sx] += 1
    cum_sum[sy][ex+1] -= 1
    cum_sum[ey+1][sx] -= 1
    cum_sum[ey+1][ex+1] += 1
    
for y in range(6):
    for x in range(6):
        cum_sum[y+1][x+1] = cum_sum[y][x+1] + cum_sum[y+1][x] - cum_sum[y][x] + cum_sum[y+1][x+1]

max_= -float('inf')
for row in cum_sum:
    max_ = max(max_, max(row))

print(max_)

位置がすべて入力で与えられるようになりました。それ以外変更はありません。

STEP: 4 2 次元上のいもす法 4

2 次元上のいもす法 4

N = int(input())
cum_sum = [[0] * 7 for _ in range(7)]

for _ in range(N):
    sx, sy, ex, ey = map(int, input().split())
    cum_sum[sy][sx] += 1
    cum_sum[sy][ex+1] -= 1
    cum_sum[ey+1][sx] -= 1
    cum_sum[ey+1][ex+1] += 1
    
for y in range(6):
    for x in range(6):
        cum_sum[y+1][x+1] = cum_sum[y][x+1] + cum_sum[y+1][x] - cum_sum[y][x] + cum_sum[y+1][x+1]

max_= -float('inf')
for row in cum_sum:
    max_ = max(max_, max(row))

print(max_)

今度は位置の数が N 個として与えられます。それだけです。

STEP: 5 2 次元上のいもす法 5

2 次元上のいもす法 5

N, K = map(int, input().split())
cum_sum = [[0] * (N+2) for _ in range(N+2)]

for _ in range(K):
    sx, sy, ex, ey = map(int, input().split())
    cum_sum[sy][sx] += 1
    cum_sum[sy][ex+1] -= 1
    cum_sum[ey+1][sx] -= 1
    cum_sum[ey+1][ex+1] += 1
    
for y in range(N+1):
    for x in range(N+1):
        cum_sum[y+1][x+1] = cum_sum[y][x+1] + cum_sum[y+1][x] - cum_sum[y][x] + cum_sum[y+1][x+1]

max_= -float('inf')
for row in cum_sum:
    max_ = max(max_, max(row))

print(max_)

マスの数が N 行 N 列となり、位置の数が K 個となっています。書き換えるべき箇所をよく見て書き換えましょう。

FINAL問題【2 次元上のいもす法】 2 次元上のいもす法 6

【2 次元上のいもす法】 2 次元上のいもす法 6

N, M, K = map(int, input().split())
cum_sum = [[0] * (M+2) for _ in range(N+2)]

for _ in range(K):
    sx, sy, ex, ey = map(int, input().split())
    cum_sum[sy][sx] += 1
    cum_sum[sy][ex+1] -= 1
    cum_sum[ey+1][sx] -= 1
    cum_sum[ey+1][ex+1] += 1
    
for y in range(N+1):
    for x in range(M+1):
        cum_sum[y+1][x+1] = cum_sum[y][x+1] + cum_sum[y+1][x] - cum_sum[y][x] + cum_sum[y+1][x+1]

max_= -float('inf')
for row in cum_sum:
    max_ = max(max_, max(row))

print(max_)

列(x) に当たる N を M に変えるだけです。

余力があるようでしたら、今度は上の１行と左の１列の 0 を作らない二次元リストで、行と列を別々にした二次元累積和を作るプログラムに作り変えてみましょう。STEP 1 の問題の説明にあったやり方です。
先頭に 0 を付けるのは、区間和を求める時などには有効ですが、今回の最大値を探して求めるだけの時には 0 は必要ありません。どんな場合でも行列やその変化がイメージできるようになるまでは先頭に 0 をつける方法がわかりやすいと思いますが、人それぞれなので自分なりにイメージしやすく組みやすい方法を見つけて取り入れてください。
私は後から見てすぐにわかる様、どんな場合もできるだけ「定型文」としたい派なので、この様な形の解説になりました。

しばらく使わないと忘れちゃいますからね！散々やってた得意なゲームを久しぶりにやったら下手になってるのと同じです。

【区間の数え上げ】区間の数え上げ 4

STEP: 1 区間の数え上げ 1

区間の数え上げ 1

しゃくとり法というアルゴリズムの学習です。これは私が長らく習得に苦戦したアルゴリズムで、あちこち調べたり ChatGPT に質問を変えながら理解しようと頑張って結局挫折し、しばらく放置していたら、その間なにもしていなかったにも関わらず、いつの間にか出来るようになっていたという謎のアルゴリズムです。

しゃくとり法と言っても多彩な使い方があり、多彩な書き方ができる為に、調べれば調べるほどにどの書き方がわかりやすいのかがわからなくなって混乱に陥った為かと思います。

ここで学習して、もし理解が難しければ私と同じルートを辿ってしまうかもしれません。

ここでは paiza の解説とは異なり、累積和を使って区間和を求めます。paiza の解説にあるような変数に区間和を保存していく方法ではなく、直接累積和から区間和を求めながらしゃくとりを進めていく方法ですが、その他の流れはほとんど同じです。

A = [1, 5, 9, 1, 20, 5, 3, 6, 5, 4]
len_A = len(A)

# 累積和をつくる
cum_sum = [0] * (len_A+1)
for i in range(len_A):
    cum_sum[i+1] = cum_sum[i] + A[i]

# しゃくとり法
r = 1
cnt = 0
for l in range(1, len_A+1):
    while r <= len_A and cum_sum[r] - cum_sum[l-1] <= 15:
        r += 1
    
    cnt += r - l
    if l == r:
        r += 1

print(cnt)

まずは累積和を前準備として作っておきます。作り方はこれまでと全く同じです。

A = [1, 5, 9, 1, 20, 5, 3, 6, 5, 4]
cum_sum = [0, 1, 6, 15, 16, 36, 41, 44, 50, 55, 59]

次にしゃくとり法です。初期値を含め、探索を以下の状態から開始します。

要素番号	0	1	2	3	4	5	6	7	8	9	10
l, r		lr
cum_sum	0	1	6	15	16	36	41	44	50	55	59

l はで、r はで位置を動かしていきます。この時点ではを過ぎ、の直前の所にいます。

for l in range(1, len_A+1):
    # >>> いまココ <<<
    while r <= len_A and cum_sum[r] - cum_sum[l-1] <= 15:
        r += 1

r <= len_A は、r が数列の中にいる間、ループします。
cum_sum[r] - cum_sum[l-1] <= 15 が、累積和で区間和を求めている所です。
数列A の先頭は、cum_sum の要素番号 1 なので、初期値は l = 1, r = 1 です。

cum_sum[1] - cum_sum[0] <= 15
↓
1 - 0 <= 15 … True

となり、True の間は r += 1 だけが実行されます。

要素番号	0	1	2	3	4	5	6	7	8	9	10
l, r		lr
cum_sum	0	1	6	15	16	36	41	44	50	55	59

1 - 0 = 1 … True
↓

要素番号	0	1	2	3	4	5	6	7	8	9	10
l, r		l	r
cum_sum	0	1	6	15	16	36	41	44	50	55	59

6 - 0 = 6 … True
↓

要素番号	0	1	2	3	4	5	6	7	8	9	10
l, r		l		r
cum_sum	0	1	6	15	16	36	41	44	50	55	59

15 - 0 = 15 … ギリ True
↓

要素番号	0	1	2	3	4	5	6	7	8	9	10
l, r		l			r
cum_sum	0	1	6	15	16	36	41	44	50	55	59

16 - 0 = 16 … False

15 以下ではなくなったのでここで False となり、文を抜けます。

ここで l と r の範囲が示す数列A を見てみます。(下記)
15 以下ではなくなった所が cum_sum の要素番号 4 です。ということは、15 以下の範囲は数列A の 1 ～ 3 番目です。

A = [1, 5, 9, 1, 20, 5, 3, 6, 5, 4]

これを踏まえて次は 15 以下の区間の個数を数えます。

cnt += r - l
if l == r:
    r += 1

現在、cnt = 0, l = 1, r = 4 となっています。
4 - 1 = 3 なので、cnt には 3 が加算されます。(現在 cnt = 3)
この 3 は 15 以下の区間の数ですが、その区間というのは次の３つです。

A = [1, 5, 9, 1, 20, 5, 3, 6, 5, 4]
[1]
[1, 5]
[1, 5, 9]

l == r ではないので次のループに移ります。

↓

要素番号	0	1	2	3	4	5	6	7	8	9	10
l, r			l		r
cum_sum	0	1	6	15	16	36	41	44	50	55	59

16 - 1 = 15 … True
↓

要素番号	0	1	2	3	4	5	6	7	8	9	10
l, r			l			r
cum_sum	0	1	6	15	16	36	41	44	50	55	59

36 - 1 = 25 … False
cnt += 5 - 2 = 3 (現在 cnt = 6)

A = [1, 5, 9, 1, 20, 5, 3, 6, 5, 4]
[5]
[5, 9]
[5, 9, 1]

↓

要素番号	0	1	2	3	4	5	6	7	8	9	10
l, r				l		r
cum_sum	0	1	6	15	16	36	41	44	50	55	59

36 - 6 = 30 … False
cnt += 5 - 3 = 2 (現在 cnt = 8)

A = [1, 5, 9, 1, 20, 5, 3, 6, 5, 4]
[9]
[9, 1]

要素番号	0	1	2	3	4	5	6	7	8	9	10
l, r					l	r
cum_sum	0	1	6	15	16	36	41	44	50	55	59

36 - 15 = 21 … False
cnt += 5 - 4 = 1 (現在 cnt = 9)

A = [1, 5, 9, 1, 20, 5, 3, 6, 5, 4]
[1]

要素番号	0	1	2	3	4	5	6	7	8	9	10
l, r						lr
cum_sum	0	1	6	15	16	36	41	44	50	55	59

36 - 16 = 20 … False
cnt += 5 - 5 = 0 (現在 cnt = 9)　うまくできてるね…(感心)
l == r なので r += 1 する。

要素番号	0	1	2	3	4	5	6	7	8	9	10
l, r							lr
cum_sum	0	1	6	15	16	36	41	44	50	55	59

41 - 36 = 5 … True

要素番号	0	1	2	3	4	5	6	7	8	9	10
l, r							l	r
cum_sum	0	1	6	15	16	36	41	44	50	55	59

44 - 36 = 8 … True

要素番号	0	1	2	3	4	5	6	7	8	9	10
l, r							l		r
cum_sum	0	1	6	15	16	36	41	44	50	55	59

50 - 36 = 14 … True

要素番号	0	1	2	3	4	5	6	7	8	9	10
l, r							l			r
cum_sum	0	1	6	15	16	36	41	44	50	55	59

55 - 36 = 19 … False
cnt += 9 - 6 = 3 (現在 cnt = 12)

A = [1, 5, 9, 1, 20, 5, 3, 6, 5, 4]
[5]
[5, 3]
[5, 3, 6]

要素番号	0	1	2	3	4	5	6	7	8	9	10
l, r								l		r
cum_sum	0	1	6	15	16	36	41	44	50	55	59

55 - 41 = 13 … True

要素番号	0	1	2	3	4	5	6	7	8	9	10
l, r								l			r
cum_sum	0	1	6	15	16	36	41	44	50	55	59

59 - 41 = 18 … False
cnt += 10 - 7 = 3 (現在 cnt = 15)

A = [1, 5, 9, 1, 20, 5, 3, 6, 5, 4]
[3]
[3, 6]
[3, 6, 5]

要素番号	0	1	2	3	4	5	6	7	8	9	10
l, r									l		r
cum_sum	0	1	6	15	16	36	41	44	50	55	59

59 - 44 = 14 … True

要素番号	0	1	2	3	4	5	6	7	8	9	10	11
l, r									l			r
cum_sum	0	1	6	15	16	36	41	44	50	55	59

r が数列を超えたので False
cnt += 11 - 8 = 3 (現在 cnt = 18)

A = [1, 5, 9, 1, 20, 5, 3, 6, 5, 4]
[6]
[6, 5]
[6, 5, 4]

要素番号	0	1	2	3	4	5	6	7	8	9	10	11
l, r										l		r
cum_sum	0	1	6	15	16	36	41	44	50	55	59

r が数列を超えているので False
cnt += 11 - 9 = 2 (現在 cnt = 20)

A = [1, 5, 9, 1, 20, 5, 3, 6, 5, 4]
[5]
[5, 4]

要素番号	0	1	2	3	4	5	6	7	8	9	10	11
l, r											l	r
cum_sum	0	1	6	15	16	36	41	44	50	55	59

r が数列を超えているので False
cnt += 11 - 10 = 1 (現在 cnt = 21)

A = [1, 5, 9, 1, 20, 5, 3, 6, 5, 4]
[4]

ここでループが終了し、最後に cnt を画面に出力して完了です。

カウントした分の範囲をかき集めてみると、きちんと 21個あります。

1: [1]
2: [1, 5]
3: [1, 5, 9]
4: [5]
5: [5, 9]
6: [5, 9, 1]
7: [9]
8: [9, 1]
9: [1]
10: [5]
11: [5, 3]
12: [5, 3, 6]
13: [3]
14: [3, 6]
15: [3, 6, 5]
16: [6]
17: [6, 5]
18: [6, 5, 4]
19: [5]
20: [5, 4]
21: [4]

処理の流れを全部書いてしまったせいで長くなりましたけど、わかりましたでしょうか？と、私自身理解できなかった期間が長かった上に何で急に理解できるようになったのかがわからないせいもあり、これでわかってもらえるかどうかが全然わかりません。😓
せめて理解に繋がったきっかけでもあればよかったのですがそれも無く、既に理解して吸収してしまっているのでわからなかった時に何でわからなかったのかももうわかりません。😅 自転車に乗る練習みたいな感じです。

累積和はほぼ定型文ですが、しゃくとり法はこれがわからないと応用が利きません、使いどころに気付きもしません。ですので今はわからなくても、気持ちだけは諦めずに時々しゃくとり法のことを思い出してみてください。

わかってもわからなくても、とりあえずこのプログラム例をメモして次の問題へ進んでみてください。わからない場合でも、やらないよりはやったほうがいいですよ。😊

STEP: 2 区間の数え上げ 2

A = list(map(int, input().split()))
len_A = len(A)

cum_sum = [0] * (len_A+1)
for i in range(len_A):
    cum_sum[i+1] = cum_sum[i] + A[i]

r = 1
cnt = 0
for l in range(1, len_A+1):
    while r <= len_A and cum_sum[r] - cum_sum[l-1] <= 15:
        r += 1
    
    cnt += r - l
    if l == r:
        r += 1

print(cnt)

数列が入力値として与えられただけです。

STEP: 3 区間の数え上げ 3

区間の数え上げ 3

K = int(input())
A = list(map(int, input().split()))
len_A = len(A)

cum_sum = [0] * (len_A+1)
for i in range(len_A):
    cum_sum[i+1] = cum_sum[i] + A[i]

r = 1
cnt = 0
for l in range(1, len_A+1):
    while r <= len_A and cum_sum[r] - cum_sum[l-1] <= K:
        r += 1
    
    cnt += r - l
    if l == r:
        r += 1

print(cnt)

15 以下が入力値 K として与えられましたので、15 を K に書き換えましょう。

FINAL問題【区間の数え上げ】区間の数え上げ 4

【区間の数え上げ】区間の数え上げ 4

N, K = map(int, input().split())
A = list(map(int, input().split()))

cum_sum = [0] * (N+1)
for i in range(N):
    cum_sum[i+1] = cum_sum[i] + A[i]

r = 1
cnt = 0
for l in range(1, N+1):
    while r <= N and cum_sum[r] - cum_sum[l-1] <= K:
        r += 1
    
    cnt += r - l
    if l == r:
        r += 1

print(cnt)

しゃくとり法の書き方としては、どんな時もまず while r <= N と『 r が数列の中にいるうちは』という一文を書きます。
and で繋ぎ、その後に問題の条件を書きます。条件は様々ですが、ここに与えられた条件を書けば大体オッケーなはずです。

のループを抜けた後が様々で、条件次第で書き方が全く変わります。こことの条件式が連動しています。この２つに注目すれば……いずれ理解に繋がるんじゃないかな？😅

【区間の長さ】区間の長さ 4

STEP: 1 区間の長さ 1

区間の長さ 1

A = [1, 5, 9, 1, 20, 5, 3, 6, 5, 4]
len_A = len(A)

# 累積和をつくる
cum_sum = [0] * (len_A+1)
for i in range(len_A):
    cum_sum[i+1] = cum_sum[i] + A[i]

# しゃくとり法
r = 1
max_length = -float('inf')
for l in range(1, len_A+1):
    while r <= len_A and cum_sum[r] - cum_sum[l-1] <= 15:
        r += 1
    
    max_length = max(max_length, r - l)
    if l == r:
        r += 1

print(max_length)

１つ前の「【区間の数え上げ】区間の数え上げ 4」の「区間の数え上げ 1」がまだの方は、そちらを先に修了してください。

今度は区間の個数から「区間の長さ」になりました。ただ、与えられた条件が全く同じですので、前回のプログラムを少し書き換えるだけで問題がクリアできます。
最大の長さというくらいですから max() 関数を使うだろうということはピンときたでしょう。それがわかれば自ずと上記のプログラムの通りになるはずです。

STEP: 2 区間の長さ 2

区間の長さ 2

A = list(map(int ,input().split()))
len_A = len(A)

cum_sum = [0] * (len_A+1)
for i in range(len_A):
    cum_sum[i+1] = cum_sum[i] + A[i]

r = 1
max_length = -float('inf')
for l in range(1, len_A+1):
    while r <= len_A and cum_sum[r] - cum_sum[l-1] <= 15:
        r += 1
    
    max_length = max(max_length, r - l)
    if l == r:
        r += 1

print(max_length)

数列が入力値として与えられますので、その数列を使います。

STEP: 3 区間の長さ 3

区間の長さ 3

K = int(input())
A = list(map(int ,input().split()))
len_A = len(A)

cum_sum = [0] * (len_A+1)
for i in range(len_A):
    cum_sum[i+1] = cum_sum[i] + A[i]

r = 1
max_length = -float('inf')
for l in range(1, len_A+1):
    while r <= len_A and cum_sum[r] - cum_sum[l-1] <= K:
        r += 1
    
    max_length = max(max_length, r - l)
    if l == r:
        r += 1

print(max_length)

入力値 K が与えられましたので、15 を K に書き換えるだけです。👍

FINAL問題【区間の長さ】区間の長さ 4

【区間の長さ】区間の長さ 4

N, K = map(int ,input().split())
A = list(map(int ,input().split()))

cum_sum = [0] * (N+1)
for i in range(N):
    cum_sum[i+1] = cum_sum[i] + A[i]

r = 1
max_length = -float('inf')
for l in range(1, N+1):
    while r <= N and cum_sum[r] - cum_sum[l-1] <= K:
        r += 1
    
    max_length = max(max_length, r - l)
    if l == r:
        r += 1

print(max_length)

大変長らくお疲れさまでした。

y x	1	2	4	5
0	0	0	0	0
1	1	0	-1	0
2	0	1	0	-1
3	0	0	0	0
4	-1	0	1	0
5	0	-1	0	1
6	0	0	0	0

y x	1	2	3	4	5	6
0	0	0	0	0	0	0
1	1	0	0	-1	0	0
2	0	1	0	0	-1	0
3	0	0	1	0	0	-1
4	-1	0	0	1	0	0
5	0	-1	0	0	1	0
6	0	0	-1	0	0	1

y x	1	2	3	4	5	6
0	0	0	0	0	0	0
1	1	0	0	-1	0	0
2	0	1	0	0	-1	0
3	1	0	1	-1	0	-1
4	-1	0	0	1	0	0
5	0	-1	0	0	1	0
6	-1	0	-1	1	0	1

y x	1	2	3	4	5	6
0	0	0	0	0	0	0
1	1	0	1	-1	0	-1
2	0	1	0	0	-1	0
3	1	0	1	-1	0	-1
4	-1	0	-1	1	0	1
5	0	-1	0	0	1	0
6	-1	0	-1	1	0	1

y x	1	2	3	4	5	6
0	0	0	0	0	0	0
1	1	0	1	-1	0	-1
2	0	1	0	0	-1	0
3	1	0	1	-1	0	-1
4	-1	0	-1	1	0	1
5	0	-1	0	0	1	0
6	-1	0	-1	1	0	1

y x	1	2	3	4	5	6
0	0	0	0	0	0	0
1	1	0	1	-1	0	-1
2	0	1	0	0	-1	0
3	1	0	1	-1	0	-1
4	-1	0	-1	1	0	1
5	0	-1	0	0	1	0
6	-1	0	-1	1	0	1

y x	1	2	3	4	5
0	0	0	0	0	0
1	1	1	2	1	1
2	0	1	1	1	0
3	1	1	2	1	1
4	-1	-1	-2	-1	-1
5	0	-1	-1	-1	0
6	-1	-1	-2	-1	-1

y x	1	2	4	5
0	0	0	0	0
1	1	0	-1	0
2	0	1	0	-1
3	0	0	0	0
4	-1	0	1	0
5	0	-1	0	1
6	0	0	0	0

y x	1	2	3	4	5	6
0	0	0	0	0	0	0
1	1	0	0	-1	0	0
2	0	1	0	0	-1	0
3	0	0	1	0	0	-1
4	-1	0	0	1	0	0
5	0	-1	0	0	1	0
6	0	0	-1	0	0	1

y x	1	2	3	4	5	6
0	0	0	0	0	0	0
1	1	0	0	-1	0	0
2	0	1	0	0	-1	0
3	1	0	1	-1	0	-1
4	-1	0	0	1	0	0
5	0	-1	0	0	1	0
6	-1	0	-1	1	0	1

y x	1	2	3	4	5	6
0	0	0	0	0	0	0
1	1	0	1	-1	0	-1
2	0	1	0	0	-1	0
3	1	0	1	-1	0	-1
4	-1	0	-1	1	0	1
5	0	-1	0	0	1	0
6	-1	0	-1	1	0	1

y x	1	2	3	4	5	6
0	0	0	0	0	0	0
1	1	0	1	-1	0	-1
2	0	1	0	0	-1	0
3	1	0	1	-1	0	-1
4	-1	0	-1	1	0	1
5	0	-1	0	0	1	0
6	-1	0	-1	1	0	1

y x	1	2	3	4	5	6
0	0	0	0	0	0	0
1	1	0	1	-1	0	-1
2	0	1	0	0	-1	0
3	1	0	1	-1	0	-1
4	-1	0	-1	1	0	1
5	0	-1	0	0	1	0
6	-1	0	-1	1	0	1

y x	1	2	3	4	5
0	0	0	0	0	0
1	1	1	2	1	1
2	0	1	1	1	0
3	1	1	2	1	1
4	-1	-1	-2	-1	-1
5	0	-1	-1	-1	0
6	-1	-1	-2	-1	-1

y x	1	2	4	5
0	0	0	0	0
1	1	0	-1	0
2	0	1	0	-1
3	0	0	0	0
4	-1	0	1	0
5	0	-1	0	1
6	0	0	0	0

y x	1	2	3	4	5	6
0	0	0	0	0	0	0
1	1	0	0	-1	0	0
2	0	1	0	0	-1	0
3	0	0	1	0	0	-1
4	-1	0	0	1	0	0
5	0	-1	0	0	1	0
6	0	0	-1	0	0	1

y x	1	2	3	4	5	6
0	0	0	0	0	0	0
1	1	0	0	-1	0	0
2	0	1	0	0	-1	0
3	1	0	1	-1	0	-1
4	-1	0	0	1	0	0
5	0	-1	0	0	1	0
6	-1	0	-1	1	0	1

y x	1	2	3	4	5	6
0	0	0	0	0	0	0
1	1	0	1	-1	0	-1
2	0	1	0	0	-1	0
3	1	0	1	-1	0	-1
4	-1	0	-1	1	0	1
5	0	-1	0	0	1	0
6	-1	0	-1	1	0	1

y x	1	2	3	4	5	6
0	0	0	0	0	0	0
1	1	0	1	-1	0	-1
2	0	1	0	0	-1	0
3	1	0	1	-1	0	-1
4	-1	0	-1	1	0	1
5	0	-1	0	0	1	0
6	-1	0	-1	1	0	1

y x	1	2	3	4	5	6
0	0	0	0	0	0	0
1	1	0	1	-1	0	-1
2	0	1	0	0	-1	0
3	1	0	1	-1	0	-1
4	-1	0	-1	1	0	1
5	0	-1	0	0	1	0
6	-1	0	-1	1	0	1

y x	1	2	3	4	5
0	0	0	0	0	0
1	1	1	2	1	1
2	0	1	1	1	0
3	1	1	2	1	1
4	-1	-1	-2	-1	-1
5	0	-1	-1	-1	0
6	-1	-1	-2	-1	-1