概要

\(N\) 台のプリンターで \(M\) 件の印刷依頼をすべて処理し終える最早時刻（メイクスパン）を求める問題です。答えに対する二分探索と貪欲法による判定を組み合わせて解きます。

考察

重要な気づき

1. 「時刻 \(t\) までにすべての依頼を処理できるか？」は単調性を持つ
   時刻 \(t\) で処理可能なら、\(t' > t\) でも当然処理可能です。この単調性から、答えに対して二分探索ができます。

2. 時刻 \(t\) が与えられたとき、各プリンターの処理可能件数が決まる
   プリンター \(i\) は時刻 \(t\) までに \(\lfloor t / T_i \rfloor\) 件の依頼を処理できます。

3. 大きなページ数の依頼ほど、使えるプリンターが限られる
   ページ数が大きい依頼から順に考えると、使えるプリンターが少ない依頼から先に割り当てを確認する貪欲法が有効です。

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

依頼をプリンターに具体的に割り当てようとすると、組合せ爆発が起き TLE になります。二分探索で「判定問題」に落とし、判定を効率よく行うのがポイントです。

判定の正当性（Hall の定理の考え方）

依頼とプリンターを容量の大きい順にソートします。ページ数が大きい上位 \(k\) 件の依頼は、容量がそれ以上のプリンターでしか処理できません。よって、任意の \(k\) について「上位 \(k\) 件を処理可能なプリンター群の合計処理可能件数 \(\geq k\)」 が成り立てば、全体の割り当てが可能です（Hall の結婚定理に対応）。

アルゴリズム

1. プリンターを \(W_i\) の降順にソート、依頼を \(P_j\) の降順にソートする。
2. 最大の依頼 \(P_1\) がどのプリンターでも処理できない場合、\(-1\) を出力。
3. 答えに対して二分探索する。判定関数 check(t) は以下の通り：
   • ポインタ ptr とプリンター群の合計処理可能件数 sum を管理。
   • 依頼を大きい順に見ていく。\(k\) 番目の依頼について：
     • printers[ptr].first >= jobs[k] であるプリンターを順に取り込み、\(\lfloor t / T_{\text{ptr}} \rfloor\) を sum に加算。
     • sum < k + 1 なら false（上位 \(k+1\) 件を処理しきれない）。
   • すべての依頼を確認できたら true。
4. 二分探索の結果を出力する。

具体例

プリンター: \((W=10, T=2), (W=5, T=1)\)、依頼: \(P=8, P=4, P=3\)

\(t=4\) の場合： - プリンター1は \(\lfloor 4/2 \rfloor = 2\) 件処理可能 - プリンター2は \(\lfloor 4/1 \rfloor = 4\) 件処理可能 - 依頼を大きい順に: \(8, 4, 3\) - \(k=0\): \(P=8\) → プリンター1のみ対応可 → \(sum=2 \geq 1\) ✓ - \(k=1\): \(P=4\) → プリンター2も加わる → \(sum=2+4=6 \geq 2\) ✓ - \(k=2\): \(P=3\) → \(sum=6 \geq 3\) ✓ - 判定: 可能

計算量

• 時間計算量: \(O((N + M) \log(M \times \max(T_i)))\)
  • 二分探索が \(O(\log(M \times 10^9)) \approx O(60)\) 回
  • 各判定に \(O(N + M)\)
• 空間計算量: \(O(N + M)\)

実装のポイント

• 二分探索の上界: 最悪ケースは全依頼を1台のプリンターで処理する場合で、\(M \times 10^9\) が上界。

• オーバーフロー対策: sum が \(M\) を超えたら \(M\) で打ち切る。\(\lfloor t / T_i \rfloor\) の値が非常に大きくなる可能性があるため、long long を使い適切にクランプする。

• ポインタの再利用: 依頼もプリンターもソート済みなので、ポインタを一方向に動かすだけで \(O(N + M)\) の判定が実現できる。

  ソースコード

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, M;
    cin >> N >> M;
    
    vector<pair<long long, long long>> printers(N);
    for (int i = 0; i < N; i++) {
        cin >> printers[i].first >> printers[i].second;
    }
    
    vector<long long> jobs(M);
    for (int j = 0; j < M; j++) {
        cin >> jobs[j];
    }
    
    sort(printers.begin(), printers.end(), [](const auto& a, const auto& b) {
        return a.first > b.first;
    });
    
    sort(jobs.begin(), jobs.end(), greater<long long>());
    
    if (jobs[0] > printers[0].first) {
        cout << -1 << endl;
        return 0;
    }
    
    auto check = [&](long long t) -> bool {
        long long sum = 0;
        int ptr = 0;
        for (int k = 0; k < M; k++) {
            while (ptr < N && printers[ptr].first >= jobs[k]) {
                sum += t / printers[ptr].second;
                if (sum >= (long long)M) sum = (long long)M;
                ptr++;
            }
            if (sum < (long long)(k + 1)) return false;
        }
        return true;
    };
    
    long long lo = 0, hi = (long long)M * 1000000000LL;
    while (lo < hi) {
        long long mid = (lo + hi) / 2;
        if (check(mid)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    
    cout << lo << endl;
    return 0;
}

---

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