令和3年度春期 システムアーキテクト 午前Ⅰ 問2

操作手順を漏れなく数え上げる観点

出力順序の数を求める問題では、思いつく順に書き出すと重複や見落としが起きやすくなります。問題文に示された操作の条件を先に整理し、一定の規則で場合分けしながら一つずつ実行可能かを確かめる姿勢が大切です。

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

この問題で意識したいのは、各データをいつ入れていつ取り出すかという操作の並びと、その結果として得られる出力順序との対応関係です。対応を見失わずに、条件を満たす場合だけを数える意識を持ちましょう。

視点

数え上げでは、思いついた順に列挙するよりも、決めた規則に沿って場合を分けるほうが確実です。たとえば最初に出力されるものを固定するなど、何か一つを基準にします。そのうえで、各場合が問題文の操作条件の下で実際に実現できるかを確かめます。規則と条件の二つを意識すると、数えすぎや数え漏れを防げます。

確認ポイント

• 問題文に示されたデータの投入順と、操作に関する制約を最初に書き出して整理したか
• 場合分けの基準を一つ決め、その規則に沿って順に列挙しているか
• 列挙した各出力順序について、条件の下で実現できる操作の並びが本当に存在するかを確かめたか

正解

ウ

解説

3個のデータの並び3!＝6通りのうち、CABだけは後入れ先出しの制約から実現できません。ABC、ACB、BAC、BCA、CBAの5通りは挿入・取出しの操作列で実現できるため、正答はウの5通りです。

成立する5通りの操作列

「入」を挿入、「出」を取出しとします。ABC：A入A出B入B出C入C出。ACB：A入A出B入C入C出B出。BAC：A入B入B出A出C入C出。BCA：A入B入B出C入C出A出。CBA：A入B入C入C出B出A出。この5つはどれも操作列で実現できます。

成立しないCAB

Cを最初に出すには、Cより先に入力されるAとBがすべてスタック内にある必要があります。このときAが下、Bが上に積まれているので、次に取り出せるのはBだけです。そのため、Cの次にAを出すCABは作れません。

計算式

全ての並べ方は3!＝3×2×1＝6通りです。ここから成立しないCABの1通りを引くと、6通り−1通り＝5通りになります。なお、n個のデータをスタックに通したときの出力順の数はカタラン数で、n＝3のときは6!÷(4!×3!)＝5通りです。これも結果と一致します。

各選択肢との比較

3通りと4通りは、上で操作列を示した成立する5通りより少なく、成立する順序を除外する根拠がありません。6通りは実現できないCABまで数えており、多すぎます。

選択肢ア

これは不正解だよ。3通りでは少なすぎるよ。ABC（A入A出B入B出C入C出）、ACB（A入A出B入C入C出B出）、BAC（A入B入B出A出C入C出）、BCA（A入B入B出C入C出A出）、CBA（全部入れてC出B出A出）の5通りは、どれも具体的な操作列で実現できるんだ。3通りにするには2通りを除く必要があるけど、除外できる根拠はないよ。

選択肢イ

これは不正解だよ。4通りでは1通り足りないよ。ABC、ACB、BAC、BCA、CBAの5通りは、挿入と取出しの操作列を具体的に書くと全て実現できて、どれも除外できないんだ。成立しない並びはCABの1通りだけだから、3!＝6通りから1通りを引いた5通りが正しくて、4通りとは一致しないよ。

選択肢ウ（正解）

これは正解だよ。3個の並べ方は3!＝6通りあるよ。そのうちCABは、Cを最初に出す時点でAとBがスタック内にあって、Bが上に載っているからAを先に出せず、成立しないんだ。残るABC、ACB、BAC、BCA、CBAはどれも操作列で実現できるから、6通り−1通り＝5通りになるよ。

選択肢エ

これは不正解だよ。6通りは3個のデータの並べ方3!＝6通りを全部数えた値で、スタックの後入れ先出しの制約を考えていないよ。Cを最初に出すとき、AとBはAが下・Bが上の順でスタックに残っているから、次に出せるのはBだけなんだ。CABは作れないので、6通りは多すぎるよ。

学習のポイント

候補の並びごとに挿入・取出しの操作列を書き、スタックの制約で成立しない並びを一つずつ除外する数え方を身に付けましょう。