概要

\(M\) 種類の部品を組み合わせて製品を作る工場で、\(N\) 件の注文を順番に処理する問題です。各注文では全種類の部品を同じ数だけ消費するため、「最も在庫が少ない部品」の推移だけを追うことで効率的に解くことができます。

考察

素朴なアプローチとその限界

各注文 \(i\) に対して、「全 \(M\) 種類の部品の在庫が \(A_i\) 以上か確認し、条件を満たすなら \(M\) 種類すべての在庫を減らす」という処理を愚直に行うとどうなるでしょうか。 この場合、1つの注文ごとに最大 \(M\) 回の確認と更新が発生するため、全体の計算量は \(O(N \times M)\) となります。制約では \(N, M \leq 5 \times 10^5\) かつ \(N+M \leq 5 \times 10^5\) ですが、最悪の場合（例：\(N=2.5 \times 10^5, M=2.5 \times 10^5\)）には計算回数が \(6 \times 10^{10}\) 回を超えてしまい、実行時間制限に間に合いません。

重要な気づき：在庫の最小値に着目する

この問題の肝は、「どの部品も、減るタイミングと減る量が全く同じである」という点にあります。

1. ある注文を処理できる条件は「すべての部品の在庫 \(B_j \geq A_i\)」ですが、これは「在庫の最小値 \(\min(B_1, \dots, B_M) \geq A_i\)」と言い換えることができます。
2. 注文を処理して在庫を減らす際、すべての \(B_j\) から同じ値 \(A_i\) を引きます。このとき、部品間の在庫数の大小関係は変化しません。つまり、最初に在庫が最小だった部品は、その後もずっと最小（タイを含む）であり続けます。

したがって、個別の部品在庫をすべて管理する必要はなく、「全部品の中での最小在庫数」という1つの変数だけを管理すれば十分であると分かります。

アルゴリズム

1. 初期最小在庫の算出: 与えられた初期在庫 \(B_1, B_2, \ldots, B_M\) の中から最小値を探し、それを min_stock とします。
2. 注文のシミュレーション: 各注文 \(A_i\) (\(i = 1, \ldots, N\)) について、順番に以下の処理を行います。
   • もし min_stock >= A_i ならば：
     • 注文成功。min_stock から \(A_i\) を引き、成功件数を 1 増やす。
   • そうでなければ：
     • 在庫不足のため注文はキャンセル。何もしない。
3. 結果の出力: 最終的な成功件数を出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • 全部品の初期在庫から最小値を求めるのに \(O(M)\)。
  • 各注文を 1 回ずつ確認するループが \(O(N)\)。
  • 全体として入力サイズに比例する時間で処理可能です。
• 空間計算量: \(O(N + M)\)
  • 入力された \(A_i\) と \(B_j\) をリストに保持するために必要なメモリ量です。

実装のポイント

• 高速な入出力: \(N + M\) が最大 \(5 \times 10^5\) と大きいため、Python の標準的な input() を繰り返すと入力だけで時間がかかる場合があります。sys.stdin.read().split() などを用いて一括で読み込むのが効率的です。

• 最小値の取得: Python の min() 関数をリストやイテレータに適用することで、\(O(M)\) で効率よく最小値を取得できます。

  ソースコード

import sys

def main():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストにする
    # 大規模な入力（N, M <= 5 * 10^5）を効率的に処理するために sys.stdin.read().split() を使用
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 注文数 N と部品の種類数 M を取得
    n = int(input_data[0])
    m = int(input_data[1])
    
    # 全ての部品の在庫は、注文が成功するたびに同じ量（Ai）だけ減少する。
    # したがって、ある注文を処理できるかどうかは、その時点での「全部品の中の最小在庫数」に依存する。
    # 初めに最小在庫であった部品は、減少量がいずれの部品も等しいため、常に最小在庫（の一つ）であり続ける。
    # そのため、各部品の在庫を個別に管理する必要はなく、最小在庫の推移だけを追えばよい。
    
    # 部品の初期在庫 B_j は input_data のインデックス n+2 から n+m+1 に格納されている。
    # map関数とmin関数を用いて、初期在庫の最小値を効率的に求める。
    # スライス input_data[n+2 : n+m+2] は B_1 から B_M までの要素をカバーする。
    min_stock = min(map(int, input_data[n + 2 : n + m + 2]))
    
    # 実際に納品できた注文の件数をカウントする変数
    successful_orders = 0
    
    # 注文 A_i を順番に処理する。
    # 注文 A_i の必要数は input_data のインデックス 2 から n+1 に格納されている。
    for i in range(2, n + 2):
        required_amount = int(input_data[i])
        
        # 現在の最小在庫が必要数以上であれば、注文を処理できる
        if min_stock >= required_amount:
            # 注文を処理し、最小在庫を必要数分だけ減らす
            min_stock -= required_amount
            # 納品件数をインクリメント
            successful_orders += 1
        else:
            # 在庫が不足している場合、この注文はキャンセルされ、在庫は変化しない
            pass
            
    # 最終的に納品できた注文の件数を出力
    print(successful_orders)

if __name__ == '__main__':
    main()

---

この解説は gemini-3-flash-thinking によって生成されました。