概要

各日最大 \(L_i\) 冊まで・同じ日に同じ本は1回までという制約のもとで、各本 \(j\) を少なくとも \(R_j\) 回点検できるかを、必要条件かつ十分条件の不等式チェックに帰着して判定します。

考察

点検計画は、\(N\) 日 \(\times\) \(M\) 冊の \(0/1\) 行列で表せます（\(a_{i,j}=1\) なら \(i\) 日目に本 \(j\) を点検）：

• 行（各日）の合計：\(\sum_j a_{i,j} \le L_i\)
• 列（各本）の合計：\(\sum_i a_{i,j} \ge R_j\)
• さらに \(a_{i,j}\in\{0,1\}\)（同じ日に同じ本を複数回不可）

ここで「各本は少なくとも \(R_j\) 回」ですが、余計に点検しても得しません（行の上限を圧迫するだけ）なので、各本ちょうど \(R_j\) 回点検できるかを考えれば十分です。

---

重要な観察（部分集合に対する上限制約）

任意の本の集合 \(S\)（\(|S|=k\)）に注目します。

• \(i\) 日目に \(S\) の本を点検できる冊数は最大でも \(\min(L_i, k)\)
  （その日に点検できる総数が \(L_i\) 冊まで、かつ \(S\) の中の本は高々 \(k\) 冊なので）
• よって \(S\) 全体で必要な点検回数 \(\sum_{j\in S} R_j\) は、 [ \sum_{j\in S} Rj \le \sum{i=1}^N \min(L_i, k) ] を満たさないと不可能です。

これは（最大流の最小カットや二部グラフの次数条件として）必要条件であり、実は十分条件でもあります。

---

「全ての集合 \(S\)」をどうチェックするか

集合 \(S\) は \(2^M\) 通りあり全探索は不可能です。しかし右辺は \(k=|S|\) にしか依存しません。

そこで、固定したサイズ \(k\) に対して左辺 \(\sum_{j\in S} R_j\) を最大化するには、\(R_j\) が大きい本から \(k\) 冊選ぶのが最悪です。
つまり \(R\) を降順に並べて、 [ \text{demand}(k)=\sum{t=1}^{k} R{(t)} ] （上位 \(k\) 個の和）だけを見れば十分です。

結局、判定すべき条件は全ての \(k=1..M\) について [ \sum{t=1}^{k} R{(t)} \le \sum_{i=1}^N \min(L_i, k) ] となります。

素朴に右辺を毎回 \(N\) 個足すと \(O(NM)\) で間に合いません。そこで右辺を高速に計算します。

アルゴリズム

1. \(L\) を昇順にソートする。

2. \(R\) を降順にソートする。

3. \(k=1\) から \(M\) まで増やしながら以下を更新・判定する。

   • \(\text{demand} \leftarrow \text{demand} + R[k-1]\)（上位 \(k\) 個の和）
   • \(\sum_i \min(L_i,k)\)（capacity）を計算：
     • \(L_i \le k\) のものは \(\min(L_i,k)=L_i\)
     • \(L_i > k\) のものは \(\min(L_i,k)=k\)

   \(L\) が昇順なので、\(L_i \le k\) の範囲をポインタで進めつつ - \(L_i \le k\) の総和を sum_small - 残りは個数 \((N-idx)\) に対して一律 \(k\)

   よって [ \text{capacity} = \text{sum_small} + (N-idx)\cdot k ] - もし \(\text{demand} > \text{capacity}\) なら不可能なので No。

4. 最後まで破れなければ Yes。

計算量

• 時間計算量: \(O(N\log N + M\log M + (N+M))\)
• 空間計算量: \(O(N+M)\)

実装のポイント

• 判定条件は「全ての \(k\)」が必要です（\(k=M\) だけでは不十分）。

• \(\sum_{i=1}^N \min(L_i,k)\) を毎回 \(O(N)\) で計算すると間に合わないため、\(L\) を昇順ソートして二重ループを避けるのが核心です。

• R は「最悪の \(k\) 冊」を作るために 降順ソートして prefix sum を取ります。

  ソースコード

import sys

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    M = next(it)
    L = [next(it) for _ in range(N)]
    R = [next(it) for _ in range(M)]

    L.sort()
    R.sort(reverse=True)

    idx = 0
    sum_small = 0  # sum of L_i <= k
    demand = 0

    for k in range(1, M + 1):
        demand += R[k - 1]

        while idx < N and L[idx] <= k:
            sum_small += L[idx]
            idx += 1

        capacity = sum_small + (N - idx) * k
        if demand > capacity:
            print("No")
            return

    print("Yes")

if __name__ == "__main__":
    main()

---

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