概要

\(N\) 人のスタッフと \(M\) 件の仕事があり、各仕事には担当可能な条件（スタッフの効率が一定以上）があるとき、1対1でマッチングして完了できる仕事の最大件数を求める問題です。

考察

問題の言い換え

スタッフ \(i\) が仕事 \(j\) を担当できる条件は \(D_j \leq V_i \times T_j\) です。これを変形すると： $\(V_i \geq \frac{D_j}{T_j}\)$

つまり、各仕事 \(j\) には「必要最小効率」\(\lceil D_j / T_j \rceil\) があり、この値以上の効率を持つスタッフのみが担当できます。

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

全ての仕事とスタッフのペアを試す方法は \(O(NM)\) となり、\(N, M \leq 2 \times 10^5\) では最大 \(4 \times 10^{10}\) 回の計算が必要でTLEします。

貪欲法による解決

この問題は「仕事の割り当て」という典型的な貪欲法で解けます。

重要な観察: 必要最小効率が高い仕事ほど、担当できるスタッフの選択肢が少ないです。

例えば、必要最小効率が 10 の仕事は効率 10 以上のスタッフしか担当できませんが、必要最小効率が 5 の仕事は効率 5 以上のスタッフなら誰でも担当できます。

貪欲戦略: 1. 仕事を「必要最小効率が大きい順」に処理する 2. 各仕事に対して、条件を満たすスタッフの中で最も効率が低いスタッフを割り当てる

「最も効率が低いスタッフを選ぶ」理由は、効率が高いスタッフは後のより厳しい条件の仕事にも使える可能性があるため、温存しておきたいからです。

具体例

• スタッフの効率: [3, 5, 8]
• 仕事の必要最小効率: [6, 4, 2]

必要最小効率が大きい順に処理: 1. 必要最小効率 6 の仕事 → 効率 8 のスタッフを割り当て（条件を満たす最小） 2. 必要最小効率 4 の仕事 → 効率 5 のスタッフを割り当て 3. 必要最小効率 2 の仕事 → 効率 3 のスタッフを割り当て

結果: 3件全て完了可能

アルゴリズム

1. 各仕事 \(j\) の必要最小効率 \(\lceil D_j / T_j \rceil\) を計算する
2. 仕事を必要最小効率の大きい順にソートする
3. スタッフの効率を SortedList（平衡二分探索木）で管理する
4. 各仕事について順に処理:
   • 必要最小効率以上の効率を持つスタッフを二分探索で探す
   • 見つかれば、その中で最小の効率のスタッフを割り当て（リストから削除）、カウントを増やす
5. 最終的なカウントを出力する

計算量

• 時間計算量: \(O((N + M) \log N)\)
  • スタッフのソート: \(O(N \log N)\)
  • 仕事のソート: \(O(M \log M)\)
  • 各仕事の処理: \(O(M \log N)\)（二分探索と削除がそれぞれ \(O(\log N)\)）
• 空間計算量: \(O(N + M)\)
  • スタッフと仕事の情報を格納する配列

実装のポイント

1. 天井関数の計算: \(\lceil D_j / T_j \rceil\) は整数演算で (D + T - 1) // T として計算できます。

2. SortedListの使用: Pythonの標準ライブラリには平衡二分探索木がないため、sortedcontainers ライブラリの SortedList を使用します。これにより \(O(\log N)\) での挿入・削除・二分探索が可能になります。

3. bisect_leftの活用: available.bisect_left(min_v) で min_v 以上の最小の要素のインデックスを取得できます。インデックスが配列長未満なら条件を満たすスタッフが存在します。

   ソースコード

import sys
from sortedcontainers import SortedList

def solve():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    V = []
    for i in range(N):
        V.append(int(input_data[idx])); idx += 1
    
    jobs = []
    for j in range(M):
        D = int(input_data[idx]); idx += 1
        T = int(input_data[idx]); idx += 1
        jobs.append((D, T))
    
    # 各仕事jを担当できるスタッフの条件: D_j <= V_i * T_j
    # つまり V_i >= D_j / T_j (= ceil(D_j / T_j) 以上の整数)
    # 必要最小効率 = ceil(D_j / T_j) = (D_j + T_j - 1) // T_j
    
    # 貪欲法: 必要最小効率が大きい仕事から順に処理し、
    # 条件を満たすスタッフの中で最も効率が低いスタッフを割り当てる
    
    # 各仕事について必要最小効率を計算
    job_requirements = []
    for j, (D, T) in enumerate(jobs):
        min_v = (D + T - 1) // T  # ceil(D/T)
        job_requirements.append((min_v, j))
    
    # 必要最小効率が大きい順にソート
    job_requirements.sort(reverse=True)
    
    # スタッフの効率をSortedListで管理
    available = SortedList(V)
    
    count = 0
    for min_v, j in job_requirements:
        # min_v以上の効率を持つスタッフの中で最小のものを探す
        idx_staff = available.bisect_left(min_v)
        if idx_staff < len(available):
            # 条件を満たすスタッフが存在
            available.pop(idx_staff)
            count += 1
    
    print(count)

if __name__ == "__main__":
    solve()

---

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