プログラミング

from heapq import heapify, heappop


def allocate(lots, orders):
    # Validate every input before allocating stock.
    remaining = {}
    for lot in lots:
        if lot["qty"] < 0:
            raise ValueError("Negative lot quantity")
        if lot["id"] in remaining:
            raise ValueError("Duplicate lot id")
        remaining[lot["id"]] = lot["qty"]

    seen_orders = set()
    for order in orders:
        if order["qty"] < 0:
            raise ValueError("Negative order quantity")
        if order["id"] in seen_orders:
            raise ValueError("Duplicate order id")
        seen_orders.add(order["id"])

    heap = [(lot["expires"], lot["id"])
            for lot in lots if lot["qty"] > 0]
    heapify(heap)
    usable_total = sum(remaining.values())
    fills = {}
    short = {}

    # Python's stable sort preserves input order for equal days.
    for order in sorted(orders, key=lambda order: order["day"]):
        day = order["day"]
        order_id = order["id"]
        need = order["qty"]
        fills[order_id] = []

        # Expired stock stays in remaining but cannot be allocated.
        while heap and heap[0][0] < day:
            _, lot_id = heappop(heap)
            usable_total -= remaining[lot_id]

        if order.get("all_or_nothing", False) and need > usable_total:
            short[order_id] = need
            continue

        while need > 0 and heap:
            _, lot_id = heap[0]
            taken = min(need, remaining[lot_id])
            fills[order_id].append((lot_id, taken))
            remaining[lot_id] -= taken
            usable_total -= taken
            need -= taken
            if remaining[lot_id] == 0:
                heappop(heap)

        if need > 0:
            short[order_id] = need

    return {"fills": fills, "short": short, "remaining": remaining}

検証は在庫の割り当てを行う前にすべて完了します。日付による安定ソートにより、同じ日の注文は元の順序を保ちます。ヒープは、在庫が正の数のロットを有効期限、次にロットIDの順に並べます。注文は日付順に処理されるため、期限切れのロットは最終的な在庫数を変えることなくヒープから永久に取り除けます。

usable_total は、現在出荷可能なすべての在庫を追跡します。これにより、全量引き当て（all-or-nothing）の注文は、何も消費せずに拒否できます。通常の注文は、満たされるか在庫が尽きるまで、ヒープの先頭の在庫を消費します。数量ゼロの注文は、空の fills を受け取り、不足は発生しません。

L をロットの数、M を注文の数、K を返される割り当てタプルの数とします。各ロットはヒープから最大1回だけ取り除かれます。時間計算量は O(L log(L + 1) + M log(M + 1) + K)、出力を含む空間計算量は O(L + M + K) です。

def allocate(lots, orders):
    # ---- validation (nothing is allocated if this fails) ----
    seen_lots = set()
    for lot in lots:
        if lot["qty"] < 0:
            raise ValueError("negative lot qty: %r" % (lot["id"],))
        if lot["id"] in seen_lots:
            raise ValueError("duplicate lot id: %r" % (lot["id"],))
        seen_lots.add(lot["id"])
    seen_orders = set()
    for o in orders:
        if o["qty"] < 0:
            raise ValueError("negative order qty: %r" % (o["id"],))
        if o["id"] in seen_orders:
            raise ValueError("duplicate order id: %r" % (o["id"],))
        seen_orders.add(o["id"])

    # ---- setup ----
    # Lots in FEFO order: earliest expiry first, ties by id.
    ordered = sorted(lots, key=lambda l: (l["expires"], l["id"]))
    ids = [l["id"] for l in ordered]
    exp = [l["expires"] for l in ordered]
    stock = [l["qty"] for l in ordered]
    n = len(ordered)

    fills = {o["id"]: [] for o in orders}
    short = {}

    # sorted() is stable, so same-day orders keep their input order.
    queue = sorted(orders, key=lambda o: o["day"])

    ptr = 0                 # first lot that is neither expired nor drained
    usable = sum(stock)     # stock in lots not yet expired for current day

    for o in queue:
        d = o["day"]
        need = o["qty"]

        # Days are non-decreasing, so an expired lot stays expired.
        while ptr < n and exp[ptr] < d:
            usable -= stock[ptr]
            ptr += 1

        if o.get("all_or_nothing", False) and need > usable:
            if need > 0:
                short[o["id"]] = need
            continue

        i = ptr
        while need > 0 and i < n:
            take = min(stock[i], need)
            if take > 0:
                fills[o["id"]].append((ids[i], take))
                stock[i] -= take
                usable -= take
                need -= take
            i += 1

        # Drained lots form a prefix of the unexpired lots; skip them.
        while ptr < n and stock[ptr] == 0:
            ptr += 1

        if need > 0:
            short[o["id"]] = need

    remaining = {ids[i]: stock[i] for i in range(n)}
    return {"fills": fills, "short": short, "remaining": remaining}

説明

入力は最初に検証されるため、割り当てを行う前に ValueError が発生する可能性があります。ロットは一度 (expires, id) でソートされます。注文は day でソートされます。Python のソートは安定しているため、同じ日の注文は入力時の順序を保ちます。

ポインタ ptr は、期限切れでも在庫切れでもない最初のロットを指します。日付は減少しないため、期限切れになったロットは期限切れのままです。また、在庫は常に最も早く使用可能なロットから引き当てられるため、在庫がなくなったロットは使用可能なロットの接頭辞を形成します。したがって ptr は前進のみします。

実行中のカウンター usable は、期限切れになっていないロットの在庫を保持します。これにより、全量か無かの注文を O(1) で確認できます。注文量が多すぎる場合は、何も変更されず、在庫はそのまま利用可能な状態に保たれます。

時間計算量: O(n log n + m log m + n + m + F)。ここで n はロット数、m は注文数、F は返される引き当て項目数です。各注文はロットを消費し、部分的に使われたロットは最大1つ残るため、F は最大で m + n です。したがって全体は O(n log n + m log m) です。追加の空間計算量は O(n + m) です。

def allocate(lots, orders):
    # Validate everything before creating or changing allocation state.
    lot_ids = set()
    for lot in lots:
        if lot["qty"] < 0:
            raise ValueError("lot quantity cannot be negative")
        if lot["id"] in lot_ids:
            raise ValueError("duplicate lot id")
        lot_ids.add(lot["id"])

    order_ids = set()
    for order in orders:
        if order["qty"] < 0:
            raise ValueError("order quantity cannot be negative")
        if order["id"] in order_ids:
            raise ValueError("duplicate order id")
        order_ids.add(order["id"])

    remaining = {lot["id"]: lot["qty"] for lot in lots}
    sorted_lots = sorted(lots, key=lambda lot: (lot["expires"], lot["id"]))
    fills = {order["id"]: [] for order in orders}
    short = {}

    for order in sorted(orders, key=lambda order: order["day"]):
        order_id = order["id"]
        qty = order["qty"]
        usable = [
            lot for lot in sorted_lots
            if lot["expires"] >= order["day"] and remaining[lot["id"]] > 0
        ]
        available = sum(remaining[lot["id"]] for lot in usable)

        if order.get("all_or_nothing", False) and qty > available:
            short[order_id] = qty
            continue

        needed = qty
        for lot in usable:
            taken = min(needed, remaining[lot["id"]])
            if taken:
                fills[order_id].append((lot["id"], taken))
                remaining[lot["id"]] -= taken
                needed -= taken
            if needed == 0:
                break

        if needed > 0:
            short[order_id] = needed

    return {"fills": fills, "short": short, "remaining": remaining}

注文は日付の昇順で安定的に処理され、ロットは有効期限、次にIDの順で検討されます。全量引当(all-or-nothing)の注文を完全に供給できない場合、在庫は変更されません。入力は引当状態が作成される前に検証され、入力のリストと辞書は変更されません。

L 個のロットと O 件の注文に対して、時間計算量は O(L log L + O log O + OL) です。これは、ロットと注文のソートに加え、各注文について使用可能なロットを走査するためです。空間計算量は、返される引当結果を除いて O(L + O) です。

def allocate(lots, orders):
    """Allocate stock FEFO (first-expiring, first-out) to orders.

    Returns {"fills": ..., "short": ..., "remaining": ...}.
    Raises ValueError for negative quantities or duplicate ids.
    """
    # ---- Validation (before any allocation) ----
    seen_lots = set()
    for lot in lots:
        if lot["qty"] < 0:
            raise ValueError(f"lot {lot['id']!r} has negative qty")
        if lot["id"] in seen_lots:
            raise ValueError(f"duplicate lot id {lot['id']!r}")
        seen_lots.add(lot["id"])

    seen_orders = set()
    for order in orders:
        if order["qty"] < 0:
            raise ValueError(f"order {order['id']!r} has negative qty")
        if order["id"] in seen_orders:
            raise ValueError(f"duplicate order id {order['id']!r}")
        seen_orders.add(order["id"])

    # ---- Setup (input dicts are never mutated) ----
    stock = {lot["id"]: lot["qty"] for lot in lots}
    # FEFO order: earliest expiry first, ties by lot id (string comparison).
    fefo = sorted(lots, key=lambda l: (l["expires"], l["id"]))
    fills = {order["id"]: [] for order in orders}
    short = {}

    # sorted() is stable, so orders on the same day keep their input order.
    for order in sorted(orders, key=lambda o: o["day"]):
        oid, day, need = order["id"], order["day"], order["qty"]

        usable = [l["id"] for l in fefo
                  if l["expires"] >= day and stock[l["id"]] > 0]

        if order.get("all_or_nothing", False):
            available = sum(stock[lid] for lid in usable)
            if need > available:
                # Allocate nothing; stock stays for later orders.
                if need > 0:
                    short[oid] = need
                continue

        for lid in usable:
            if need == 0:
                break
            take = min(need, stock[lid])
            stock[lid] -= take
            need -= take
            fills[oid].append((lid, take))

        if need > 0:
            short[oid] = need

    return {"fills": fills, "short": short, "remaining": stock}

動作の説明

この関数は、まずすべてのロットと注文を検証します。qty が負の値であるもの、または ID が重複しているものがあれば ValueError を送出するため、入力が無効な場合は何も引き当てられません。ロットは一度 (expires, id) で並べ替えられます。注文は day で並べ替えられます。Python のソートは安定なので、同じ日の注文は入力時の順序を保ちます。各注文について、まだ使用可能なロットを列挙します。条件は expires >= day かつ在庫が 0 より大きいことです。全量引当て(all-or-nothing)の注文が、使用可能な在庫の合計を超える数量を必要とする場合、その注文には何も割り当てられず、全数量が short に入ります。それ以外の場合は、FEFO の順序で使用可能なロットから在庫を取り、使用したロットごとに (lot_id, qty) のタプルを記録します。まだ満たされていない数量は short に入ります。数量が 0 の注文には空の引当てリストが与えられ、short には現れません。関数は在庫数量のコピーに対して動作し、入力の辞書は決して変更しません。

計算量: O(L log L + O log O + O·L)。ここで L はロットの数、O は注文の数です。対数を含む 2 つの項はロットと注文のソートから生じます。O·L の項は、各注文ごとにロットを一度ずつ走査することから生じます。使用メモリは O(L + O + F) です。F は引当てタプルの総数です。

Note: The short dict and remaining value semantics are unchanged.

def allocate(lots, orders):
    # 1. Validation
    seen_lot_ids = set()
    for lot in lots:
        if lot["qty"] < 0:
            raise ValueError(f"Negative lot quantity: {lot['qty']}")
        if lot["id"] in seen_lot_ids:
            raise ValueError(f"Duplicate lot ID: {lot['id']}")
        seen_lot_ids.add(lot["id"])

    seen_order_ids = set()
    for order in orders:
        if order["qty"] < 0:
            raise ValueError(f"Negative order quantity: {order['qty']}")
        if order["id"] in seen_order_ids:
            raise ValueError(f"Duplicate order ID: {order['id']}")
        seen_order_ids.add(order["id"])

    # Internal lot inventory
    remaining = {lot["id"]: lot["qty"] for lot in lots}
    lots_meta = {lot["id"]: lot["expires"] for lot in lots}

    fills = {order["id"]: [] for order in orders}
    short = {}

    # Sort orders by day (Python's Timsort is stable, preserving input order on ties)
    sorted_orders = sorted(orders, key=lambda o: o["day"])

    for order in sorted_orders:
        oid = order["id"]
        req_qty = order["qty"]
        day = order["day"]
        aon = order.get("all_or_nothing", False)

        # Identify and sort usable lots
        usable_lots = [
            lid for lid, exp in lots_meta.items()
            if exp >= day and remaining[lid] > 0
        ]
        usable_lots.sort(key=lambda lid: (lots_meta[lid], lid))

        total_usable = sum(remaining[lid] for lid in usable_lots)

        # Handle all-or-nothing check
        if aon and req_qty > total_usable:
            if req_qty > 0:
                short[oid] = req_qty
            continue

        # Allocate stock according to FEFO
        unfilled = req_qty
        for lid in usable_lots:
            if unfilled == 0:
                break
            take = min(remaining[lid], unfilled)
            if take > 0:
                remaining[lid] -= take
                unfilled -= take
                fills[oid].append((lid, take))

        if unfilled > 0:
            short[oid] = unfilled

    return {
        "fills": fills,
        "short": short,
        "remaining": remaining,
    }

計算量とその説明

• 時間計算量: ロットの数を $L$、注文の数を $O$ とします。入力の検証には $O(L + O)$ かかります。注文のソートには $O(O \log O)$ かかります。各注文について、利用可能なロットの抽出と並べ替えには $O(L \log L)$ かかり、在庫の引き当て（差し引き）には $O(L)$ かかります。したがって、すべての注文の処理には $O(O \cdot L \log L)$ かかります。全体の時間計算量は $\mathcal{O}(O \log O + O \cdot L \log L)$ です。
• 空間計算量: $\mathcal{O}(L + O \cdot \min(L, \text{平均引き当て分割数}))$ です。ロット、注文のメタデータ、引き当て履歴の追跡には、入力に対して線形の補助領域が必要なためです。

FEFO割当関数

def allocate(lots, orders):
    if any(l["qty"] < 0 for l in lots) or any(o["qty"] < 0 for o in orders):
        raise ValueError("Negative quantity found")
    
    lot_ids = [l["id"] for l in lots]
    if len(lot_ids) != len(set(lot_ids)):
        raise ValueError("Duplicate lot ID")
    
    order_ids = [o["id"] for o in orders]
    if len(order_ids) != len(set(order_ids)):
        raise ValueError("Duplicate order ID")
    
    remaining = {l["id"]: l["qty"] for l in lots}
    lot_data = {l["id"]: {"expires": l["expires"], "id": l["id"]} for l in lots}
    
    sorted_orders = sorted(enumerate(orders), key=lambda x: (x[1]["day"], x[0]))
    
    fills = {o["id"]: [] for o in orders}
    short = {}
    
    for _, order in sorted_orders:
        oid = order["id"]
        oday = order["day"]
        oqty = order["qty"]
        aon = order.get("all_or_nothing", False)
        
        usable_lots = [
            lid for lid, qty in remaining.items()
            if qty > 0 and lot_data[lid]["expires"] >= oday
        ]
        usable_lots.sort(key=lambda lid: (lot_data[lid]["expires"], lot_data[lid]["id"]))
        
        total_usable = sum(remaining[lid] for lid in usable_lots)
        
        if aon and oqty > total_usable:
            short[oid] = oqty
            continue
            
        allocated_for_order = []
        needed = oqty
        
        # Check if we can fulfill the order partially or fully
        temp_allocation = []
        for lid in usable_lots:
            if needed <= 0:
                break
            take = min(remaining[lid], needed)
            temp_allocation.append((lid, take))
            needed -= take
            
        if aon and needed > 0:
            short[oid] = oqty
            continue
            
        # Apply allocation
        for lid, take in temp_allocation:
            remaining[lid] -= take
            allocated_for_order.append((lid, take))
            
        fills[oid] = allocated_for_order
        if needed > 0:
            short[oid] = needed
            
    return {
        "fills": fills,
        "short": short,
        "remaining": remaining
    }

解説と計算量

allocate 関数はまず、負の数量と重複した ID を検証し、いずれかの制約に違反していれば ValueError を送出します。同じ日に属する注文の順序を決める際の並べ替えのために、元の注文の順番のインデックスを保持します。

日付順に並べられた各注文について、関数は有効期限が注文日以上で在庫が 0 でないロットを抽出します。これらのロットを FEFO のルールに従って並べ替えます。すなわち、expires の昇順、次に id の昇順です。all_or_nothing の注文で利用可能な在庫の合計が不足している場合は、その注文を飛ばします。それ以外の場合は、充足するか利用可能な在庫が尽きるまで、在庫を貪欲に差し引きます。

時間計算量

$L$ をロットの数、$O$ を注文の数とします。注文の並べ替えには $O(O \log O)$ かかります。$O$ 個の各注文について、ロットの抽出と並べ替えに $O(L \log L)$ かかります。したがって、全体の時間計算量は $O(O \log O + O \cdot L \log L)$ です。