応用情報技術者試験 令和4年度 春期 午前 問73

【正解】ア

四つの仕事を一度ずつ行うので、仕事間の段取りは3回発生します。表は行がFROM、列がTOであり、方向によって時間が異なる点に注意します。仕事を「b→a→c→d」の順にすると、表からb→aは1時間、a→cは1時間、c→dは2時間です。したがって、合計段取り時間は、1＋1＋2＝4時間となります。

さらに、これが最小であることを確認します。3回の段取りはいずれも1時間以上なので、4時間未満にするには、3回全てを1時間にして合計3時間にする必要があります。しかし、表で1時間の移動はa→c、b→a、b→cだけであり、仕事dへ入る移動にもdから出る移動にも1時間のものがありません。よって、四つ全てを通る経路を3時間にはできず、4時間が最小です。

イの5時間は誤りです。例えばa→b→c→dでは2＋1＋2＝5時間ですが、最小ではありません。

ウの6時間は誤りです。4時間で実行できる順序があるため、最小値にはなりません。

エの7時間も誤りです。同様に、求める最小値ではありません。

【ポイント】 段取り時間の表は、FROMからTOへの向きを確認して読みます。 仕事がn個なら、最初と最後の追加作業が指定されない限り、仕事間の移動はn－1回です。 候補となる順序を示すだけでなく、それ未満にできない理由まで確認すると確実です。