令和7年度春期 情報処理安全確保支援士 午前Ⅰ 問3

午前I 問03：スタックで作れる並びは何通り？

1,2,3 をこの順番で箱に積んでいくイメージだよ。この箱はスタックなので、最後に入れたものから取り出すルールになる。ただし、途中で好きなタイミングで取り出してOK。そうすると、出力できる並びは全部で5通りになる。これは「3番目のカタラン数」としても求められるよ。

この問題で問われていること

ポイントは、スタックの「後入れ先出し」というルールで、どんな順列が作れるかを見抜けるかどうかだよ。実際に入れる・取り出す流れを手で試して数えてもいいし、知っていればカタラン数を使って判断しよう。

スタック順列の個数

3 個の要素なら生成可能順列数は `C3 = 5` になる。

n=3\nCatalan number = 5

確認ポイント

• FIFO ではなく LIFO の制約で考える。
• 3! = 6 をそのまま選ばない。
• 1 つだけ実現できない並びがあると押さえる。

正解

ウ

出典

問題文と解答は IPA 公開の過去問題冊子・解答例を基にしています。

選択肢ア

3は不正解だよ。スタックには制限があるとはいえ、3通りしか出せないほど窮屈ではないよ。例えば、Aをすぐ出せばABC、Aを出してからBとCを積めばACB、AとBを積んでBから出せばBACのように、少なくとも3通り以上は作れるんだ。実際は5通り作れるよ。

選択肢イ

4は不正解だよ。スタックは、積んだ皿みたいに「後から入れたものが先に出る」仕組みだよ。A、B、Cの順に入れる条件で試すと、ABC、ACB、BAC、BCA、CBAの5通りは出せるので、4通りでは1つ足りないんだ。

選択肢ウ（正解）

5が正解だよ。スタックは積み重ねた皿と同じで、最後に置いた皿から取るルールだよ。このルールで実際に作れる出力順は、ABC、ACB、BAC、BCA、CBAの5通り。CABだけは、Cの下にB、その下にAがある状態になるので、AをBより先に取り出せず作れないんだ。

選択肢エ

6は不正解だよ。A、B、Cの並び替えだけなら全部で6通りあるけど、スタックは自由な出口じゃなくて、上からしか取れない箱みたいなものだよ。CABだけは、Cを出したあとにBを飛ばしてAを先に出せないので、6通り全部は無理なんだ。