概要

各プリンターは「処理できるページ数の上限」と「1件あたりの処理時間」を持ちます。
すべての依頼を処理し終える最小時刻を、二分探索と貪欲な判定で求めます。

考察

時刻 \(x\) までに、プリンター \(i\) が処理できる依頼数は

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

件です。

つまり、時刻 \(x\) までにすべての依頼を処理できるかどうかは、

• プリンター \(i\) は最大 \(W_i\) ページまでの依頼を処理できる
• そのような処理枠を \(\left\lfloor \frac{x}{T_i} \right\rfloor\) 個持っている

と考えることができます。

例えば、プリンターの能力が

プリンター	\(W_i\)	\(T_i\)
1	10	3
2	5	2

で、\(x = 6\) のとき、

• プリンター 1 は \(\lfloor 6/3 \rfloor = 2\) 件処理可能
• プリンター 2 は \(\lfloor 6/2 \rfloor = 3\) 件処理可能

です。

したがって、

• 最大 10 ページまで処理できる枠が 2 個
• 最大 5 ページまで処理できる枠が 3 個

ある、とみなせます。

---

ここで依頼をページ数の大きい順に並べます。

ページ数が大きい依頼ほど、処理できるプリンターが限られるため、先に考えるべきです。

例えば、依頼が

\(9, 7, 4\)

だったとします。

最初の 2 件、つまり \(9, 7\) ページの依頼は、少なくとも \(7\) ページ以上を処理できるプリンターの枠で処理する必要があります。

一般に、依頼を降順に並べて

\(P_1 \geq P_2 \geq \cdots \geq P_M\)

としたとき、先頭 \(k\) 件の依頼はすべて \(P_k\) ページ以上の依頼です。

したがって、時刻 \(x\) までに処理可能であるためには、

「\(W_i \geq P_k\) を満たすプリンターたちの処理可能件数の合計」が \(k\) 以上

である必要があります。

この条件をすべての \(k\) について満たせば、処理可能です。

---

素朴に各依頼をどのプリンターに割り当てるかを全探索すると、組み合わせが膨大で到底間に合いません。

また、各時刻について実際にスケジューリングをシミュレーションするのも複雑です。

そこで、

• 答えの時刻を二分探索する
• その時刻で処理可能かを高速に判定する

という方針を取ります。

時刻 \(x\) で処理可能なら、それより大きい時刻でも必ず処理可能です。
この単調性があるため、二分探索が使えます。

アルゴリズム

まず、すべての依頼をページ数の降順にソートします。

また、プリンターも \(W_i\) の降順にソートします。

判定関数 feasible(x) では、時刻 \(x\) までにすべての依頼を処理できるかを調べます。

手順は以下の通りです。

1. 依頼をページ数の大きい順に見る
2. 現在見ている依頼のページ数を \(p\) とする
3. \(W_i \geq p\) を満たすプリンターを追加する
4. 追加したプリンターについて、時刻 \(x\) までに処理可能な件数 \(\left\lfloor x / T_i \right\rfloor\) を合計する
5. ここまで見た依頼数より、処理可能件数の合計が少なければ不可能

コード中では、処理可能件数の合計を cap としています。

while (idx < N && printers[idx].first >= p) {
    ll add = x / printers[idx].second;
    if (add > M) add = M;
    cap = min<ll>(M, cap + add);
    idx++;
}

プリンターは \(W_i\) の降順に並んでいるので、各プリンターは高々 1 回だけ追加されます。

そのため、1 回の判定は \(O(N + M)\) で行えます。

---

あとは答えを二分探索します。

まず、どのプリンターでも処理できない依頼がある場合、つまり

\( \max P_j > \max W_i \)

なら答えは \(-1\) です。

そうでない場合、最大ページ数の依頼を処理できるプリンターのうち、最も速いものを使えば、全依頼を処理できます。

その処理時間を minT とすると、答えは高々

\(minT \times M\)

です。

これを二分探索の上限にします。

ll ng = 0;
ll ok = minT * M;

• ng: 処理不可能な時刻
• ok: 処理可能な時刻

として二分探索します。

while (ok - ng > 1) {
    ll mid = (ng + ok) / 2;
    if (feasible(mid)) ok = mid;
    else ng = mid;
}

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

計算量

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

実装のポイント

プリンターごとの処理可能件数

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

をすべて足し合わせると、非常に大きな値になり、オーバーフローする可能性があります。

しかし、必要なのは最大でも依頼数 \(M\) 件までなので、コードでは cap を \(M\) で打ち切っています。

if (add > M) add = M;
cap = min<ll>(M, cap + add);

また、依頼を降順、プリンターも \(W_i\) の降順にソートしておくことで、判定関数内でプリンターを一度ずつ見るだけで済みます。

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<pair<ll, ll>> printers(N);
    ll maxW = 0;
    for (int i = 0; i < N; i++) {
        ll W, T;
        cin >> W >> T;
        printers[i] = {W, T};
        maxW = max(maxW, W);
    }

    vector<ll> jobs(M);
    for (int i = 0; i < M; i++) cin >> jobs[i];

    sort(jobs.rbegin(), jobs.rend());

    if (jobs[0] > maxW) {
        cout << -1 << '\n';
        return 0;
    }

    sort(printers.begin(), printers.end(), [](const auto& a, const auto& b) {
        if (a.first != b.first) return a.first > b.first;
        return a.second < b.second;
    });

    ll minT = (ll)4e18;
    for (auto [W, T] : printers) {
        if (W >= jobs[0]) minT = min(minT, T);
    }

    auto feasible = [&](ll x) -> bool {
        ll cap = 0;
        int idx = 0;

        for (int j = 0; j < M; j++) {
            ll p = jobs[j];

            while (idx < N && printers[idx].first >= p) {
                ll add = x / printers[idx].second;
                if (add > M) add = M;
                cap = min<ll>(M, cap + add);
                idx++;
            }

            if (cap < j + 1) return false;
        }

        return true;
    };

    ll ng = 0;
    ll ok = minT * M;

    while (ok - ng > 1) {
        ll mid = (ng + ok) / 2;
        if (feasible(mid)) ok = mid;
        else ng = mid;
    }

    cout << ok << '\n';
    return 0;
}

---

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