FE SUBJECT B
基本情報技術者 科目Bの問題解説：配列 a={2,1,3,2} に対して、次の手続 dpHar…
問題
配列 a={2,1,3,2} に対して、次の手続 dpHard(a) を実行したときの戻り値はどれか。
○整数型: dpHard(整数型の配列: a)
整数型の配列: dp[0..aの要素数]
整数型: i
dp[0] ← 0
dp[1] ← a[1]
for (i を 2 から aの要素数 まで 1ずつ増やす)
if (dp[i － 1] ＞ dp[i － 2] ＋ a[i])
dp[i] ← dp[i － 1]
else
dp[i] ← dp[i － 2] ＋ a[i]
endif
endfor
return dp[aの要素数]- ア 4
- イ 5（正解）
- ウ 6
- エ 7
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：5
隣り合う要素を同時に選ばない最大和を dp で求めています。dp[1]=2 です。i=2では max(2,1)=2、i=3では max(2,2+3)=5、i=4では max(5,2+2)=5 となります。したがって戻り値は dp[4]=5 です。
6は3と2を隣接して選んでしまった場合、7は2+3+2のように制約を無視した場合に出やすい誤りです。4は最後の dp[4] 更新だけを見た途中値です。
DPでは、dp[i] が何を表すかを先に決めます。この問題では「i番目まで見たときの最大和」なので、選ぶ場合は dp[i-2]+a[i]、選ばない場合は dp[i-1] です。
このアルゴリズムの正体：これは「隣り合う要素を選べない条件での最大和」を求める典型的なDPで、各要素を1回ずつ見るだけなので計算量は要素数nに比例するO(n)です。dp[1]だけは比較せずa[1]をそのまま入れる初期値である点に注意が必要で、ここをmax比較に含めると境界でつまずきやすくなります。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。