応用情報技術者 2012年 秋期 午前2 問20

最大空き領域方式【午前2解説】

正解の理由

解法ステップ

1. 初期状態を A=0, B=0, C=0（各媒体の割当済み合計）とする。
2. 各要求（90, 30, 40, 40, 70, 30）を順に処理する。容量が同一のため「空き最大媒体」は「割当合計が最小の媒体」と同義。
3. 割当先が複数ある（割当合計が同値）場合は、優先順 A → B → C を適用する。
4. 各要求ごとにどの媒体を選んだかと、その後の合計を記録する。

1. 要求 90：初期は A,B,C が同値 → 優先順で A を選択 → A=90, B=0, C=0
2. 要求 30：最小は B,C（0）→ 優先順で B を選択 → A=90, B=30, C=0
3. 要求 40：最小は C（0）→ C を選択 → A=90, B=30, C=40
4. 要求 40：最小は B（30）→ B を選択 → A=90, B=70, C=40
5. 要求 70：最小は C（40）→ C を選択 → A=90, B=70, C=110
6. 要求 30：最小は B（70）→ B を選択 → A=90, B=100, C=110

選択肢別の誤答解説

• ア: A, B, C
  誤りです。もし A が最も大きくなるなら最後に A が他より大きな追加割当を受けている必要がありますが、逐次割当の結果 A は最初の 90 だけで終わり、C が 70 と 40 を受け取るため A が最大になることはありません。
• イ: A, C, B
  誤りです。A が最も大きく、C が B より大きいという順序ですが、逐次処理では C が 110、B が 100、A が 90 であり A は最小です。したがってこの順序とは矛盾します。
• ウ: B, A, C
  誤りです。B が最も大きいとするには B が合計110以上を受ける必要がありますが、実際は B は 30+40+30 = 100 にとどまります。逐次の割当ルール上、C が 70 を受け取る場面があり C が最大になります。
• エ: C, B, A
  正しい順序です。上の逐次計算と一致します（詳細は「解法ステップ」を参照）。

よくある誤解

• 「最初に A に 90 を割り当てた後は次に C を選ぶ」と考える誤り
  実際は A が 90、B と C が 0 のとき B と C が同順位であり、優先順 A→B→C により B が次に選ばれます。これが誤答発生の最も多い原因です。
• 空き容量比較を「割当済み合計が大きい方を選ぶ」と逆に理解するミス
  本方式は「空きが最大」なので、割当済み合計が小さい媒体を選ぶのが正解です。
• 同容量でも途中での解放を想定する誤り
  問題で「途中で解放されない」と明記されている点を見落とすと入れ替わりがあると誤認します。

補足コラム

• 等容量の媒体に対する「最大空き領域方式」は実装上、各媒体の“現在の割当合計”を追跡し、最小のものを選べばよく、これにより比較が容易になります。
• 実際に検算するための簡単なPythonシミュレーション例を示します（学習用）。

requests = [90, 30, 40, 40, 70, 30]
names = ['A','B','C']
alloc = {'A':0,'B':0,'C':0}
for r in requests:
    # 空き最大は割当合計が最小の媒体を選ぶ
    # 同値時の優先順は A,B,C
    target = min(names, key=lambda n: (alloc[n], names.index(n)))
    alloc[target] += r
    print(f"req {r} -> {target}, totals: {alloc}")
print("final order:", sorted(alloc.items(), key=lambda x:-x[1]))

FAQ