概要

\(N\) 人のスタッフと \(M\) 件の仕事があり、各スタッフを条件を満たす仕事に最大 1 件ずつ割り当てるとき、完了できる仕事の最大件数を求める問題です。各スタッフの能力と仕事の要求値を比較する「最大マッチング」の問題ですが、ソートと貪欲法を用いることで効率的に解くことができます。

考察

1. 条件の整理

スタッフ \(i\) が仕事 \(j\) を担当できる条件は \(D_j \leq V_i \times T_j\) です。これをスタッフの作業効率 \(V_i\) について整理すると、以下のようになります。 $\(V_i \geq \frac{D_j}{T_j}\)\( \)V_i\( は整数であるため、仕事 \)j\( を完遂するために必要な最小の作業効率を \)R_j\( とすると、 \)\(R_j = \lceil \frac{D_j}{T_j} \rceil \quad (\text{\)D_j / T_j\( の小数点以下切り上げ})\)$ となります。プログラム上での整数の切り上げ計算は、(D + T - 1) // T と書くのが一般的です。

2. 貪欲法の適用

この問題は「能力値 \(V_i\) が要求値 \(R_j\) 以上のペアを最大いくつ作れるか」という問題に言い換えられます。 このような場合、「要求値が小さい仕事に対して、それをこなせる中で最も能力が低いスタッフを割り当てる」という貪欲な戦略が最適となります。なぜなら、能力が高いスタッフを簡単な仕事に使ってしまうと、後から出てくる難しい（要求値が高い）仕事に対処できるスタッフがいなくなってしまう可能性があるからです。

アルゴリズム

1. 必要効率の算出: 各仕事 \(j\) について、必要な最小効率 \(R_j = \lceil D_j / T_j \rceil\) を計算し、リストに格納します。
2. ソート: スタッフの能力リスト \(V\) と、仕事の必要効率リスト \(R\) をそれぞれ昇順（小さい順）にソートします。
3. 2ポインタ法による走査:
   • スタッフを指すポインタ v_ptr と、仕事を指すポインタ r_ptr を用意します。
   • V[v_ptr] >= R[r_ptr] ならば、そのスタッフはその仕事を担当できます。
     • 仕事を 1 件完了とし、両方のポインタを次に進めます。
   • V[v_ptr] < R[r_ptr] ならば、そのスタッフは現在の仕事（およびそれ以上に難しい仕事）を担当できません。
     • スタッフのポインタ v_ptr だけを次に進め、より能力の高いスタッフを探します。
4. どちらかのポインタが末尾に達するまで繰り返し、完了した仕事数を出力します。

計算量

• 時間計算量: \(O(N \log N + M \log M)\)
  • 必要効率の計算に \(O(M)\)、ソートに \(O(N \log N + M \log M)\)、2ポインタによる走査に \(O(N + M)\) かかります。ソートの部分が支配的です。
• 空間計算量: \(O(N + M)\)
  • スタッフの能力と仕事の必要効率を保持するためのメモリが必要です。

実装のポイント

• 高速な入出力: \(N, M\) が最大 \(2 \times 10^5\) と大きいため、Pythonでは input() を繰り返すよりも sys.stdin.read().split() などで一括で入力を取得する方が実行時間を短縮できます。

• 切り上げ処理: 浮動小数点数（D / T）を使うと、非常に大きな数値で精度誤差が生じる可能性があるため、整数演算 (D + T - 1) // T を用いるのが安全です。

  ソースコード

import sys

def solve():
    # Read all input at once and split by whitespace for efficiency
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    it = iter(input_data)
    
    # Read N (number of staff) and M (number of jobs)
    try:
        N = int(next(it))
        M = int(next(it))
    except StopIteration:
        return
    
    # Read staff work rates V
    V = [0] * N
    for i in range(N):
        V[i] = int(next(it))
        
    # Read job requirements D (workload) and T (time limit)
    # Calculate the minimum required work rate V_i for each job
    # The condition D_j <= V_i * T_j is equivalent to V_i >= D_j / T_j
    # Since V_i must be an integer, V_i >= ceil(D_j / T_j)
    R = [0] * M
    for i in range(M):
        D = int(next(it))
        T = int(next(it))
        # Integer calculation for ceil(D / T)
        R[i] = (D + T - 1) // T
        
    # Sort both staff work rates and job requirements in non-decreasing order
    V.sort()
    R.sort()
    
    # Use a greedy strategy with two pointers to find the maximum matching
    # We try to satisfy the smallest job requirement with the smallest possible staff work rate
    v_ptr = 0
    r_ptr = 0
    ans = 0
    
    while v_ptr < N and r_ptr < M:
        if V[v_ptr] >= R[r_ptr]:
            # This staff member is efficient enough to handle the current smallest job requirement
            ans += 1
            v_ptr += 1
            r_ptr += 1
        else:
            # This staff member is not efficient enough for the current job requirement.
            # Since requirements are sorted, this staff won't be able to handle any subsequent jobs.
            # Move to the next, more efficient staff member.
            v_ptr += 1
            
    # Output the maximum number of jobs that can be completed
    print(ans)

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-preview によって生成されました。