冬期講習 2026-2027、募集中。総復習は売りません。90分×完全1対1で、穴だけを塞ぎます 詳しく →
電話 0422-27-7828チャットで質問無料相談を予約

武蔵野個別指導塾の特徴

共通テスト情報I 累積和の起点—最初の要素より前の値から区間の差を確かめる|武蔵野個別指導塾

学習のイメージ写真 武蔵野個別指導塾
X LINE Facebook

色タイルの区間を例に、先頭より前の0と負の添字の違いをたどり、差が表す範囲を読み解く累積和です。

よくあるのは、高校生が横一列の色タイルに書かれた数を区間ごとに合計しようとして、先頭のタイルより前の値を配列の末尾から取る場面です。途中から始まる区間では、左端より前までの合計を引けばよさそうです。しかし、先頭から始まるときに「その一つ前」を添字 -1 とすると、Pythonでは末尾の要素を参照します。存在しない先頭前のタイルを指すわけではありません。

先頭の前までにはタイルが何枚あるのかを数えると、区間の両端を同じ規則で扱えます。以下のタイルの値、プログラム、問題はすべて説明のための自作です。累積表の作成と区間の差に絞り、作成後の元データの変更は扱いません。

どこからどこまでを引くのか

問題の型には、まず元の並びから累積表を完成させるものがあります。このとき累積表の添字は、最後に加えたタイルの番号ではなく、先頭から加えた枚数を表します。最初の 0 が表のどの場所にあるかを読むことが出発点です。

次に、指定された区間を累積表の差で求める型があります。ここでは区間の記号 [l, r) を、左端 l を含み、右端 r を含まない範囲と定めます。元の並びの添字は 0 から始め、区間に入るのは l から r − 1 までです。r は最後のタイルの番号ではなく、その次の境目です。l と r が等しいときは空の区間で、合計を 0 とします。

もう一つは、起点を取り違えた式の結果を比べる型です。先頭からの区間だけでなく途中の区間も試すと、たまたま合う場合と、規則として正しい場合を分けられます。問題文に累積表の定義があれば、慣れた式を先に当てはめず、その表の各値が何個分かを確認します。

枚数を境目に対応させる

元の整数の並びを A とし、その長さを n とします。ここで作る累積表 P は n + 1 個の値を持ち、P[0] = 0 です。0 個のタイルの合計が 0 なので、この値は先頭の前の境目に対応します。k が 0 から n − 1 のとき、P[k + 1] = P[k] + A[k] とします。したがって P[k + 1] は先頭から k + 1 個の合計です。

図1のように、各タイルの右側に「そこまでに数えた枚数」を置きます。P の番号はタイル上ではなく境目の番号です。たとえば P[3] は先頭から 3 個の合計で、A[3] 自体を含む合計ではありません。P[3] に A[3] を加えたものが P[4] です。

図1 タイルの境目と累積値の添字の対応

[l, r) の合計は P[r] − P[l] です。P[r] に含まれる先頭 r 個から、P[l] に含まれる先頭 l 個を除くと、添字 l から r − 1 の部分が残るためです。両方に共通する部分を一度ずつ差し引くので、タイルの値に負の数や 0 があっても成り立ちます。値が増える並びである必要はありません。

累積表の各値だけを見て区間を想像すると、左側に何が残るかを見落としがちです。P[r] と P[l] の両方に入る先頭 l 個を指で覆い、残ったタイルを確認してください。たとえば左端が 0 なら覆うタイルはなく、左端が 2 なら最初の 2 個を除きます。左の境目自身をタイルとして除くわけではありません。

境目は 0 から n まであり、ここで扱う区間の条件は 0 <= l <= r <= n です。先頭からの区間なら l = 0 として P[0] を引きます。最後まで含む区間なら r = n として P[n] を使います。P[n] は存在しますが、A[n] は存在しません。空の元の並びでも P は [0] となり、許される区間 [0, 0) の合計は 0 です。

基本例題:先頭からの区間を追う

4 枚の色タイルの値を、左から A = [4, 2, 5, 3] とします。添字は左から 0, 1, 2, 3 です。P[0] = 0 から累積表を作り、区間 [0, 3) の合計を整数で答えてください。この区間は添字 0, 1, 2 のタイルを含みます。

次の Python のプログラムは表を作り終えた後に P と区間の合計を出力します。P は累積値の並び、k は今加えるタイルの添字、l と r は区間の境目です。

A = [4, 2, 5, 3]
P = [0]
k = 0
while k < len(A):
    P.append(P[k] + A[k])
    k = k + 1
l = 0
r = 3
print(P)
print(P[r] - P[l])
判定時の k k < 4 加える値 追加後の P 更新後の k
0 真 4 [0, 4] 1
1 真 2 [0, 4, 6] 2
2 真 5 [0, 4, 6, 11] 3
3 真 3 [0, 4, 6, 11, 14] 4
4 偽 なし [0, 4, 6, 11, 14] 更新なし

最初の判定が真なので、P[0] の 0 と A[0] の 4 から P[1] に 4 を追加し、その後 k を 1 にします。次は P[1] の 4 に A[1] の 2 を加えて 6、さらに 6 に 5 を加えて 11、最後に 11 に 3 を加えて 14 です。k が 4 になった判定は偽で、追加も更新も行いません。

出力は [0, 4, 6, 11, 14] と 11 です。図2のように、右の境目 P[3] は 11、左の境目 P[0] は 0 です。差は 11 − 0 = 11 となります。元のタイルに戻しても 4 + 2 + 5 = 11 で、最後の 3 は区間の外です。

図2 先頭から3枚の累積値と区間の差

最後の要素まで含めたいなら右の境目を 4 に変えます。P[4] − P[0] = 14 であり、右端 3 の場合とは最後のタイル 3 の分だけ違います。右端を含まない約束を保ったまま、目的のタイルがどこまで入るかを見ます。

標準例題:途中から最後まで

別の並び A = [7, -2, 6, 1, 4] を考えます。左からの添字は 0 から 4、P は先ほどと同じ定義です。区間 [1, 5) の合計と累積表をそれぞれ答えてください。左端 1 は含み、右端 5 は含まないので、添字 1, 2, 3, 4 が対象です。

P の追加順は 0 から始めて 7, 5, 11, 12, 16 です。したがって P = [0, 7, 5, 11, 12, 16] となり、求める値は P[5] − P[1] = 16 − 7 = 9 です。対象のタイルを直接足しても -2 + 6 + 1 + 4 = 9 です。負の値で P[2] は P[1] より小さくなりますが、差が区間を残す理由は変わりません。

もし右端を 4 に変更すれば対象は添字 1, 2, 3 です。P[4] − P[1] = 12 − 7 = 5 となり、最後の値 4 が入らなくなります。P[5] と A[5] は同じものではなく、前者は 5 個を数えた境目、後者はこの並びの外です。区間を絵に戻して検算すれば、式の添字がずれたかを見分けられます。

発展例題:空の区間と1枚の区間

展示用の別の列 A = [8, -3, 2] に対して同じ P を作ります。[2, 2) と [2, 3) の合計をそれぞれ整数で求めてください。前者は左端と右端が同じ境目、後者は添字 2 のタイルだけを含みます。

P は [0, 8, 5, 7] です。[2, 2) では P[2] − P[2] = 0、[2, 3) では P[3] − P[2] = 7 − 5 = 2 です。元の列に戻ると、空の区間には加える値がなく、もう一方には値 2 のタイルが 1 枚あります。両者は左端だけでなく右端まで読むことで区別できます。

さらに元の列が空なら、表の作成時に追加するタイルがなく P = [0] です。[0, 0) には P[0] − P[0] を使えます。これは先頭や末尾のタイルが 0 という意味ではなく、選んだタイルがないという意味です。区間の条件を外れる境目は、この式の対象として扱いません。

誤答はどの境目からずれるか

先頭からの区間を求めるとき、左側の差し引きに「左端の一つ前」を使うつもりで P[l − 1] と書く誤りを考えます。基本例題の P = [0, 4, 6, 11, 14]、区間 [0, 3) で比べます。Python の P[-1] は P の末尾 14 なので、誤った式 P[3] − P[-1] は 11 − 14 = -3 です。図3のように、最初に食い違うのは引く値を選ぶところです。

図3 先頭の区間で引く値を取り違える比較
式の読み方 右の値 引く値 結果 対象の 3 枚との対応
P[3] − P[0] 11 0 11 4, 2, 5 の合計
P[3] − P[-1] 11 14 -3 末尾までの合計を引いている

原因は P の番号をタイルの番号と同じ意味にしたことです。P[0] は先頭のタイルではなく、その前までの合計です。Python の負添字は末尾からの参照として働くため、先頭の前の空の部分を表す代用品にはなりません。修正は P[l − 1] を P[l] に戻し、P[r] − P[l] とすることです。

途中からの区間でも誤りを確かめます。基本例題の [1, 3) は値 2 と 5 なので 7 です。正しい式は P[3] − P[1] = 11 − 4 = 7、誤った式は P[3] − P[0] = 11 で、先頭の 4 が余分に残ります。一方、先頭の値が 0 ならこの途中区間では二つの式が偶然一致します。1 例の一致だけでは式の正しさを保証できません。

ここで結果が負になったこと自体を誤りの判定基準にはしません。元の値に負の数があれば正しい区間和も負になり得ます。判断の根拠は、引いた 14 が選択区間より左の合計ではなく、列全体の合計であることです。元のタイルの位置に戻れば、符号だけに頼らず原因を説明できます。

また、P[0] を省いて作った表に同じ式を適用しても、添字の意味が一つずれます。先に表の長さと初期値を確認し、P[1] が 1 個分か 2 個分かを一行目から確定させます。式の形が似ていても、表の定義が違えば同じ結果になるとは限りません。

別の構造の累積表では、最後に含めた要素の添字を番号に使うこともあります。その場合の式をここへ移す前に、先頭より前の合計をどう表すかまで確認してください。この例の P には最初から 0 があり、その 0 を特別な負添字に置き換える必要はありません。

練習:境目を選んで差を取る

次の 5 問はそれぞれ独立した自作の条件です。元の整数の並びの添字は 0 から始め、P[0] = 0、P[k + 1] = P[k] + A[k] とします。区間 [l, r) は l を含み r を含みません。答えは指定された形で書いてください。

  1. 本の箱に付いた数が A = [3, 9, 1, 6] のとき、累積表 P を配列で、[0, 2) の合計を整数で答えてください。
  2. 水位の変化を表す数が A = [-4, 10, -1] のとき、[1, 3) の合計を整数で答えてください。
  3. 空の棚を A = [] とします。P を配列で、[0, 0) の合計を整数で答えてください。
  4. 印の数が A = [12] のとき、[0, 1) と [1, 1) の合計をこの順に整数で答えてください。
  5. 列 A = [2, 0, 13] の [0, 2) を求めるとき、正しい P[r] − P[l] と誤った P[r] − P[l − 1] の結果をこの順に整数で答えてください。負添字は Python の規則で読みます。

解答と確かめ方

  1. P = [0, 3, 12, 13, 19]、合計は 12 です。先頭から 2 個の境目は P[2] = 12、開始前は P[0] = 0 です。元の箱に戻すと 3 と 9 の合計で、後ろの 1 と 6 は入りません。
  2. P = [0, -4, 6, 5] なので、P[3] − P[1] = 5 − (-4) = 9 です。対象は添字 1 と 2 の 10 と -1 で、その和も 9 です。負の累積値を引くときの符号まで追います。
  3. P = [0]、合計は 0 です。追加処理は一度も動かず、P[0] − P[0] となります。空の棚には先頭の品も末尾の品もなく、0 は空の合計です。
  4. P = [0, 12] です。[0, 1) は P[1] − P[0] = 12、[1, 1) は P[1] − P[1] = 0 です。前者には唯一の印が入り、後者には入りません。右端を含めると空の区間を誤読します。
  5. P = [0, 2, 2, 15] です。正しい結果は P[2] − P[0] = 2、誤った結果は P[2] − P[-1] = 2 − 15 = -13 です。対象は最初の 2 個の 2 と 0 なので 2 です。P[-1] は 15 を取り、先頭前の 0 にはなりません。

覚えておくこと

追跡表のどの列を見るか

答えが合わないときは、まず P の各番号の下に「何個分か」を書いてもらい、P[0] を最初のタイルの値としていないかを見ます。次に、区間の左と右に対応する境目の列を別々に確認します。右端をタイルの番号と読む誤りと、左端の手前をもう一度引く誤りは、違う列に最初のずれが現れます。

個別指導では、先頭からの区間、途中からの区間、空の区間を並べ、本人が指定したタイルを直接足した結果と表の差を照合します。お子さまが正しい結果を出せた場合も、どの境目を引いたかを説明できるか確かめます。累積和の起点は、選んだ区間を過不足なく残すための境目です。

もう「日東駒専」を目標にしないでください。

武蔵境駅徒歩30秒、講師1人に生徒1人の完全1対1。授業のあいだ、先生は隣を離れません。いまの詰まりを、無料相談でそのまま話してください。

まず15分だけ電話で話したい方は、無料電話相談(15分)から。塾からお電話を差し上げます。

本気になった日が、入塾の日。

お子様の教育、迷ったら「丸投げ」してください。必ず、期待以上の結果で返します。武蔵野で育む、武蔵境で学ぶ。

電話は年中無休。365日、24時間、お電話可能。

チャットで質問チャット
無料相談を予約する 電話 0422-27-7828電話 LINE チャット
で質問