FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：長さ3の連続部分列のうち、和が10を超え、かつ偶数であるもの…
問題
長さ3の連続部分列のうち、和が10を超え、かつ偶数であるものの個数を求める。戻り値はどれか。
整数型の配列: a ← {5, 2, 4, 7, 1, 6}
整数型: i, s, count ← 0
s ← a[1] ＋ a[2] ＋ a[3]
if (s ＞ 10 かつ s mod 2 = 0)
count ← count ＋ 1
endif
for (i を 4 から aの要素数 まで 1 ずつ増やす)
s ← s ＋ a[i] － a[i - 3]
if (s ＞ 10 かつ s mod 2 = 0)
count ← count ＋ 1
endif
endfor
return count- ア 1
- イ 2（正解）
- ウ 3
- エ 4
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：2
長さ3の窓を右へずらし、和が10を超えることと偶数であることを同時に確認します。
区間1〜3は11で奇数、2〜4は13で奇数、3〜5は12で条件成立、4〜6は14で条件成立です。したがってcountは2となります。
「10を超える」だけで数えると誤答になります。
Hardでの確認点：窓を右へ広げる処理と、条件を満たすまで左端を縮める処理を分けて追います。sumが一時的に条件を超えても、その後whileで調整されるため、追加直後の値ではなく調整後の区間長や個数を見ましょう。
計算量の着目点：このコードは窓を1つずらすたびに右端のa[i]を足し左端のa[i-3]を引くだけで、和を毎回3要素分足し直しません。そのため各位置の計算は一定時間で済み、全体は要素数nに比例するO(n)で求まります。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。