FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：次の二ポインタ法で、和が8以下の組の数を求める。戻り値はどれ…
問題
次の二ポインタ法で、和が8以下の組の数を求める。戻り値はどれか。
整数型の配列: a ← {1, 2, 3, 5, 7}
整数型: left ← 1, right ← 5, count ← 0
while (left ＜ right)
if (a[left] ＋ a[right] ≦ 8)
count ← count ＋ (right - left)
left ← left ＋ 1
else
right ← right - 1
endif
endwhile
return count- ア 5
- イ 6
- ウ 7（正解）
- エ 8
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：7
配列は昇順なので、a[left]+a[right]が8以下なら、leftとleft+1〜rightまでの全ての組が条件を満たします。そのためcountにright-leftを一気に足します。
| left | right | 判定 | count |
|---|---|---|---|
| 1 | 5 | 1+7≦8 | 4 |
| 2 | 5 | 2+7>8 | 4 |
| 2 | 4 | 2+5≦8 | 6 |
| 3 | 4 | 3+5≦8 | 7 |
最終的にcountは7です。条件を満たすたびに1だけ増やすのではない点が重要です。
選択肢の見分け方：5や6は一括加算right-leftを一部しか足していない値、8は条件を超える組まで含めた値です。整列済みであることを利用してまとめて数えます。
計算量で見る価値：この二ポインタ法は、left と right が合わせて高々 n 回しか動かないため、要素数 n に対して O(n) で数え上げが完了します。すべての組を二重ループで調べる素朴な方法は O(n²) ですが、配列が昇順に整列済みだからこそ、a[left]+a[right] が条件を満たした瞬間に left〜right 間の組をまとめて加算でき、無駄な比較を省けるのです。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。