【慶應SFC過去問】2016年度総合政策「情報」第4問を詳しく解説｜クリティカルパス | みらい先生の共通テスト情報Ⅰ教室

「カレーは最短で何分で完成する?」――キャンプの段取りを題材にしたこの情報Ⅳは、前半の手計算が後半のアルゴリズムの穴埋めにそのままつながる、SFCらしい良問です。

全問解説記事では要点だけを紹介しましたが、この記事では空欄(63)〜(92)を一つずつ取り上げ、「なぜその答えになるのか」まで丁寧に解説します。手計算の考え方をアルゴリズムに書き直す流れがつかめれば、ほかの年度のアルゴリズム問題もずっと解きやすくなります。

まずは解答一覧で答え合わせをして、気になった空欄の解説から読んでみてください。

解答一覧

空欄	解答
(63)(64)(65)	0, 6, 6(=66分)
(66)(67)	(3) C、(5) E(順不同)
(68)	(1) A
(69)(70)	(28) すべての作業の集合
(71)(72)	(27) 空集合
(73)(74)	(14) P(x)
(75)(76)	(19) M(y)
(77)(78)	(16) M(x)
(79)(80)	(15) T(x)
(81)(82)	(11) x
(83)(84)	(22) M(z)
(85)(86)	(23) T_min = T_delay
(87)(88)	(29) 1増やす
(89)(90)	(29) 1増やす
(91)(92)	(13) D

この問題のテーマ
(ア) 最短時間と「遅れてもよい時間」
1. (63)(64)(65) 完成までの最短時間 Tmin
2. (66)(67)(68) 何分まで遅れてよいか(余裕時間)
  1. おまけ: クリティカルパス
(イ) 手順を一般的なアルゴリズムとして書く
過去問演習には赤本を

この問題のテーマ

この問題は、工事や製造の現場で使われている「クリティカルパス法」というスケジュール管理の考え方を、キャンプのカレー作りにあてはめたものです。

設定をおさえておきましょう。

人数は十分に多いので、いくつかの作業を同時に進められる
ただし作業には「先行作業」があり、先行作業がすべて終わるまではその作業を始められない

作業の一覧は次のとおりです。

作業	所要時間(分)	先行作業
A 火をおこす	15	なし
B 米を研ぐ	30	なし
C 肉・野菜を切る	20	なし
D 米を炊く	30	A, B
E カレーを煮る	35	A, C
F 火の後始末	3	D, E
G 盛り付ける	6	D, E
H 完成	0	F, G

「H 完成」は所要時間0分の作業です。実際の作業ではなく、「FとGが両方終わった瞬間が完成」という目印として置かれています。

作業のつながりを図にすると、次のようになります(矢印は「この作業が終わったら、次の作業に進める」という意味です)。

(ア) 最短時間と「遅れてもよい時間」

(63)(64)(65) 完成までの最短時間 Tmin

各作業について「最も早くて何分後に終わるか」を順番に計算します。ルールは一つだけです。

ある作業が終わる最短時刻 = (先行作業が終わる最短時刻のうち、いちばん遅いもの)+(自分の所要時間)

「いちばん遅いもの」をとるのは、先行作業が全部終わるまで始められないからです。たとえばDは、Aが15分後に終わっていても、Bが終わる30分後までは始められません。

先行作業がないものから順に計算します。

作業	始められる時刻	終わる最短時刻
A	0	0+15 = 15
B	0	0+30 = 30
C	0	0+20 = 20
D	max(Aの15, Bの30) = 30	30+30 = 60
E	max(Aの15, Cの20) = 20	20+35 = 55
F	max(Dの60, Eの55) = 60	60+3 = 63
G	max(Dの60, Eの55) = 60	60+6 = 66
H	max(Fの63, Gの66) = 66	66+0 = 66

解答: T_min = 66分 → (63)(64)(65) は 0, 6, 6

3桁でマークする欄なので、「066」とマークする点に注意しましょう。

(66)(67)(68) 何分まで遅れてよいか(余裕時間)

次は「その作業の所要時間が延びたとき、全体の完成(66分)も遅れるかどうか」を考えます。ここでカギになるのが余裕時間です。

余裕時間は、完成の側から逆向きに計算するとわかります。

ある作業が遅くとも終わっていなければならない時刻 = (その作業を先行作業にしている作業の「遅くとも始めなければならない時刻」のうち、いちばん早いもの)

完成Hを66分に保つには、Hの直前の作業から順にさかのぼって考えます。

作業	遅くとも終わるべき時刻	遅くとも始めるべき時刻	余裕時間(遅くとも終わる − 最短で終わる)
H	66	66	66 − 66 = 0
G	66(Hが始まるまで)	66 − 6 = 60	66 − 66 = 0
F	66(Hが始まるまで)	66 − 3 = 63	66 − 63 = 3
D	min(Gの60, Fの63) = 60	60 − 30 = 30	60 − 60 = 0
E	min(Gの60, Fの63) = 60	60 − 35 = 25	60 − 55 = 5
A	min(Dの30, Eの25) = 25	25 − 15 = 10	25 − 15 = 10
B	Dの30	30 − 30 = 0	30 − 30 = 0
C	Eの25	25 − 20 = 5	25 − 20 = 5

Aは、DにもEにも間に合わせなければならないので、2つのうち厳しいほう(早いほう)の25分が締め切りになります。ここが間違えやすいところです。

余裕時間の意味は「この分数までなら、所要時間が延びても完成は66分のまま」ということです。余裕を1分でも超えると、完成時刻が延びてしまいます。

設問の条件をこれにあてはめます。

「5分延びても変わらないが、10分延びると長くなる」→ 余裕時間が 5分以上9分以下の作業 → 余裕5分の C と E
「10分延びても変わらないが、15分延びると長くなる」→ 余裕時間が 10分以上14分以下の作業 → 余裕10分の A

Fは余裕が3分しかないので、5分延びると完成が延びてしまい、条件に合いません。

解答: (66)(67) は (3) C と (5) E(順不同)、(68) は (1) A

【確認】たとえばCが5分延びて25分になると、Eは25分に始まって60分に終わります。Dも60分に終わるので、GとFはこれまでどおり60分に始められ、完成は66分のままです。Cが10分延びて30分になると、Eは65分に終わり、Gは65分に始まって71分に終わるので、完成が5分延びます。

おまけ: クリティカルパス

余裕時間が0の作業 B → D → G → H をつなげた道筋をクリティカルパスと呼びます。所要時間を足すと 30+30+6+0 = 66分となり、最短時間と一致します。この道筋の作業は1分でも遅れると完成が遅れるので、現場ではここを重点的に管理します。

(イ) 手順を一般的なアルゴリズムとして書く

(ア)で手計算した内容を、どんな作業表にも使える手順として書く問題です。問題文の方針は次の2段階でした。

まず、遅れがない場合の最短時間を計算する(処理A)
次に、作業 w の所要時間を1分ずつ増やしながら、最短時間が延びるかどうかを調べる(処理B、その中で最短時間を計算し直すのが処理C)

記号の意味を整理しておきます。

記号	意味	カレーの例
T(x)	作業 x の所要時間	T(D) = 30
P(x)	作業 x の先行作業の集合	P(D) = {A, B}、P(A) = { }(空集合)
M(x)	始めてから x が終わるまでの最短時間	M(D) = 60
z	全体の完成を表す作業	H
U	まだ M の値を計算していない作業の集合

処理A: 最短時間の計算(空欄 (69)〜(84))

問題文の手順に答えを入れると、次のようになります。

すべての作業 x について、M(x) を決まっていない状態にする
集合 U を「すべての作業の集合」とする              … (69)(70)
集合 U が「空集合」でない間、処理Aを繰り返す        … (71)(72)
  処理Aの始め
    x∈U かつ「すべての y∈P(x) について M(y) が      … (73)(74)、(75)(76)
      すでに決まっている」という条件を満たす x を1つ選ぶ
    M(x) の値を、「すべての y∈P(x) に対する M(y)    … (77)(78)
      の中の最大値」に T(x) を加えたものと決める     … (79)(80)
    集合 U から x を取り除く                         … (81)(82)
  処理Aの終わり
変数 T_min の値を M(z) にする                        … (83)(84)

1つずつ理由を見ていきましょう。

(69)(70) (28) すべての作業の集合 U は「まだ計算が終わっていない作業」を入れておく箱です。最初はどの作業の M も決まっていないので、全部の作業を入れておきます。

(71)(72) (27) 空集合 計算が終わった作業は U から取り除いていきます。U が空っぽ(空集合)になれば、全作業の計算が終わったということです。「空集合でない間」繰り返せば、ちょうど全部を計算し終えたところで止まります。

(73)(74) (14) P(x)、(75)(76) (19) M(y) x の最短終了時刻を計算するには、x の先行作業すべての終了時刻がわかっている必要があります。先行作業の集合は P(x) なので、「すべての y∈P(x) について M(y) が決まっている」という条件になります。

ここで y と x の役割を取り違えないようにしましょう。y は「x の先行作業の1つ」を表す変数です。P(y) や M(x) を入れると意味が通りません。

カッコ書きの「P(x) が空集合の場合も含む」は、A・B・Cのように先行作業がない作業のことです。調べる相手がいないので条件は自動的に満たされ、真っ先に計算できます。

(77)(78) (16) M(x)、(79)(80) (15) T(x) (ア)で使ったルールそのものです。

M(x) = max{ M(y) | y∈P(x) } + T(x)

先行作業がない場合は最大値を0とするので、M(A) = 0 + 15 = 15 のように計算されます。

(81)(82) (11) x M(x) が決まったので、x を「未計算の箱」U から取り除きます。これを忘れると、同じ作業を何度も選んでしまい、U がいつまでも空にならず、処理が終わりません。

(83)(84) (22) M(z) 全体の完成を表す作業 z(カレーの例ではH)が終わる最短時刻こそが、完成までの最短時間です。カレーの例では M(H) = 66 です。

【処理Aの動きを追ってみる】選び方の一例を示します(条件を満たす x が複数あるときは、どれを選んでも結果は同じです)。

回	選べる候補	選んだ x	M(x)	処理後の U
1	A, B, C	A	0+15 = 15	{B,C,D,E,F,G,H}
2	B, C	B	0+30 = 30	{C,D,E,F,G,H}
3	C, D	C	0+20 = 20	{D,E,F,G,H}
4	D, E	D	max(15,30)+30 = 60	{E,F,G,H}
5	E	E	max(15,20)+35 = 55	{F,G,H}
6	F, G	F	max(60,55)+3 = 63	{G,H}
7	G	G	max(60,55)+6 = 66	{H}
8	H	H	max(63,66)+0 = 66	空集合 → 終了

最後に T_min = M(H) = 66 となり、(ア)の答えと一致します。

処理B: 遅れを1分ずつ増やす(空欄 (85)〜(92))

変数 D の値を 0 にする
変数 T_delay の値を T_min にする
条件「T_min = T_delay」が成り立つ間、処理Bを繰り返す   … (85)(86)
  処理Bの始め
    変数 D の値を「1増やす」                          … (87)(88)
    変数 T(w) の値を「1増やす」                       … (89)(90)
    (処理Aと同じ手順=処理Cで最短時間を計算し直す)
    変数 T_delay の値を M(z) にする                   … (83)(84)
  処理Bの終わり
結果として変数 D の値を出力する                       … (91)(92)

変数の役割は次のとおりです。

D: 作業 w を何分遅らせたか(遅れの分数)
T_delay: w を D 分遅らせたときの、完成までの最短時間
T_min: 遅れがないときの最短時間(66分のまま変わらない)

(85)(86) (23) T_min = T_delay 「遅らせても完成時刻が変わらない」間は、もっと遅らせて様子を見ます。完成時刻が延びた(T_delay が T_min より大きくなった)瞬間に繰り返しをやめます。最初は T_delay = T_min にしてあるので、少なくとも1回は処理Bに入ります。

選択肢の (24) D = 0 や (25) D > 0 は、遅れの分数だけを見ていて、完成時刻が延びたかどうかを判断していないので不適です。

(87)(88) (29) 1増やす、(89)(90) (29) 1増やす 遅れを1分増やす(Dを1増やす)ことと、作業 w の所要時間を実際に1分延ばす(T(w)を1増やす)ことを、セットで行います。こうすると、常に「T(w) = もとの所要時間 + D」の関係が保たれます。

処理Cの中身は処理Aとまったく同じで、延ばした T(w) を使って最短時間を計算し直しているだけです。そのため、空欄も (69)〜(82) と同じ番号が使われています。なお、問題冊子の処理Cの最初の行は、処理Aと同じく「x∈U」と読みます。

(91)(92) (13) D 繰り返しが止まったときの D は、「初めて完成時刻が延びた遅れの分数」です。これが問題の求める「作業 w が何分遅れると、完成までの時間に影響するか」の答えです。

【処理Bの動きを追ってみる(w = A の場合)】

D	T(A)	T_delay	T_min = T_delay?
0(開始時)	15	66	成り立つ → 処理Bへ
1	16	66	成り立つ → 続ける
…	…	66	成り立つ → 続ける
10	25	66	成り立つ → 続ける
11	26	67	成り立たない → 終了

出力は D = 11 です。「11分遅れると完成に影響する」という意味で、(ア)で求めた余裕時間10分より1大きい値になっています。つまり、このアルゴリズムの出力は常に「余裕時間 + 1」です。

念のため、すべての作業について出力をプログラムで確かめると、次のようになりました。

w	A	B	C	D	E	F	G	H
余裕時間	10	0	5	0	5	3	0	0
出力 D	11	1	6	1	6	4	1	1

クリティカルパス上の作業(B・D・G・H)は、1分遅れただけで完成が延びるので、出力は1になります。

この問題から学べること

「先行作業がすべて終わってから始められる」という条件は、max(最大値)で表せる
締め切りを逆向きにさかのぼるときは、min(最小値)で表せる
「計算が終わったものを集合から取り除き、空になったら終了」は、アルゴリズムでよく使う型
「条件が変わるまで1ずつ増やして試す」という素朴な方法でも、正しい答えが得られる(ただし計算回数は多くなる)

後半の穴埋めは、前半で手計算した手順を言葉に置き換えただけです。(イ)で迷ったら、(ア)で自分が何をしたかを思い出し、それに合う記号を選ぶと解きやすくなります。

過去問演習には赤本を

慶應SFCの「情報」は、今回のようなアルゴリズムの穴埋めや、手を動かして答えを出す問題が毎年出題されます。本番で時間内に解き切るには、実際の問題を時間を計って解く練習が欠かせません。

最新年度の赤本には、直近の過去問と解答・解説がまとめて収録されています。この記事で考え方をつかんだら、次は赤本で最新の問題にも挑戦してみてください。

リンク