基本情報技術者 2019年秋期午前（科目A）問08

問題文

A, C, K, S, Tの順に文字が入力される。スタックを利用して、S, T, A, C, Kという順に文字を出力するために、最小限必要となるスタックは何個か。ここで、どのスタックにおいてもポップ操作が実行されたときには必ず文字を出力する。また、スタック間の文字の移動は行わない。

🖊️ 解答を隠して解いてみる

選択肢

ア：1

イ：2

ウ：3（正解）

エ：4

🔒 解説は解答すると表示されます

並列スタックの最小数【午前解説】

正解の理由

正解はウ（3個）です。
理由は次の通りです。入力順を位置番号で表すとA,C,K,S,Tは1,2,3,4,5、出力S,T,A,C,Kは4,5,1,2,3になります。並列スタックにおいては、同一スタックに入った要素は「後入れ先出し」になり、入力順と同じ順序で出力したい要素は同じスタックに置けません。出力列中で入力順を保持している部分列A(1),C(2),K(3) は長さ3の増加部分列になっており、それぞれ別のスタックが必要です。よって最小数は3個です。

解法ステップ

出力を入力のインデックス列で表す（ここでは4,5,1,2,3）。
出力列中で入力の元の順序を保つ最長増加部分列（LIS）を求める。
LISの長さが並列スタックの最小個数の下限となる（実際にその個数で構成可能かを確認）。
今回はLIS = 3（1,2,3に対応するA,C,K）であり、具体的な配置を示して成立するため最小は3個で確定。

具体構成例（3個で可能）:

スタック1へA（1）をpush、後でS（4）をpush（スタック1は下:A, 上:S）。
スタック2へC（2）をpush、後でT（5）をpush（下:C, 上:T）。
スタック3へK（3）をpush。
ポップ順にスタック1→S、スタック2→T、スタック1→A、スタック2→C、スタック3→KとしてS,T,A,C,Kが得られます。

選択肢別の誤答解説

ア: 1個
一つのスタックでは入力を逆順にしか出力できず、TがトップにあるためSを先に出せません。よって不可能です。
イ: 2個
2個だとSとTは別スタックにする必要がある一方、A,C,Kを順序どおりに出力するには3個分の「独立なトップ位置」が必要であり配置できません。具体例で試すと必ずCとKの順序が逆転します。
ウ: 3個（正解）
上の構成例で実現可能なことを示しました。
エ: 4個
4個あれば確実に可能ですが問題は「最小」を問うているため過剰です。最小は3個なので不正解です。

よくある誤解

「SとTは順序が近いので同じスタックに置ける」と考える誤り：入力ではSがTより先に来るため、同じスタックにするとTが先に出てしまい順序が逆転します。
「A,C,Kは一つのスタックで良い」と考える誤り：一つのスタックにA→C→Kの順で積むとポップ順はK,C,Aになり、目的のA,C,Kにはなりません。
「多めにスタックがあれば良い」と考えがちだが、最小化には増加部分列（LIS）の長さが鍵になる点を見落としやすいです。

補足コラム

この問題は「並列スタック（multiple stacks in parallel）である順列を実現するのに必要な最小スタック数」と「最長増加部分列（LIS）」の関係を示す典型例です。一般に、入力が1..nで与えられ、出力がある順列のとき、並列スタックの最小個数はその順列のLISの長さに等しくなる（patience sortingによる解釈が可能）という性質があります。今回も出力位置列4,5,1,2,3のLISは1,2,3（長さ3）で、これが答えです。

FAQ

Q1: なぜ「増加部分列の長さ = 必要なスタック数」なのですか？
A1: 各スタックは内部で逆順（降順に出力される）を作るため、出力で入力順を保つ要素群は別のスタックに分ける必要があり、その最小分割数がLISの長さに対応します（patience sortingの考え方）。

Q2: スタック間で移動が許されれば変わりますか？
A2: はい。スタック間移動が許されるとより柔軟になり、必要なスタック数は減る可能性があります。本問は移動禁止なので上記結論が成り立ちます。

Q3: 実際の解法でまず何を見るべきですか？
A3: 出力列を入力のインデックス列に変換し、増加部分列（入力順を保つ部分列）を探すことが最短解法です。

関連キーワード: スタック, 後入れ先出し, 最長増加部分列, LIS, patience sorting, 並列スタック, 出力順制御, アルゴリズム問題解法

← 前の問題へこの年度をクイズで解く次の問題へ →

\ せっかくなら /

基本情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！