FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：配列 a={3,1,4,1,5} に対して、次の手続 ran…
問題
配列 a={3,1,4,1,5} に対して、次の手続 rangeSum(a) を実行したときの戻り値はどれか。
○整数型: rangeSum(整数型の配列: a)
整数型の配列: acc[0..aの要素数]
整数型: i
acc[0] ← 0
for (i を 1 から aの要素数 まで 1 ずつ増やす)
acc[i] ← acc[i-1] ＋ a[i]
endfor
return acc[5] - acc[2]- ア 9
- イ 10（正解）
- ウ 14
- エ 4
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：10
累積和配列 acc は、先頭からi番目までの合計を保存します。acc[5]-acc[2] は、1〜5番目の合計から1〜2番目の合計を引くので、3〜5番目の合計を表します。
a={3,1,4,1,5} では acc[5]=14、acc[2]=4 です。したがって戻り値は10で、これは a[3]+a[4]+a[5]=4+1+5 と一致します。acc[5]だけを見て14を選ばないようにしましょう。
| i | acc[i] |
|---|---|
| 0 | 0 |
| 1 | 3 |
| 2 | 4 |
| 3 | 8 |
| 4 | 9 |
| 5 | 14 |
このアルゴリズムの正体：これは累積和（プレフィックス和）で、最初に acc を作る前処理だけ O(n) かかりますが、いったん作れば任意の区間 l〜r の合計を acc[r]-acc[l-1] という引き算1回、つまり O(1) で求められます。同じ配列に何度も区間和を問う場面で効き、毎回足し直す素朴な方法より高速になります。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。