応用情報技術者 2011年 春期 午前2 問51

結合点の最遅通過日【午前2解説】

正解の理由

解法ステップ

1. 最早結合点時刻（前から）
   • ①＝0、②＝0＋8（A）＝8、③＝0＋5（B）＝5
   • ④＝max(8＋10（D）、5＋9（E）)＝max(18, 14)＝18
   • ⑤＝max(0＋12（C）、④＋0（ダミー④→⑤）)＝max(12, 18)＝18
   • ⑥＝18＋5（H）＝23
   • ⑦＝max(8＋8（F）、18＋12（G）、23＋4（I）)＝max(16, 30, 27)＝30
2. 最遅結合点時刻（後ろから）
   • ⑦＝30
   • ⑥＝30－4（I）＝26
   • ⑤＝26－5（H）＝21
   • ④＝min(30－12（G）、⑤－0（ダミー）)＝min(18, 21)＝18
3. 結合点⑤の最遅結合点時刻は21日なので、遅くとも21日後に通過していればよい。

選択肢別の誤答解説

• ア: 12
  C の所要日数で、⑤の最早時刻をダミーを無視して求めた値です。
• イ: 14
  E を通る経路（5＋9）の値で、⑤とは関係ありません。
• ウ: 18
  ⑤の最早結合点時刻（最も早く通過できる日）です。ダミーの向きを逆（⑤→④）に読んで最遅時刻を求めた場合にもこの値になりますが、問われているのは遅くとも通過すべき日です。
• エ: 21
  ⑤の最遅結合点時刻で、正しい値です。

よくある誤解

• ダミー作業の向きを逆に読むこと。ダミーは④から⑤へ向かっているので、⑤から始まる H は④に入る作業（D・E）の完了も待ちます。最遅時刻の計算では、⑤の後ろにある作業は H だけです。
• 最早結合点時刻と最遅結合点時刻を取り違えること。「遅くとも何日後」は最遅結合点時刻です。

補足コラム

FAQ