\(R\) は降順にソートされているとしてよいです。

答え

答えが Yes となるための必要十分条件は「全ての \(1 \leq K \leq M\) に対して、 \(\sum_{i=1}^{K}R_i \leq \sum_{j=1}^{N}\min(L_j,K)\) が成り立つ」(★)ことです。

証明

必要性

\(K\) を任意に取ります。 本 \(K+1\) 以降を無視し、本 \(1,2,\ldots,K\) についてだけ点検回数を守れるかを考えます。\(1\) つの本は \(1\) 日に高々 \(1\) 回しか点検できないため、 \(j\) 日目に点検できる本の数は高々 \(\min(L_j,K)\) です。よって、本 \(1,2,\dots,K\) ののべ点検回数を考えると \(\sum_{i=1}^{K}R_i \leq \sum_{j=1}^{N}\min(L_j,K)\) が成り立つことが必要です。

十分性

\(M\) に関する帰納法で示します。\(M=1\) のとき明らかです。
\(L\) を降順にソートすることで、\(L_1,\dots,L_{R_1}\) は \(0\) でないとしてよいです。（そうでないと \(K=1\) のケース \(R_1 \leq \sum_{j=1}^{N}\min(L_j,1)\) に反す）
本 \(1\) の点検を \(1\) 日目から \(R_1\) 日目に行うとします。残りの本について★が成り立つことを示せば十分です。即ち、

\(L'_j=\begin{cases} L_j - 1 & j \leq R_1\\ L_j & j>R_1 \end{cases}\)

と定めたとき、任意の \(1 \leq K \leq M-1\) に対して、 \(\sum_{i=1}^{K}R_{i+1} \leq \sum_{j=1}^{N}\min(L'_j,K)\) が成り立つことを示せばよいです。

\(L_{R_1+1}\leq K\) のとき

\(j >R_1\) のとき \(L_j \leq L_{R_1+1}\leq K\) なので、 \(\min(L_j,K)=\min(L_j,K+1)\) であることに注意すると、

\(\begin{aligned} \sum_{i=1}^{K}R_{i+1} &= \sum_{i=1}^{K+1}R_i-R_1\\ & \leq \sum_{j=1}^{N}\min(L_j,K+1) - R_1 \\ &= \sum_{i=1}^{R_1}\min(L_j,K+1)-R_1+\sum_{j=R_1+1}^{N}\min(L_j,K+1)\\ &=\sum_{i=1}^{R_1}\min(L_j-1,K)+\sum_{j=R_1+1}^{N}\min(L_j,K)\\ &=\sum_{j=1}^{N}\min(L'_j,K) \end{aligned}\)

より成り立つことが確かめられました。

\(L_{R_1+1} > K\) のとき

\(j \leq R_1\) のとき \(L'_j =L_j-1 \geq L_{R_1+1}-1 \geq K\) なので、 \(\min(L'_j,K)=K\) であることに注意すると

\(\begin{aligned} \sum_{i=1}^{K}R_{i+1} & \leq \sum_{i=1}^{K}R_1\\ &= K R_1 \\ & = \sum_{j=1}^{R_1}K \\ & = \sum_{j=1}^{R_1}\min(L'_j,K)\\ &\leq\sum_{j=1}^{N}\min(L'_j,K) \end{aligned}\)

より成り立つことが確かめられました。

実装

★の条件を定義式通りに計算すると、\(K\) 1 つあたり \(\Omega(N)\) 、全体で \(\Omega(NM)\) 時間かかるため TLE となります。

\(K=1,2,\dots,M\) の順に計算することを考えます。\(K\) が \(1\) 増えたとき、左辺の変化は明らかに \(O(1)\) で計算することができます。右辺は \(L\) のうち \(K\) より大きな要素の個数だけ値が増えます。この個数は \(L\) を予めソートしておくことで二分探索により \(O(\log N)\) で求めることができます。別の方法として、 \(L_j \leq K\) となる最大の \(j\) を管理する方法もあり、こちらは全体で \(O(M)\) となります。

いずれの解法もソートがボトルネックとなり、計算量は \(O(N\log N+M\log M)\) となります。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, m;
  cin >> n >> m;
  vector<int>l(n),r(m);
  for(int i=0; i<n; i++) cin >> l[i];
  for(int i=0; i<m; i++) cin >> r[i];
  sort(l.begin(), l.end());
  sort(r.rbegin(), r.rend());  // 降順

  int lpos = 0;
  long long ls = 0, rs = 0;
  for(int k=0; k<m; k++){
    rs += r[k];
    while(lpos < n && l[lpos] < k+1){
      lpos++;
    }
    ls += n - lpos;
    if(rs > ls){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}

実装例 (Python)

N, M = map(int, input().split())
L = list(map(int, input().split()))
R = list(map(int, input().split()))
L.sort()
R.sort()

Lpos = 0
LS = 0
RS = 0
for k in range(1, M+1):
  RS += R[-k]
  while Lpos < N and L[Lpos] < k:
    Lpos += 1
  LS += N - Lpos
  if RS > LS:
    print("No")
    exit()

print("Yes")