FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：配列 a={3,1,2,5,4} に対して、次の手続 lis…
問題
配列 a={3,1,2,5,4} に対して、次の手続 lisScore(a) を実行したときの戻り値はどれか。
○整数型: lisScore(整数型の配列: a)
整数型の配列: dp[1..aの要素数]
整数型: i, j, best ← 1
for (i を 1 から aの要素数 まで 1ずつ増やす)
dp[i] ← 1
for (j を 1 から i － 1 まで 1ずつ増やす)
if (a[j] ＜ a[i] and dp[j] ＋ 1 ＞ dp[i])
dp[i] ← dp[j] ＋ 1
endif
endfor
if (dp[i] ＞ best)
best ← dp[i]
endif
endfor
return best × 10 ＋ dp[aの要素数]- ア 23
- イ 32
- ウ 33（正解）
- エ 34
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：33
各位置で終わる増加部分列の長さをdpに入れます。a[1]=3は1、a[2]=1も1、a[3]=2は1→2で長さ2、a[4]=5は1,2,5などで長さ3、a[5]=4も1,2,4で長さ3です。best=3、dp[5]=3なので戻り値は33になります。
32は最後のdp[5]を2とした場合、34は5番目の値4を戻り値の一部に使った誤りです。23はbestとdp[5]を逆または途中値で読んでいるものです。
LISのDPでは、dp[i]は全体の最大ではなく「i番目で終わる最大長」です。最後にbestとdp[n]が同じとは限りませんが、この問題ではどちらも3になります。
このアルゴリズムの正体：これは最長増加部分列（LIS）を求める動的計画法です。dp[i]は「a[i]で終わる増加部分列の最大長」で、二重ループのため計算量はO(n²)です。なお「部分列」は連続でなくてよい点が「部分文字列」との違いで、{1,2,5}や{1,2,4}のように飛び飛びに選べます。二分探索を併用すればO(n log n)に改善できます。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。