概要

\(N\) 件の注文を順番に処理し、\(M\) 種類の部品の在庫が足りる場合のみ製品を生産・納品するとき、実際に納品できた注文の件数を求める問題です。

考察

重要な気づき：ボトルネックは「最も在庫の少ない部品」

製品を \(A_i\) 個作るには、すべての種類の部品がそれぞれ \(A_i\) 個以上必要です。注文を処理すると、すべての部品が同じ数（\(A_i\) 個）ずつ減ります。つまり、各部品の在庫は常に「初期在庫の差」を保ったまま一様に減っていきます。

具体例で考えてみましょう。\(M = 3\) で初期在庫が \(B = [10, 7, 15]\) のとき：

• 注文を受けるかどうかは、すべての部品が \(A_i\) 個以上あるか で決まります。
• すべての部品が同じ量だけ減るので、常に一番少ない部品が制約になります。
• 初期在庫の最小値は \(\min(B) = 7\) です。

ある注文を処理した後の各部品の在庫は \([10 - S, 7 - S, 15 - S]\)（\(S\) は累計生産数）となります。次の注文で \(A_i\) 個作れるかは、最小の \(7 - S \geq A_i\) かどうかで決まります。

素朴なアプローチの問題点

各注文ごとに \(M\) 種類の部品すべてをチェックすると \(O(N \times M)\) となり、\(N, M\) が最大 \(5 \times 10^5\) のとき TLE になる可能性があります。

解決策

上記の考察から、\(M\) 種類の部品を個別に管理する必要はなく、\(\min(B)\) だけを覚えておけば十分です。残りの在庫（ボトルネック部品の在庫）を \(1\) つの変数で管理し、各注文を \(O(1)\) で処理できます。

アルゴリズム

1. 初期在庫の最小値 \(\text{remaining} = \min(B_1, B_2, \ldots, B_M)\) を求める。
2. 注文を \(i = 1, 2, \ldots, N\) の順に処理する：
   • \(\text{remaining} \geq A_i\) なら、納品可能。\(\text{remaining}\) から \(A_i\) を引き、カウントを \(1\) 増やす。
   • \(\text{remaining} < A_i\) なら、キャンセル。何もしない。
3. 最終的なカウントを出力する。

計算量

• 時間計算量: \(O(N + M)\)
  • \(\min(B)\) の計算に \(O(M)\)、注文の処理に \(O(N)\)
• 空間計算量: \(O(N + M)\)
  • 入力の読み込みに必要な分（在庫は最小値だけ保持すれば \(O(1)\) で済む）

実装のポイント

• 高速な入力: \(N + M\) が最大 \(5 \times 10^5\) と大きいため、sys.stdin.buffer.read() で一括読み込みを行い、入力のオーバーヘッドを減らしています。

• 整数のオーバーフロー: \(A_i, B_j\) が最大 \(10^9\) ですが、Python は任意精度整数なのでオーバーフローの心配はありません。

• 核心はシンプル: 全部品が同じ量ずつ減るという構造に気づけば、問題は「初期在庫の最小値を予算として、注文を先頭から貪欲に処理する」というシンプルな問題に帰着します。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    A = [int(input_data[idx + i]) for i in range(N)]; idx += N
    B = [int(input_data[idx + i]) for i in range(M)]; idx += M
    
    min_B = min(B)
    count = 0
    remaining = min_B
    
    for i in range(N):
        if remaining >= A[i]:
            remaining -= A[i]
            count += 1
    
    print(count)

if __name__ == '__main__':
    main()

---

この解説は claude4.6opus-thinking によって生成されました。