基本情報技術者 2019年 秋期 午前（科目A） 問08
問題文
A, C, K, S, Tの順に文字が入力される。スタックを利用して、S, T, A, C, Kという順に文字を出力するために、最小限必要となるスタックは何個か。ここで、どのスタックにおいてもポップ操作が実行されたときには必ず文字を出力する。また、スタック間の文字の移動は行わない。
選択肢
ア：1
イ：2
ウ：3（正解）
エ：4
##: スタックを用いた文字列出力の最小スタック数【午前2 解説】
要点まとめ
- 結論: 入力 A, C, K, S, T から出力 S, T, A, C, K を作るには最小で3個のスタックが必要です。
- 根拠: 出力列のうち入力順を保持する部分列 A, C, K は互いに別スタックで保持する必要があり、少なくとも3個が必要です。
- 差がつくポイント: 「同じスタックに置ける条件（出力順が入力順の逆になる）」を理解して、最短構成を構築できるかが合否を分けます。
正解の理由
正解は ウ（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個です。
理由は次の通りです。入力順を位置番号で表すと 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個です。
よくある誤解
- 「S と T は順序が近いので同じスタックに置ける」と考える誤り：入力では S が T より先に来るため、同じスタックにすると T が先に出てしまい順序が逆転します。
- 「A,C,K は一つのスタックで良い」と考える誤り：一つのスタックに A→C→K の順で積むとポップ順は K,C,A になり、目的の A,C,K にはなりません。
- 「多めにスタックがあれば良い」と考えがちだが、最小化には増加部分列（LIS）の長さが鍵になる点を見落としやすいです。
解法ステップ
- 出力を入力のインデックス列で表す（ここでは 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個なので不正解です。
補足コラム
この問題は「並列スタック（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 の考え方）。
A1: 各スタックは内部で逆順（降順に出力される）を作るため、出力で入力順を保つ要素群は別のスタックに分ける必要があり、その最小分割数が LIS の長さに対応します（patience sorting の考え方）。
Q2: スタック間で移動が許されれば変わりますか？
A2: はい。スタック間移動が許されるとより柔軟になり、必要なスタック数は減る可能性があります。本問は移動禁止なので上記結論が成り立ちます。
A2: はい。スタック間移動が許されるとより柔軟になり、必要なスタック数は減る可能性があります。本問は移動禁止なので上記結論が成り立ちます。
Q3: 実際の解法でまず何を見るべきですか？
A3: 出力列を入力のインデックス列に変換し、増加部分列（入力順を保つ部分列）を探すことが最短解法です。
A3: 出力列を入力のインデックス列に変換し、増加部分列（入力順を保つ部分列）を探すことが最短解法です。
関連キーワード: スタック, 後入れ先出し, 最長増加部分列, LIS, patience sorting, 並列スタック, 出力順制御, アルゴリズム問題解法
\ せっかくなら /
基本情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！