概要

各仕事をこなすのに必要な「最低作業効率」を計算しておき、スタッフの作業効率と仕事の要求を小さい順に並べて貪欲に割り当てることで、完了できる仕事数の最大値を求めます。

考察

仕事 \(j\) をスタッフ \(i\) が担当できる条件は
\(D_j \le V_i \times T_j\)
です。これを \(V_i\) について整理すると
\(V_i \ge \dfrac{D_j}{T_j}\)
となります。

ただし \(V_i\) は整数なので、仕事 \(j\) に必要な最低の作業効率は

• \(\left\lceil \dfrac{D_j}{T_j} \right\rceil\)

です。つまり各仕事は「必要効率 \(req_j\) 以上のスタッフなら誰でもよい」という単純な条件に置き換えられます。

素朴な方法が難しい理由

• 各仕事について「担当可能なスタッフ」を探して割り当てる、ということを愚直にやると最悪で \(O(NM)\) になり、\(N,M \le 2\times 10^5\) では到底間に合いません。
• 二部マッチングとして解くこともできますが、グラフが巨大になりやすく（辺数が膨大）、同様に非現実的です。

どう解決するか（重要な気づき）

仕事は「必要効率 \(req_j\)」という1つの値に圧縮でき、条件は「スタッフの効率がそれ以上かどうか」だけになります。
この形なら、

• 要求が小さい仕事から順に、
• それを満たせる最小のスタッフを割り当てる

という貪欲法が最適になります。

（直感）小さい要求の仕事に高性能スタッフを使ってしまうと、後で大きい要求の仕事をこなせるスタッフが足りなくなる可能性があるため、「ギリギリ満たせる最小のスタッフ」を使うのが得です。

アルゴリズム

1. 各仕事 \((D_j, T_j)\) から必要効率を計算する
   \(req_j = \left\lceil \dfrac{D_j}{T_j} \right\rceil = \left\lfloor \dfrac{D_j + T_j - 1}{T_j} \right\rfloor\)
2. スタッフの効率配列 \(V\) を昇順ソートする。
3. 必要効率配列 \(req\) も昇順ソートする。
4. 2本のポインタで貪欲にマッチングする：
   • \(V[i] \ge req[j]\) なら仕事 \(j\) はスタッフ \(i\) に割り当て可能なので採用（答え+1、\(i\) と \(j\) を両方進める）
   • そうでなければスタッフ \(i\) では足りないので次のスタッフへ（\(i\) だけ進める）

具体例

スタッフ効率 \(V=[2,5,6]\)、仕事の必要効率 \(req=[1,5,7]\) とします（既にソート済み）。

• \(2 \ge 1\) → 割り当て（1件達成）
• \(5 \ge 5\) → 割り当て（2件達成）
• \(6 \not\ge 7\) → もう割り当て不可（終了）

最大2件になります。

計算量

• 時間計算量: \(O(N\log N + M\log M)\)（ソートが支配的、マッチングは \(O(N+M)\)）
• 空間計算量: \(O(N + M)\)（配列保持）

実装のポイント

• 必要効率の計算は切り上げ除算：\(req = (D + T - 1) // T\)

• ソート後の貪欲マッチングは「小さい要求から順に、満たせる最小スタッフを使う」ことを2ポインタで実現する

• \(D, T, V\) は最大 \(10^9\) ですが、計算は整数の範囲で安全に扱えます（Python の int なら問題ありません）

  ソースコード

import sys

def main():
    it = list(map(int, sys.stdin.buffer.read().split()))
    if not it:
        return
    idx = 0
    N = it[idx]; M = it[idx + 1]; idx += 2

    V = it[idx:idx + N]
    idx += N

    req = [0] * M
    for j in range(M):
        D = it[idx]; T = it[idx + 1]; idx += 2
        req[j] = (D + T - 1) // T

    V.sort()
    req.sort()

    i = j = 0
    ans = 0
    while i < N and j < M:
        if V[i] >= req[j]:
            ans += 1
            i += 1
            j += 1
        else:
            i += 1

    print(ans)

if __name__ == "__main__":
    main()

---

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