概要

スタッフと仕事の組み合わせの中で、条件を満たす最大マッチング数を求める問題です。

考察

この問題では、各仕事に対し「必要な作業量 \(D_j\)」と「制限時間 \(T_j\)」が与えられており、スタッフ \(i\) の作業効率 \(V_i\) で仕事を完了できるかどうかを判定します。
具体的には、staff が job を処理できる条件は次のように表されます：

\[ D_j \leq V_i \times T_j \quad \Leftrightarrow \quad \frac{D_j}{T_j} \leq V_i \]

ただし、整数演算で扱うために、必要な最低限の能力値は次のように天井関数を用いて求められます：

\[ \text{req}_j = \left\lceil \frac{D_j}{T_j} \right\rceil = \left\lfloor \frac{D_j + T_j - 1}{T_j} \right\rfloor \]

素朴な方法として考えられるのは、すべてのスタッフと仕事のペアについてチェックを行う方法（全探索）ですが、これは最悪の場合 \(O(NM)\) の計算量となり、制約 \(N, M \leq 2 \times 10^5\) では間に合いません。

そこで、効率的にマッチングを行うために次の貪欲法を利用します：

• スタッフも仕事もそれぞれ「能力値」または「必要能力値」で昇順にソートします。
• 能力値の低いスタッフから見て行き、現在見ているスタッフが対応可能な最小の必要能力値の仕事を割り当てていきます。

これは、小さいもの同士からマッチングさせていく典型的な貪欲戦略であり、最適解を得ることができます。

アルゴリズム

1. 各仕事の必要能力値 \(\text{req}_j = \left\lceil \frac{D_j}{T_j} \right\rceil\) を計算する。
2. スタッフの能力値リスト \(V\) と仕事の必要能力値リスト \(\text{requirements}\) をともに昇順にソートする。
3. スタッフを一人ずつ見ながら、その人が対応可能な最も小さな必要能力値の仕事を貪欲に割り当てる。
   • 双方ともソートされているので、前から順番に一致を見つけていけば良い。
4. 割り当てた仕事数をカウントして出力する。

例：

例えば、以下の入力を考えます：

N = 3, M = 3
V = [2, 3, 1]
jobs = [(6,2), (3,1), (4,2)]

• 必要能力値 reqs = [3, 3, 2]
• ソート後 V = [1, 2, 3], reqs = [2, 3, 3]

staff 1 (ability=1): req=2 → 不可
staff 2 (ability=2): req=2 → OK (count++)
staff 3 (ability=3): req=3 → OK (count++)

→ 合計2件完了可能

計算量

• 時間計算量: \(O(N \log N + M \log M)\) （主にソートによる）
• 空間計算量: \(O(N + M)\) （配列保存分）

実装のポイント

• 必要能力値の計算は、整数での天井除算を使うこと（誤差回避のため）。
• スタッフ・仕事両方をソートすることを忘れない。
• 双方向ソート後に単純な線形走査で十分高速に動作する。

## ソースコード

```python
import sys
import heapq

def solve():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    
    V = list(map(int, data[2:2+N]))
    jobs = []
    index = 2 + N
    for _ in range(M):
        D = int(data[index])
        T = int(data[index+1])
        jobs.append((D, T))
        index += 2

    # 必要最低限の能力値を計算（ceil(D/T)）
    requirements = [(jobs[i][0] + jobs[i][1] - 1) // jobs[i][1] for i in range(M)]
    
    # 各能力値を持つスタッフを昇順にソート
    V.sort()
    
    # 各仕事の必要能力値を昇順にソート
    requirements.sort()
    
    # 貪欲法：能力値が低いスタッフから、必要能力値が低い仕事にマッチングしていく
    j = 0
    count = 0
    for i in range(N):
        if j < M and requirements[j] <= V[i]:
            count += 1
            j += 1
            
    print(count)

if __name__ == "__main__":
    solve()

---

この解説は qwen3-coder-480b によって生成されました。