平成27年度 秋期 午前 問18

✓ これが正解エC，B，A

解説

1回ずつ追うと総量はC・B・Aの順になります。

この媒体選択アルゴリズムは、空き領域が最も大きいものを選ぶと定めています。三つの媒体は容量が同じで、初めはすべて空なので、空きが最大というのは使った量が最も少ないという言い換えになります。この形に直してから、六つの要求を一行ずつ追います。最初の90は三つとも同じ状態なので、等しいときの決まりに従ってAへ。次の30は、まだ何も使っていないBとCが並ぶので、同じ決まりからBへ。次の40は、唯一まだ何も使っていないCへ。四つ目の40は、使った量が30で最も少ないBへ。五つ目の70は、使った量が40で最も少ないCへ。最後の30は、90と70と110を比べて最も少ないBへ。合計するとAが90、Bが100、Cが110となり、大きい順に並べるとC、B、Aです。検算として、要求の合計は90と30と40と40と70と30で300、三つの媒体の合計も300で一致します。途中で解放されない条件があるので、この二つは必ず一致します。ここが眼目ですが、空いているほうへ回す仕組みなので、最初に一番大きな領域を受け取った媒体は以後ずっと避けられ、最後には総量が最小になります。

ほかの選択肢はなぜ違うのか

• アA，B，C：最初に90という大きな領域を受け取った媒体が、最後まで首位を保つと見た形です。空いているほうへ回す仕組みでは、その媒体はその後ずっと選ばれず、かえって総量が最小になります。
• イA，C，B：先頭に置いた媒体が実際と食い違っています。追ってみるとその媒体が受け取るのは最初の90だけで、三つの中では総量が最小になります。残る二つの並びは実際どおりで、二回で合計110を受け取るほうが、三回で合計100を受け取るほうより上に来ます。
• ウB，A，C：最後尾に置いた媒体が実際と食い違っています。その媒体は二回目の要求こそ同点の決まりで見送られますが、その後に40と70を受け取り、三つの中で総量が最大になります。