概要

各注文をそのままシミュレーションすると、毎回 \(M\) 種類すべての在庫確認が必要で重くなります。
この問題の本質は「成功した注文では、すべての部品の在庫が同じ個数だけ減る」ことにあり、実は 最小在庫だけ見れば十分 です。

考察

注文 \(i\) で \(A_i\) 個生産できるかどうかは、

• すべての部品の在庫が \(A_i\) 個以上あるか

で決まります。

重要な気づき

製品を \(x\) 個作ると、全部品の在庫がそれぞれ \(x\) 個ずつ減ります。
つまり、成功した注文の合計生産数を \(S\) とすると、部品 \(j\) の現在の在庫は

\(B_j - S\)

です。

したがって、ある注文 \(A_i\) を処理できる条件は

\(B_j - S \ge A_i \quad (\forall j)\)

です。これは

\(\min(B_1, B_2, \ldots, B_M) - S \ge A_i\)

と同値です。

つまり、各部品を個別に管理しなくても、

• 現在の「最小在庫」だけを 1 つ持っておけばよい

と分かります。

なぜ素朴な方法ではだめか

素朴にやると、各注文ごとに全部品を確認して、成功したら全部品を減らすことになります。
すると 1 回の注文で \(O(M)\)、全体で \(O(NM)\) です。

制約は \(N, M \le 5 \times 10^5\) なので、\(O(NM)\) は最大で非常に大きくなり、到底間に合いません。

どう解決するか

最初に

\(\text{remain} = \min(B)\)

を求めます。
これは「今あと何個までなら、どの部品も共通して使えるか」を表しています。

各注文 \(A_i\) について：

• \(A_i \le \text{remain}\) なら受注成功
  • 答えを 1 増やす
  • \(\text{remain} \leftarrow \text{remain} - A_i\)
• そうでなければキャンセル
  • 何も変えない

これだけで正しく処理できます。

具体例

例えば

• \(B = [10, 7, 12]\)

なら最小在庫は \(7\) です。

注文が

• \(A = [3, 5, 2]\)

だったとします。

最初：\(\text{remain} = 7\)

1. 注文 \(3\)
   \(3 \le 7\) なので成功
   \(\text{remain} = 7 - 3 = 4\)

2. 注文 \(5\)
   \(5 > 4\) なので失敗
   \(\text{remain}\) はそのまま \(4\)

3. 注文 \(2\)
   \(2 \le 4\) なので成功
   \(\text{remain} = 4 - 2 = 2\)

よって成功件数は \(2\) 件です。

実際に各部品の在庫で考えても、

• 最初：\([10, 7, 12]\)
• 3 個生産後：\([7, 4, 9]\)
• 5 個は無理
• 2 個生産後：\([5, 2, 7]\)

となり、確かに一致します。

アルゴリズム

1. 配列 \(B\) の最小値を求め、remain とする。
2. 答え ans = 0 で初期化する。
3. 注文を先頭から順に見る。
   • もし \(A_i \le \text{remain}\) なら
     • ans += 1
     • remain -= A_i
   • そうでなければ何もしない
4. ans を出力する。

計算量

• 時間計算量: \(O(N + M)\)
• 空間計算量: \(O(1)\)（入力配列を除く）

実装のポイント

• 各部品の在庫を毎回更新する必要はありません。min(B) だけを持てば十分です。

• 注文が失敗したときは、在庫は変化しないので remain も変えません。

• A_i や B_j は最大 \(10^9\) ですが、Python の整数ならそのまま扱えます。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    remain = min(B)
    ans = 0
    
    for x in A:
        if x <= remain:
            ans += 1
            remain -= x
    
    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.4-high によって生成されました。