概要

\(N\) 日間の蔵書点検において、各日の最大点検冊数 \(L_i\) と、各本の必要点検回数 \(R_j\) が与えられたとき、すべての条件を同時に満たす点検スケジュールが作成可能かを判定する問題です。この問題は、\((0,1)\) 行列の存在条件に関する「ゲイル＝ライザーの定理 (Gale-Ryser theorem)」の考え方を応用することで効率的に解くことができます。

考察

この問題は、「行の和が \(L_i\) 以下、列の和が \(R_j\) 以上となる \(N \times M\) の \((0,1)\) 行列が存在するか」という問題に置き換えられます。ここで、同じ日に同じ本を点検できないという制約が、行列の各要素が \(0\) か \(1\) である（同じ要素を \(2\) 以上にできない）ことに対応します。

重要な気づき

必要点検回数が多い本から順に \(k\) 冊選んだとき、それらの本を点検するために必要な延べ回数は \(\sum_{j=1}^k R_j\) です。 一方で、ある \(i\) 日目にこれら \(k\) 冊の本を点検できる最大数は、以下の \(2\) つの制限のうち小さい方になります。 1. その日の点検可能枠数： \(L_i\) 2. 選んだ本の種類数： \(k\) （1日に同じ本は1回しか点検できないため）

したがって、 \(i\) 日目にこれら \(k\) 冊に対して提供できる枠は \(\min(k, L_i)\) 冊分となります。 すべての \(k\) (\(1 \leq k \leq M\)) について、以下の条件が満たされていれば、点検基準を満たすことが可能です。 $\(\sum_{j=1}^k R_j \leq \sum_{i=1}^N \min(k, L_i)\)$

もし、ある \(k\) において左辺（要求）が右辺（供給の限界）を上回ってしまうと、どのようにスケジュールを組んでも条件を満たすことはできません。

アルゴリズム

効率的に判定を行うために、以下の手順で処理を行います。

1. ソート:
   • 必要回数 \(R\) を降順にソートします（厳しい条件から順に累積和をとるため）。
   • 日ごとの上限 \(L\) を昇順にソートします（\(\min(k, L_i)\) の計算を効率化するため）。
2. 累積和の準備:
   • \(L\) の累積和を計算しておきます。
3. 判定ループ:
   • \(k = 1\) から \(M\) まで順に、\(\sum_{j=1}^k R_j\) と \(\sum_{i=1}^N \min(k, L_i)\) を比較します。
   • 右辺の \(\sum \min(k, L_i)\) は、\(L_i < k\) となる日の \(L_i\) の総和と、\(L_i \geq k\) となる日の \(k\) の総和に分けて計算します。\(L\) がソートされているため、二分探索やポインタの移動で「\(L_i < k\) となる境界」を高速に見つけることができます。

計算量

• 時間計算量: \(O(N \log N + M \log M)\)
  • \(L\) と \(R\) のソートに \(O(N \log N + M \log M)\) かかります。
  • 判定ループは \(M\) 回で、その中の境界探索（ポインタ移動）は全体で \(N\) 回のため \(O(N + M)\) です。
• 空間計算量: \(O(N + M)\)
  • 配列 \(L, R\) および累積和の保持に利用します。

実装のポイント

• \(\min(k, L_i)\) の高速な計算: ループ内で毎回 \(N\) 日分を走査すると \(O(NM)\) になり間に合いません。\(L\) を昇順ソートしておき、「\(L_i\) が \(k\) 未満である範囲」のインデックスを idx とすると、右辺は (Lの idx までの累積和) + (N - idx) * k と \(O(1)\) で計算できます。

• 大きな入力: \(N, M\) が \(2 \times 10^5\) と大きいため、Pythonでは sys.stdin.read().split() などを用いて高速に入力を読み込むのが無難です。

  ソースコード

import sys

# 競技プログラミングのエキスパートとして、効率的なアルゴリズムを用いて
# この問題を解決します。この問題は、各本を「少なくとも R_j 回」点検し、
# 各日に「最大 L_i 冊」点検するという制約のもとで、点検が可能かどうかを
# 判定するものです。これは、(0,1)行列の存在条件に関するゲイル＝ライザーの定理
# (Gale-Ryser theorem) の考え方を応用することで、効率的に解くことができます。

def solve():
    # 標準入力からすべてのデータを一度に読み込みます
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 日数, M: 本の冊数
    N = int(input_data[0])
    M = int(input_data[1])
    
    # L: 各日に点検可能な最大冊数, R: 各本に必要な最小点検回数
    L = list(map(int, input_data[2:2+N]))
    R = list(map(int, input_data[2+N:2+N+M]))
    
    # 判定条件を効率的にチェックするために、Rを降順、Lを昇順にソートします。
    # Rを降順にするのは、必要回数が多い本から順に累積和をとるためです。
    R.sort(reverse=True)
    L.sort()
    
    # Lの累積和を計算しておきます。これにより、任意のkに対して
    # sum_{i=1}^N min(k, L_i) を O(1) または O(log N) で計算可能になります。
    L_pref = [0] * (N + 1)
    current_L_sum = 0
    for i in range(N):
        current_L_sum += L[i]
        L_pref[i+1] = current_L_sum
        
    # 判定条件: すべての k (1 <= k <= M) について、
    # 必要な点検回数の上位 k 冊の合計が、それら k 冊に対して全日程で提供可能な
    # 最大枠数を超えていないかを確認します。
    # 式: sum_{j=1}^k R_j <= sum_{i=1}^N min(k, L_i)
    
    idx = 0
    R_sum_k = 0
    for k in range(1, M + 1):
        # Rの累積和（上位 k 冊の合計）
        R_sum_k += R[k-1]
        
        # L[idx] が k 未満である間、idxをインクリメントします。
        # k はループごとに1ずつ増加するため、idxは単調増加します。
        while idx < N and L[idx] < k:
            idx += 1
        
        # sum_{i=1}^N min(k, L_i) の計算:
        # 1. L_i < k の場合、min(k, L_i) = L_i (累積和 L_pref[idx] を使用)
        # 2. L_i >= k の場合、min(k, L_i) = k (残りの (N - idx) 日分)
        current_max_capacity = L_pref[idx] + (N - idx) * k
        
        # もし必要回数が供給可能な枠数を超えたら、達成不可能
        if R_sum_k > current_max_capacity:
            print("No")
            return

    # すべての k について条件を満たせば達成可能
    print("Yes")

if __name__ == '__main__':
    solve()

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