概要

各注文で必要になる部品数は「全部品で同じ個数」なので、実は最小在庫の部品だけ見れば可否判定できる問題です。
累積で何個生産したかを管理し、各注文を順に処理すれば高速に解けます。

考察

この問題では、製品を \(x\) 個作るたびに、すべての部品在庫が \(x\) ずつ減ります。
つまり、どの時点でも各部品の在庫は

• 部品 \(j\) の残り在庫 = \(B_j - (\text{これまでに生産した総数})\)

となります。

ここで重要な観察は次です：

• 注文 \(i\)（必要数 \(A_i\)）を通す条件は
  すべての \(j\) で
  \(B_j - used \ge A_i\)
• これは
  \(used + A_i \le B_j \ (\forall j)\)
• よって
  \(used + A_i \le \min_j B_j\)

つまり、判定に必要なのは \(\min(B)\) だけです。
各部品を毎回チェックする必要はありません。

---

素朴に「各注文ごとに全 \(M\) 種類を確認」すると \(O(NM)\) になり、
最大で \(5\times10^5 \times 5\times10^5\) と到底間に合いません。

そこで、

• 最小在庫 min_b = min(B) を先に求める
• used = これまでに納品できた注文で生産した総数
• 各注文 \(a\) について
  used + a <= min_b なら採用（used += a, ans += 1）
  そうでなければキャンセル

とすれば、1注文あたり \(O(1)\) で処理できます。

アルゴリズム

1. 入力を受け取る。
2. min_b = min(B) を求める。
3. used = 0, ans = 0 で初期化。
4. 注文列 A を先頭から順に見る。
   • もし used + a <= min_b なら、その注文は納品可能：
     • used += a
     • ans += 1
   • それ以外はキャンセル（何もしない）。
5. ans を出力。

計算量

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

実装のポイント

• used や used + a は最大で \(5\times10^5 \times 10^9\) 程度になりうるので、言語によっては 64bit 整数が必要です（Python は自動で多倍長なので問題なし）。

• 注文がキャンセルされた場合、在庫は減らない（= used を増やさない）点を忘れないようにします。

  ソースコード

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()))

    min_b = min(B)
    used = 0
    ans = 0

    for a in A:
        if used + a <= min_b:
            used += a
            ans += 1

    print(ans)

if __name__ == "__main__":
    main()

---

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