概要

\(N\) 日間で \(M\) 冊の本を点検する際、各日の点検可能冊数の制約と各本の必要点検回数の制約を同時に満たせるかを判定する問題です。これは二部グラフのマッチング問題の一種で、貪欲法と累積和を用いて効率的に解くことができます。

考察

問題の言い換え

• 各本 \(j\) は \(R_j\) 個の異なる日に点検される必要がある（同じ日に同じ本を複数回点検できないため）
• 各日 \(i\) には最大 \(L_i\) 冊の本しか点検できない

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

二部グラフ（日と本）の最大マッチングを直接計算すると、\(O(NM)\) 以上の計算量がかかり、\(N, M \leq 2 \times 10^5\) の制約では TLE になります。

重要な観察

点検回数が多く必要な本ほど「良い日」（点検可能冊数が多い日）を多く使う必要があります。

ソートして考える： - \(L\) を降順にソート：\(l_1 \geq l_2 \geq \cdots \geq l_N\) - \(R\) を降順にソート：\(r_1 \geq r_2 \geq \cdots \geq r_M\)

Hall の定理的な条件： 「点検回数が \(k\) 番目に多い本まで」を考えたとき、それらの本が必要とする総点検回数を、各日が提供できる点検回数で賄えるかをチェックします。

具体的には、各 \(k\) について： $\(\sum_{i=1}^{k} r_i \leq \sum_{j=1}^{N} \min(l_j, k)\)$

右辺の意味： 上位 \(k\) 冊の本に対して、各日が提供できる点検回数の合計。日 \(j\) は \(l_j\) 冊まで点検できますが、本は \(k\) 冊しかないので \(\min(l_j, k)\) 回分しか貢献できません。

具体例

\(N = 3, M = 2\)、\(L = [3, 2, 1]\)、\(R = [2, 2]\) の場合： - \(k = 1\): 左辺 \(= 2\)、右辺 \(= \min(3,1) + \min(2,1) + \min(1,1) = 1+1+1 = 3\) → OK - \(k = 2\): 左辺 \(= 2+2 = 4\)、右辺 \(= \min(3,2) + \min(2,2) + \min(1,2) = 2+2+1 = 5\) → OK

アルゴリズム

1. \(L\) と \(R\) をそれぞれ降順にソートする
2. \(\sum R > \sum L\) なら即座に No（必要条件）
3. \(cnt[k]\) = 「\(L_i \geq k\) となる日の数」を計算
4. 各 \(k = 1, 2, \ldots, M\) について以下をチェック：
   • 左辺：\(\sum_{i=1}^{k} r_i\)（累積和で計算）
   • 右辺：\(\sum_{j=1}^{k} cnt[j]\)（\(\sum_{j=1}^{N} \min(l_j, k) = \sum_{j=1}^{k} cnt[j]\) という関係を利用）
   • 左辺 > 右辺 なら No
5. すべての \(k\) でOKなら Yes

右辺の式の補足

\(\sum_{j=1}^{N} \min(l_j, k)\) は「各日が提供できる点検回数（上限 \(k\)）の合計」です。 これは \(\sum_{t=1}^{k} (\text{\)lj \geq t\( となる日数})\) と等しく、つまり $\sum{t=1}^{k} cnt[t]$ となります。

計算量

• 時間計算量: \(O(N \log N + M \log M)\)（ソートがボトルネック）
• 空間計算量: \(O(N + M)\)（配列の格納）

実装のポイント

• \(cnt[k]\) の計算では、\(L_i > M\) の場合も正しく処理する（\(M\) にクリップ）

• \(cnt\) 配列は後ろから累積和を取ることで「\(k\) 以上」の個数を求める

• \(R\) の要素数が \(k\) より少ない場合（\(k > M\)）も考慮が必要だが、ループは \(M\) までで十分

  ソースコード

def solve():
    import sys
    from collections import defaultdict
    
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    L = [int(input_data[idx + i]) for i in range(N)]
    idx += N
    R = [int(input_data[idx + i]) for i in range(M)]
    idx += M
    
    # 各本jはR[j]回点検が必要、同じ日に同じ本を複数回点検不可
    # 各日iには最大L[i]冊点検可能
    
    # これはマッチング問題として考えられる
    # 本jを点検する日の集合を選ぶ（|集合| >= R[j]）
    # 各日iに選ばれる本の数は <= L[i]
    
    # Hall's theorem的なアプローチ:
    # R[j]が大きい本から順に、できるだけ余裕のある日に割り当てる
    
    # 貪欲法: R[j]が大きい本は多くの日が必要
    # 各本は最大N日まで点検可能（各日1回ずつ）
    
    # 条件: 各本jをR[j]個の異なる日に割り当てる
    # 各日iには最大L[i]冊
    
    # これは二部グラフのマッチング問題だが、N, M が大きいので効率的な方法が必要
    
    # 考え方を変える:
    # sum(R) <= sum(L) は必要条件
    # また、R[j] <= N も必要（各日1回なので最大N回）
    
    # より強い条件: 
    # L[i]の大きい順にソートして、R[j]の大きい順にソートして
    # 割り当てを考える
    
    # 実は、この問題は以下のように解ける:
    # L を降順ソート、R を降順ソート
    # L[0], L[1], ..., L[N-1] (降順)
    # R[0], R[1], ..., R[M-1] (降順)
    # 
    # 本jはR[j]日必要で、それはL値が大きい上位R[j]日に割り当て可能
    # 
    # 条件: 各k (1 <= k <= N) について
    # 「点検回数がk回以上必要な本の数」 <= 「1日にk冊以上点検できる日数」の累積
    
    # count_R[k] = R[j] >= k となる本の数
    # count_L[k] = L[i] >= k となる日の数
    # 
    # 各本jがR[j]回点検されるには、上位R[j]日を使う
    # k日目までに処理できる総点検回数 = sum of min(L[i], k) for top k days
    
    # 別の考え方:
    # Rを降順ソート: r_1 >= r_2 >= ... >= r_M
    # Lを降順ソート: l_1 >= l_2 >= ... >= l_N
    # 
    # 本iは r_i 個の日が必要
    # 日jは l_j 冊まで対応可能
    # 
    # 条件: 任意のkについて、sum(r_1, ..., r_k) <= sum(min(l_1, k), ..., min(l_N, k))
    # つまり、上位k冊の本が必要とする総点検回数 <= 各日が上位k冊に提供できる点検回数の合計
    
    R_sorted = sorted(R, reverse=True)
    L_sorted = sorted(L, reverse=True)
    
    # 必要条件: sum(R) <= sum(L)
    if sum(R) > sum(L):
        print("No")
        return
    
    # 各kについてチェック
    # sum(R_sorted[:k]) <= sum(min(l, k) for l in L_sorted)
    
    # 効率的に計算するために、Lの累積を使う
    # cnt[k] = L[i] >= k となる日の数
    cnt = [0] * (M + 2)
    for l in L_sorted:
        if l <= M:
            cnt[l] += 1
        else:
            cnt[M] += 1
    
    # cnt[k] を累積（k以上の数）
    for k in range(M, 0, -1):
        cnt[k] += cnt[k + 1]
    
    # sum(min(l, k) for l in L_sorted) = sum over i of min(L_sorted[i], k)
    # = sum_{j=1}^{k} cnt[j]  (cnt[j] = L[i] >= j となる数)
    
    prefix_R = 0
    capacity = 0
    
    for k in range(1, M + 1):
        if k <= len(R_sorted):
            prefix_R += R_sorted[k - 1]
        capacity += cnt[k]
        
        if prefix_R > capacity:
            print("No")
            return
    
    print("Yes")

solve()

---

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