基本情報技術者試験基礎・応用
条件を読む・根拠を説明する
連続区間の和の更新
条件を整理し、答えを選んでから解き方を確認しましょう。
A=[2,5,1,4]。長さ3の先頭区間の和s=8が分かる。次の区間[5,1,4]の和を1回の除算もなく求める式はどれか。
答え・解き方を読む
s−2+4
図で見る
連続区間の両端を動かす
図を拡大して見る ↗右端を延ばすと新しい要素を加え、左端を進めると外れた要素を引きます。累積和なら区間末尾までの和から区間直前までを引きます。図の要素数と端位置は操作の例です。
図は問題の関係を整理する模式図です。記号には各問題の数値を当てはめます。寸法・面積・時間の縮尺や、実施工の全条件は表していません。
考える順序
- 1次の区間で外れるのは先頭の2
- 2新しく入るのは末尾の4
- 38−2+4=10に更新する
選択肢ごとの理由
- 比較 · s−2+1
1は両区間で共通するので追加しません。
- 比較 · s+4
外れた2を差し引く必要があります。
- 正解 · s−2+4
次の区間で外れるのは先頭の2。新しく入るのは末尾の4。8−2+4=10に更新する。
- 比較 · s−5+4
5は次の区間にも残る要素です。