科目Bの累積和問題の解き方｜途中までの合計を配列にためて追う

s[r + 1] − s[l] の + 1 がどこから来たのか、何度見ても腑に落ちない。

科目Bの問題で、合計を配列にためておくコードを見たとき、引き算の添字で手が止まったことはありませんか？

合計の求め方は分かる。それなのに、区間の合計を引き算で出す形になると、急に1つずれた答えを選んでしまう人は多いのではないでしょうか。

大丈夫です。累積和の問題で必要なのは、ためていく配列を1つずつ表に書くことと、引き算で残る範囲を小さな例で確かめることだけです。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。実務でも、日ごとの売上やアクセス数を集計して、任意の期間の合計をすばやく返す処理を何度も書いています。

そのとき、期間の初日を合計に含め忘れて、毎回1日分少ない数字を出すコードを作りかけたことがあります。気づけたのは、3日分だけの小さなデータで、手計算の合計と突き合わせたからでした。

この記事では、累積和の問題を、科目Bの解き方に合わせて5つの段階で紹介します。科目B全体の中でこうした問題がどんな位置にあるのかを先に確かめたい人は、親記事から読んでおくと流れがつかみやすくなります。

【関連記事】基本情報技術者試験の科目Bとは？擬似言語・アルゴリズム対策を初心者向けに解説

累積和の問題は何を聞いているのか¶

最初に、累積和とは何かを短く押さえておきましょう。名前は難しそうですが、やっていることは足し算を少しずつ進めて、途中経過をメモしておくだけです。

累積和とは、先頭からある位置までの合計を、位置ごとに記録した配列のことです。{4, 2, 7} の累積和なら、4、6、13 のように、1つ進むたびに合計が増えていきます。

この途中経過をためておくと、ある区間の合計を、引き算1回で求められるようになります。2番目から3番目の合計なら、3番目までの合計 13 から、1番目までの合計 4 を引いて 9 です。

科目Bで問われる形¶

試験の擬似言語で累積和が出るときは、考え方そのものよりも、添字の式がどう書かれているかが問われます。どんな形で聞かれやすいのかを、表に整理しました。

どの形でも、中心にあるのは、ためていく行と引き算する行の2つです。この2つの添字を小さな例で確かめられれば、問われ方が変わっても同じ手順で解けます。

合計を求める問題との違い¶

配列の合計を1つの変数に足していく処理は、科目Bの定番です。累積和は、その足していく途中の値を捨てずに、配列に全部残しておく形だと考えると分かりやすくなります。

普通の合計では、最後に1つの値が残ります。累積和では、位置ごとの途中経過がすべて残るので、あとから好きな区間の合計を取り出せるのが違いです。

合計を変数にためていく書き方そのものに不安がある場合は、こちらの記事で先に整理しておくと読みやすくなります。

【関連記事】擬似言語の合計・最大値・件数の求め方｜科目Bで頻出の集計パターンを解説

まず目を付ける場所¶

累積和が何かつかめたら、次はコードのどこから読むかを決めます。累積和の問題では、目を付ける場所が3つあります。

ひとつ目は累積配列の要素数、ふたつ目は配列をためていく行、みっつ目は区間の合計を引き算で出す行です。この3か所が分かれば、添字のずれをほぼ見抜けます。

累積配列の要素数は元より1つ多いか¶

最初に確かめたいのが、累積配列 s の要素数です。元の配列 a が n 個のとき、s が n 個なのか n + 1 個なのかで、あとの式がすべて変わります。

科目Bでよく見るのは、s を n + 1 個にして、s[1] に 0 を入れておく形です。s[1] は何も足していない合計、s[2] は a[1] までの合計、s[i + 1] は a[i] までの合計という対応になります。

なぜ、わざわざ1つ多く作るのでしょうか？ 先頭から始まる区間を引き算で求めるとき、引く相手として何も足していない 0 が必要になるからです。

ためていく行は1つ前に足す¶

次に探すのが、s[i + 1] ← s[i] ＋ a[i] のように、1つ前の合計に今の要素を足している行です。この1行が、累積和の作り方のすべてです。

右辺の s[i] は、a[i − 1] までの合計です。そこに a[i] を足すので、左辺には a[i] までの合計が入ります。

左辺と右辺で s の添字が1つずれているのは、この対応を保つためです。添字が同じ s[i] ← s[i] ＋ a[i] のような選択肢は、前の合計を引き継げていないので誤りになります。

引き算の行は残したい範囲で確かめる¶

最後に見るのが、区間の合計を返す行です。s[r + 1] − s[l] のように、2つの累積値を引き算しています。

s[r + 1] は a[r] までの合計、s[l] は a[l − 1] までの合計です。大きいほうから小さいほうを引くと、a[l] から a[r] までが残ります。

冒頭の + 1 の正体は、累積配列が元の配列より1つ後ろにずれていることでした。ここが腑に落ちると、引き算の式で迷うことがぐっと減ります。

例題：累積配列を作って区間の合計を返す¶

ここからは、実際の例題で追い方を確かめます。この記事の例題は説明のために作成したもので、IPA の公開問題そのものではありません。

次のプログラムは、整数型の配列 a から累積配列 s を作る手続と、a[l] から a[r] までの合計を返す関数です。配列の添字は1から始まり、s の要素数は a の要素数より1つ多いものとします。

○makePrefix(整数型の配列: a, 整数型の配列: s)
  整数型: n ← a の要素数
  整数型: i
  s[1] ← 0
  for (i を 1 から n まで 1 ずつ増やす)
    s[i + 1] ← s[i] ＋ a[i]
  endfor

○整数型: rangeSum(整数型の配列: s, 整数型: l, 整数型: r)
  return s[r + 1] − s[l]

makePrefix は、先頭から順に合計を足していき、その途中経過を s に1つずつ書き込みます。rangeSum は、できあがった s から2つの値を取り出して引き算するだけで、ループを1つも使いません。

では、a が {4, 2, 7, 1, 5, 3} のとき、rangeSum(s, 2, 5) の戻り値は何になるでしょうか？

トレース表で途中までの合計を追う¶

頭の中だけで足し算を続けると、いまどこまで足したのかが分からなくなりがちです。そこで、ループ1回ごとに、足す要素と、書き込む位置と、その値をトレース表に書きます。

ポイントは、書き込む位置の列と、その値が何番目までの合計なのかの列を分けることです。こうしておくと、s の添字と a の添字が1つずれている様子が一目で分かります。

できあがった s は {0, 4, 6, 13, 14, 19, 22} です。最後の 22 が、a 全体の合計と一致していることも確かめておきましょう。

次に rangeSum(s, 2, 5) を計算します。s[5 + 1] − s[2] で 19 − 4 となり、戻り値は 15 です。

答えが合っているか不安なときは、a を直接足して確かめましょう。a[2] から a[5] までは 2、7、1、5 で、足すと 15 になるので、正しく計算できています。

トレース表の書き方そのものに慣れていない場合は、こちらの記事で基本から確認できます。

【関連記事】擬似言語のトレース表の書き方｜科目Bで変数の値を追う手順を解説

先頭から始まる区間で 0 が効く¶

今度は rangeSum(s, 1, 3) を考えてみましょう。a[1] から a[3] までの合計なので、答えは 4 ＋ 2 ＋ 7 で 13 のはずです。

式に当てはめると、s[4] − s[1] で 13 − 0 となり、ちゃんと 13 が返ります。s[1] に 0 を入れておいたおかげで、先頭から始まる区間も同じ式で扱えるわけです。

もし s を n 個で作り、s[1] に a[1] を入れる形にしていたら、先頭の区間では s[0] を引く必要が出てきます。1始まりの配列には0番目がないので、そこで式が破綻してしまいます。

一定の幅の合計を順に求める¶

累積和は、一定の幅の合計を順番に求める問題でもよく使われます。たとえば、連続する3個の合計を、先頭から順にすべて求めるような場面です。

幅が3なら、i 番目から始まる3個の合計は s[i + 3] − s[i] で求まります。i を1つずつ増やしていけば、ループの中では毎回引き算を1回するだけです。

例題の a なら、i が 1 のときは s[4] − s[1] で 13、i が 2 のときは s[5] − s[2] で 10 になります。毎回3個を足し直すよりも、手順がずっと少なくて済むことが分かります。

間違いやすい選択肢の見分け方¶

累積和の問題では、引き算の添字を1つだけずらした選択肢が並びます。どんな誤りが用意されやすいのかを知っておけば、選択肢を見た瞬間に候補を絞れます。

例題の a と、l が 2、r が 5 の場合を使って、よくある誤りを表にまとめました。

正解の 15 に対して、10 や 13 のように近い数字が選択肢に並ぶのがこの種の問題の特徴です。計算結果だけ見て選ぶと、うっかり近い数字に飛びついてしまいます。

長さ1の区間で式を試す¶

引き算の式で迷ったら、l と r を同じ値にしてみてください。a[3] から a[3] までの合計は、a[3] そのものの 7 になるはずです。

正しい式なら、s[4] − s[3] で 13 − 6 となり、7 が返ります。s[r] − s[l] の形だと、s[3] − s[3] で 0 になってしまうので、すぐに誤りだと分かります。

長さ1の区間は、答えが元の配列を見るだけで分かる、いちばん確かめやすい入力です。選択肢ごとに1回試すだけで、ずれた式をほとんど落とせます。

二重ループとの違いは計算量で見る¶

累積和を使わずに、l から r までを毎回足し直すコードが選択肢に並ぶこともあります。これは答えとしては正しく合計を返すので、何を問われているかを読み分けることが大切です。

設問が合計の値だけを聞いているなら、どちらの書き方でも同じ答えになります。一方で、区間の合計を何度も求めるときの効率を聞いているなら、毎回ループする書き方より、累積和で引き算1回にする書き方が速い、というのが答えになります。

ループの形から処理の速さを見積もる考え方は、こちらの記事で詳しく扱っています。

【関連記事】科目Bの計算量問題の解き方｜ループの形からオーダーを判断する

Giji Academy のシミュレーターで動かす¶

紙のトレース表で動きをつかんだら、最後は実際に動かして確かめましょう。添字が1つずれるだけで結果が変わる処理ほど、動かして見る効果は大きくなります。

Giji Academy の擬似言語シミュレーターでは、擬似言語のコードを1行ずつ実行し、変数や配列の値が変わる様子を目で確かめられます。自分で書いたトレース表と見比べながら進めると、どの回で予想とずれたのかがすぐに分かります。

試すときは、まず正しい makePrefix を動かして、s が {0, 4, 6, 13, 14, 19, 22} になるのを確かめてください。そのあと、引き算の式を s[r] − s[l] に書き換えて、答えが1つ分少なくなる様子を見ると、+ 1 の意味が体で分かります。

慣れてきたら、a の値を自分で変えたり、要素数を増やしたりしてみましょう。最後の s の値が、いつも a 全体の合計と一致することが確かめられます。

まずはGiji Academy の擬似言語シミュレーターで講座を選び、合計が1行ごとにたまっていく様子を確かめてみてください。

まとめ¶

科目Bの累積和の問題は、難しい数学の知識を問うものではありません。途中までの合計を1つずつ表に書き、引き算で残る範囲を小さな例で確かめれば、落ち着いて解けます。

この記事でお伝えした5つの段階を振り返っておきましょう。

最初は、要素数が5個前後の小さな配列で十分です。何度か表を書くうちに、s[r + 1] − s[l] を見ただけで、l から r までが残るのだと分かるようになります。

答えが出たら、元の配列を直接足して同じ値になるかを確かめる。この一手間を習慣にしておけば、本番でも自分の答えに自信を持てます。次に累積和の問題に出会ったら、まずは途中までの合計の表を書くところから始めてみてください。