高校情報I 確定モデルのシミュレーション—更新の順と時間刻みから状態の変化を追う｜武蔵野個別指導塾

補充と出庫の順序を入れ替えた在庫表を比べ、二つの棚の同時更新では開始時の値から移動量を決めます。

よくあるのは、更新後の値を別の同時更新へ混ぜてしまう場面です。2つの棚の間で品物を動かす表を作ると、先に計算した棚の新しい数を、もう一方の棚の計算に使いたくなります。しかし、両方を同じ時点の状態から求める約束なら、その混用で移動できる数まで変わります。

品物の数を時刻ごとに追うモデルを作り、どの時点の数を使うか、在庫不足をどう扱うかを決めてから実行します。数は説明のために作った条件であり、実際の倉庫の記録ではありません。

何を答える問題か

出方の1つは、初期在庫と各時刻の補充数、出庫要求から、指定時刻の在庫や実際の出庫数を求めるものです。表の各行が処理前か処理後かを見分け、数の単位をそろえます。もう1つは、2つの状態を同時に更新する式と順番に更新する式を比べ、結果の差を説明するものです。最後に、時間刻みを変えたとき、同じ出来事を同じ順に表せているかを考える問題もあります。

入力は、初期在庫と時刻ごとの補充数、出庫要求です。いずれも0以上の整数とします。出庫要求が使える在庫を超えたら、使える数まで出庫し、残りの要求は持ち越さないことにします。出力は各時刻の処理後の在庫と実出庫数です。出庫できなかった数は要求から実出庫数を引いて求めます。これらの約束が違えば、同じ入力でも別の答えが成立します。

状態と更新の約束

モデルは、目的に必要な状態と、その状態を次の時点へ移す規則を選んだものです。ここでは状態を品物の個数とし、時刻は0、1、2のような離れた点で表します。確定モデルでは、初期状態と入力と規則が同じなら、次の状態も決まります。現実の補充遅れや破損を省いているので、計算結果はこの条件の下での見通しです。

各刻みの開始時に補充し、その後で出庫する規則を採用します。開始在庫を前の行の終了在庫として、補充後の数を求めます。実出庫数は要求数と補充後の数の小さい方です。終了在庫は補充後の数から実出庫数を引きます。したがって出庫は存在する数を超えず、終了在庫は負になりません。

図1のように、開始在庫に補充を足したものが出庫の上限です。矢印は1刻み内の順序を表し、次の刻みは前の刻みの終了在庫から始まります。

図1で、補充を出庫の後に置けば、在庫不足のときに実出庫数が変わることがあります。終了在庫が偶然同じでも、満たせなかった要求が同じとは限りません。状態の値と、その期間に起きた移動量を分けて記録すると、差を見落としにくくなります。

同時更新は複数の新しい状態を、いずれも更新前の状態から計算することです。逐次更新は前の更新結果を次の計算に使う順序を含みます。どちらも使えますが、同時という言葉から逐次のコードを書くと、表現したい規則とずれます。途中の値を別の名前に保存すると、どの時点の値を参照したかを追えます。

基本例題：補充してから出庫する棚

開始時の在庫は4個です。各刻みの補充と出庫要求を順に (3, 5)、(0, 4)、(2, 1) 個とします。各刻みで補充を先に行い、要求は在庫まで満たします。各行の終了在庫と実出庫数を整数で答えてください。

手計算では、1刻み目は4個に3個が入り、7個から5個が出て2個です。2刻み目は2個に補充がなく、要求4個に対して2個を出すので0個です。3刻み目は2個を補充して1個を出し、1個残ります。実出庫は順に5、2、1個です。合計では開始4個と補充5個の合計9個から、出庫8個を引いて残り1個です。

図2のように、各行の右端が次の行の開始在庫へ移ります。特に2行目の要求4個をそのまま引くと負になるため、実出庫数を先に決めます。

次のプログラムは、入力の各組を順に処理して、実出庫と終了在庫の組を返します。初期在庫と各組は0以上の整数という前提です。関数は入力表を変更しません。

def simulate(stock, steps):
    result = []
    for supply, demand in steps:
        available = stock + supply
        shipped = min(available, demand)
        stock = available - shipped
        result.append((shipped, stock))
    return result

print(simulate(4, [(3, 5), (0, 4), (2, 1)]))

def の行は初期在庫と刻みの一覧を受け取る入口です。空の result に結果を順に入れ、for で各組から補充と要求を取り出します。available はその刻みに出庫できる上限、shipped は上限と要求の小さい方です。続く代入で終了在庫を次の開始在庫にし、append で実出庫と終了在庫を記録します。return は一覧を呼出し側へ返し、最後の行が表示します。

入力は初期値4と3組です。期待出力と、Python 3.15.0での実際の出力はともに次のとおりです。

[(5, 2), (2, 0), (1, 1)]

処理前の在庫が非負なら補充後も非負です。実出庫は補充後の数以下なので、処理後も非負です。この性質が各刻みで保たれます。一覧の要素を1つずつ消費する有限回の反復なので、空の一覧なら0回で終わり、有限の一覧なら最後の組の後に終わります。実行例の一致に加え、この理由で前提を満たす各刻みの非負を説明できます。

標準例題：順序を取り替える

開始在庫1個、補充4個、出庫要求3個の1刻みを考えます。補充後に出庫する方式と、開始在庫から先に出庫してから補充する方式について、実出庫数と終了在庫をそれぞれ整数で答えてください。満たせない要求はどちらも持ち越しません。

補充が先なら、利用可能な5個から3個を出し、2個残ります。出庫が先なら1個しか出せず、0個になってから4個が入るので4個残ります。要求の未充足は前者が0個、後者が2個です。両方とも開始1個と補充4個から実出庫を引くと終了在庫に戻ります。補充の前に要求を受け付けるかどうかが、必要な仕様です。

次のコードは2方式を別々に計算します。最初の行で補充先行の実出庫、2行目でその残数を求めます。3行目は出庫先行の実出庫、4行目はその残数です。表示順は実出庫、終了在庫です。

stock, supply, demand = 1, 4, 3
first_in = min(stock + supply, demand)
end_in = stock + supply - first_in
first_out = min(stock, demand)
end_out = stock - first_out + supply
print((first_in, end_in), (first_out, end_out))

Python 3.15.0での期待出力と実際の出力はともに (3, 2) (1, 4) です。もし未充足分を次の刻みに持ち越す目的なら、未充足数も状態に加え、次の要求とどう合算するか定めなければなりません。終了在庫だけを引き継ぐ今のモデルでは、その再注文は表せません。

発展例題：2つの棚を同時に更新する

棚Aに6個、棚Bに2個あります。1刻みにつき、開始時のAからBへ2個、開始時のBからAへ1個を移します。両方の移動は開始時の在庫を基準に決め、利用可能数を超えません。1刻み後と2刻み後のA、Bの個数を答えてください。

1刻み後はAが6から2を出して1を受け取り5個、Bが2から1を出して2を受け取り3個です。次は開始状態が5、3なので、同じ移動を行い4、4個です。各刻みで片方の減少と他方の増加が対応し、合計8個を保ちます。各棚の開始数も指定の移動数以上なので、この2刻みの移動は実行可能です。

同時更新は、移動量を更新前の2つの棚から決めることが要点です。次のコードは一般に、Aから最大2個、Bから最大1個を、その棚の開始在庫を上限に移します。old_a と old_b に開始値を保存し、移動量を決めてから両方の新しい値を作ります。結果を表に追加し、有限回の range が終わると表を返します。

def exchange(a, b, count):
    rows = []
    for step in range(count):
        old_a, old_b = a, b
        to_b = min(old_a, 2)
        to_a = min(old_b, 1)
        a = old_a - to_b + to_a
        b = old_b - to_a + to_b
        rows.append((a, b))
    return rows

print(exchange(6, 2, 2))
print(exchange(1, 0, 1))

Python 3.15.0での入力はそれぞれ (6, 2, 2)、(1, 0, 1) です。期待出力と実際の出力は、順に [(5, 3), (4, 4)]、[(0, 1)] です。後者は開始時のBが空なのでBからの移動は0個です。Aから出た1個はBへ届きますが、同じ刻みにBから折り返すことはありません。合計は前後とも1個です。

時間刻みを半分にしたとしても、各新しい刻みで同じ個数を移すなら、元の1刻みの間に移動する機会が2回になります。移動量と順序の規則を再定義せず、刻みの名前だけ変えた結果は同じ現象の細かい再現とは限りません。途中の在庫不足によって実行できる移動も変わるので、細かくした表と元の表を対応する時刻で照合します。

誤答を途中の状態から直す

開始時Aが1個、Bが0個のとき、AからBへ最大2個、BからAへ最大1個を同時に移す場合を考えます。誤ってAからの移動を先に反映し、その後のBを使ってBからの移動を決めると、入ったばかりの1個まで引き返せます。

a, b = 1, 0
to_b = min(a, 2)
a = a - to_b
b = b + to_b
to_a = min(b, 1)
b = b - to_a
a = a + to_a
print(a, b)

Python 3.15.0での期待値は同時更新の仕様では 0 1 ですが、この誤ったコードの実際の出力は 1 0 です。最初の移動後はAが0、Bが1です。次の min は更新後のBを見て1を選ぶため、開始時のBが0という条件から外れます。合計が1のままでも、正しい同時更新とは限りません。

図3のように原因は後半が新しいBを参照する点です。修正は発展例の exchange のように開始時のAとBを保存し、両移動量を決めてから更新することです。図3の修正後はAが0、Bが1となり、元の条件に戻してもBから出る数は0です。

図3の再実行結果は上の exchange(1, 0, 1) と一致します。この例は逐次更新が常に誤りという意味ではありません。入庫後に出庫する約束なら更新後の数を使う必要があります。何を同時に決めるのかを仕様と照らすことが、修正箇所を選ぶ基準です。

試験で正常と失敗を区別する

基本例の関数は入力の前提を定めた学習用です。正常な試験として、空の刻み一覧なら結果は空、1組なら結果は1組、同じ組が繰り返されれば各行を前行の残数から計算することを調べます。要求0なら出庫0、補充後の数と要求が等しければ残数0です。実出庫の合計と最終在庫を、開始在庫と補充の合計へ戻して照合します。

失敗を調べる試験も同じように用意します。負の在庫や負の要求はこのモデルの範囲外で、関数は入力検査をしないため、結果を正しい在庫表と解釈できません。数の代わりに文字を混ぜると計算時に TypeError になります。外部の道具へ入力を取りに行く場合は、道具の失敗を在庫0や空の一覧に置き換えず、処理を中断して原因を伝える設計が必要です。

時間切れも未完了として扱います。途中までの表を最終結果と混同せず、再実行するなら初期状態と入力を固定します。下の検査では外部の道具を実際には呼ばず、失敗を例外として模擬します。時間切れを含む例外が呼出し側へ伝わることを調べ、成功値の代わりに0を返していないことを確かめます。実際の通信や時間制限の仕組み自体を試すものではありません。

def read_then_run(reader):
    stock, steps = reader()
    if not isinstance(stock, int) or stock < 0:
        raise ValueError("invalid stock")
    for supply, demand in steps:
        if not isinstance(supply, int) or not isinstance(demand, int):
            raise ValueError("invalid step")
        if supply < 0 or demand < 0:
            raise ValueError("invalid step")
    return simulate(stock, steps)

def broken():
    raise RuntimeError("tool failed")

def late():
    raise TimeoutError("time limit")

for reader in [lambda: (2, []), lambda: (2, [(1, 3)]),
               lambda: (-1, []), lambda: (1, [(0, "x")]),
               broken, late]:
    try:
        print(read_then_run(reader))
    except (ValueError, RuntimeError, TimeoutError) as error:
        print(type(error).__name__, str(error))

この検査は先ほどの simulate を同じプログラム内で定義してから実行します。Python 3.15.0で、入力順の期待値と実際の出力は以下のとおり一致しました。最初の2行は正常系、残り4行は前提外、壊れた値、外部の道具の失敗、時間切れの模擬です。例外の種類と文言を残すことで、空の結果と失敗を区別します。

[]
[(3, 0)]
ValueError invalid stock
ValueError invalid step
RuntimeError tool failed
TimeoutError time limit

この検査は組の形が壊れた場合まで捕捉する設計ではありません。実用上は組の長さや一覧そのものの型も入口で検査し、どの失敗を呼出し側へ返すか決めます。例えば要素が1個の組は展開時に例外となり、成功として扱われません。例外を受け取る側で表示や再試行の方針を決める必要があります。

練習：まず自分で表を作る

各問は独立した自作条件です。品物は整数個で、要求を満たせない分は持ち越しません。1から3は補充後に出庫します。答えは指定された順の整数または整数の組で表してください。

1. 開始在庫7個、補充2個、要求6個です。実出庫と終了在庫をこの順の組で答えてください。
2. 開始在庫3個、補充0個、要求8個です。実出庫、未充足、終了在庫をこの順の組で答えてください。
3. 開始在庫2個に、(補充1個、要求0個)、(補充2個、要求5個) を順に適用します。各刻みの終了在庫を順に答えてください。
4. 開始在庫2個、補充5個、要求4個です。補充先行と出庫先行のそれぞれについて、実出庫と終了在庫を組で答えてください。
5. 棚Aが3個、Bが1個です。各刻みの開始時のAからBへ最大2個、開始時のBからAへ最大1個を同時に移します。2刻み後のA、Bを組で答えてください。

練習の答えと照合

1. (6, 3) です。利用可能9個から6個を出し3個です。出庫6個と残り3個を合わせると9個に戻ります。
2. (3, 5, 0) です。3個を出すと棚は空になり、要求8個のうち5個が満たされません。実出庫と未充足を合わせると要求8個です。
3. 3, 0 です。最初に3個となり、次に5個から5個を出します。開始2個と補充3個を合わせた5個がすべて出庫され、残り0個です。
4. 補充先行は (4, 3)、出庫先行は (2, 5) です。前者は7個から4個、後者は2個から2個を出した後に5個を足します。各方式で終了在庫と実出庫を足すと、開始と補充の合計7個に戻ります。
5. (1, 3) です。1刻み後は (2, 2)、2刻み後は (1, 3) です。各開始時点で指定の移動が可能で、合計4個は変化しません。

次の独立した式と関数呼出しで、手計算した答えを照合します。Python 3.15.0で期待出力と実際の出力は記載どおりです。simulate と exchange は上に示した定義を同じプログラムへ置いてから実行します。

print(simulate(7, [(2, 6)]))
print((min(3, 8), 8 - min(3, 8), 3 - min(3, 8)))
print(simulate(2, [(1, 0), (2, 5)]))
print((min(2 + 5, 4), 2 + 5 - min(2 + 5, 4)))
print((min(2, 4), 2 - min(2, 4) + 5))
print(exchange(3, 1, 2))

[(6, 3)]
(3, 5, 0)
[(0, 3), (5, 0)]
(4, 3)
(2, 5)
[(2, 2), (1, 3)]

覚えておくこと

• 状態がどの時点の値かを行ごとに記します。
• 補充と出庫の順序、および不足分の扱いを先に決めます。
• 同時更新では各移動量を更新前の状態から決めます。
• 非負と物の出入りのつじつまで結果を検査します。
• 時間刻みを変えたら1刻み内の規則も見直します。

表のどこで迷ったかを確かめる

在庫が負になった場合は、要求と実出庫を同じ列にしていないかを見直します。最初に負になった行で、開始在庫、補充後の上限、実出庫の順に指さして説明すると、計算の取り違えと規則の取り違えを分けられます。出庫が足りない場合には未充足を残す仕様なのかも、問題文に戻って確認します。

2つの棚の合計が合っているのに答えが違う場合は、各移動量を計算した時点の棚の数を別の色の欄に書きます。個別指導では、まず本人に1刻みの開始状態と終了状態を説明してもらい、次に空の棚を含む入力で同じ説明が通るかを確かめます。同時更新の表は、移動量の参照元をそろえたところから読み直せます。