概要

各印刷依頼を処理可能なプリンターに割り当て、すべての依頼が完了する最小時刻を求めます。
「ある時刻 \(x\) までに全依頼を処理できるか？」を判定し、その結果を使って答えを二分探索します。

考察

プリンター \(i\) は、1件の依頼を処理するのに常に \(T_i\) かかります。
そのため、時刻 \(x\) までにプリンター \(i\) が処理できる依頼数は

\( \left\lfloor \frac{x}{T_i} \right\rfloor \)

件です。

つまり、時刻 \(x\) が決まっているとき、問題は次のように言い換えられます。

• プリンター \(i\) は最大で \( \left\lfloor \frac{x}{T_i} \right\rfloor \) 件まで依頼を処理できる
• ただし、ページ数 \(P_j\) の依頼は \(W_i \geq P_j\) のプリンターにしか割り当てられない
• すべての依頼を割り当てられるか？

ここで重要なのは、時刻 \(x\) までに処理できるなら、より長い時刻 \(x+1\) やそれ以上でも必ず処理できるということです。
したがって、答えに対して二分探索ができます。

判定方法

依頼をページ数の大きい順、プリンターを処理できる最大ページ数 \(W_i\) の大きい順に並べます。

ページ数が大きい依頼ほど、処理できるプリンターが限られます。
そのため、大きい依頼から順に、処理能力の高いプリンターへ貪欲に割り当てるのが自然です。

例えば、ある時刻 \(x\) においてプリンターの処理可能件数が次のようになっているとします。

プリンター	最大ページ数 \(W_i\)	処理可能件数
A	10	1
B	8	2
C	4	1

依頼のページ数が

\(9, 8, 5, 4\)

なら、

• A に \(9\)
• B に \(8, 5\)
• C に \(4\)

と割り当てられます。

一方で、最大ページ数が小さいプリンターから先に考えてしまうと、大きい依頼が後で割り当てられなくなる可能性があります。
そのため、「大きい依頼を、大きい \(W_i\) のプリンターから順に処理する」ことが重要です。

素朴な方法では難しい理由

各依頼ごとに使えるプリンターを探したり、実際のスケジュールをシミュレーションしたりすると、\(N+M \leq 2 \times 10^5\) なので間に合いません。

また、全ての割り当て方を試すのは組合せ爆発を起こします。

そこで、

1. 答えを二分探索する
2. 固定した時刻 \(x\) で、貪欲に割り当て可能か判定する

という方針にします。

アルゴリズム

まず、どのプリンターでも処理できない依頼がある場合は不可能です。

具体的には、

\( \max P_j > \max W_i \)

なら、その依頼を処理できるプリンターが存在しないので、答えは \(-1\) です。

そうでない場合は、答えを二分探索します。

判定関数 ok(x)

時刻 \(x\) までに全依頼を処理できるかを判定します。

1. 依頼をページ数の大きい順にソートしておく
2. プリンターを \(W_i\) の大きい順にソートしておく
3. まだ割り当てていない最大ページ数の依頼を指す添字 idx を用意する
4. 各プリンターについて、
   • そのプリンターが時刻 \(x\) までに処理できる件数は \(x // T_i\)
   • もし現在の最大の未処理依頼がそのプリンターで処理できないなら、以降のプリンターでも処理できないので不可能
   • 処理できるなら、そのプリンターに可能なだけ依頼を割り当てる
5. 全依頼を割り当てられたら可能

コード中では次の部分が判定です。

def ok(x):
    idx = 0
    for w, t in ps:
        if idx >= m:
            return True
        cap = x // t
        if cap:
            if js[idx] > w:
                return False
            idx += cap
            if idx >= m:
                return True
    return False

ここで、js は依頼をページ数の大きい順に並べた配列です。
ps はプリンターを \(W_i\) の大きい順に並べた配列です。

js[idx] > w の場合、現在残っている最大の依頼をこのプリンターでは処理できません。
さらに、これ以降のプリンターは \(W_i\) が同じか小さいため、この依頼を処理できるプリンターはもう存在しません。
したがって、不可能と判定できます。

二分探索

答えの上限として、最大ページ数の依頼を処理できるプリンターのうち、最も速いものに全依頼を処理させる場合を考えます。

hi = min(t for w, t in printers if w >= max_p) * M

この値は必ず実現可能な時刻です。

あとは、

• ok(mid) が真なら、もっと短い時間でできるかもしれないので hi = mid
• 偽なら、時間が足りないので lo = mid

として二分探索します。

最終的に hi が答えになります。

計算量

• 時間計算量: \(O(N \log N + M \log M + N \log (M \max T_i))\)
• 空間計算量: \(O(N + M)\)

二分探索の回数は高々約 \(50\) 回程度です。
各判定はプリンターを一度なめるだけなので \(O(N)\) です。

実装のポイント

• 依頼は jobs.sort(reverse=True) でページ数の大きい順にします。

• プリンターも printers.sort(reverse=True) で \(W_i\) の大きい順にします。

• 答えは最大で \(10^9 \times 2 \times 10^5 = 2 \times 10^{14}\) 程度になるため、64 bit 整数が必要です。

  • Python では整数の桁あふれを気にする必要はありません。

• 判定関数では、依頼を1件ずつ割り当てるのではなく、idx += cap によってまとめて進めることで高速に処理しています。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    N = next(it)
    M = next(it)

    printers = []
    max_w = 0
    for _ in range(N):
        w = next(it)
        t = next(it)
        printers.append((w, t))
        if w > max_w:
            max_w = w

    jobs = [next(it) for _ in range(M)]
    max_p = max(jobs)

    if max_p > max_w:
        print(-1)
        return

    jobs.sort(reverse=True)
    printers.sort(reverse=True)

    hi = min(t for w, t in printers if w >= max_p) * M
    lo = 0

    js = jobs
    ps = printers
    m = M

    def ok(x):
        idx = 0
        for w, t in ps:
            if idx >= m:
                return True
            cap = x // t
            if cap:
                if js[idx] > w:
                    return False
                idx += cap
                if idx >= m:
                    return True
        return False

    while lo + 1 < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid
        else:
            lo = mid

    print(hi)

if __name__ == "__main__":
    main()

---

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