FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：和が7以下である連続部分列の最大長を求める。戻り値はどれか。…
問題
和が7以下である連続部分列の最大長を求める。戻り値はどれか。
整数型の配列: a ← {2, 4, 1, 3, 2, 5}
整数型: left ← 1, sum ← 0, best ← 0, right
for (right を 1 から aの要素数 まで 1 ずつ増やす)
sum ← sum ＋ a[right]
while (sum ＞ 7)
sum ← sum － a[left]
left ← left ＋ 1
endwhile
if (right － left ＋ 1 ＞ best)
best ← right － left ＋ 1
endif
endfor
return best- ア 2
- イ 3（正解）
- ウ 4
- エ 5
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.x 科目B範囲
正解と解説
正解：3
rightを伸ばした後、sumが7を超えたらleftを必要なだけ進めます。
right=1,2,3では区間1〜3の和が7で長さ3です。right=4では和が10になるのでleftを3まで進め、区間3〜4になります。right=5で区間3〜5の長さ3、right=6では再び縮めて長さ2です。最大長は3となります。
Hardでの確認点：窓を右へ広げる処理と、条件を満たすまで左端を縮める処理を分けて追いましょう。sumが一時的に条件を超えても、その後whileで調整されるため、追加直後の値ではなく調整後の区間長や個数を見ます。
計算量に着目：このコードは典型的な「尺取り法（スライディングウィンドウ）」です。leftは一度進めると後戻りしないため、leftとrightはそれぞれ最大で要素数だけしか動かず、二重ループに見えても全体の処理量は要素数に比例するO(n)に収まります。和が7を超えるたびに先頭から全区間を調べ直すと最悪O(n²)になりますが、本コードはその無駄を省いている点が要点です。
この問題について
擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。