概要

この問題は、与えられた \(N\) 台のプリンターを用いて、ページ数の制約を満たしつつ \(M\) 件の印刷依頼をすべて完了させるための「最小の時間」を求める問題です。

「すべての依頼を完了する最小の時刻（最大値の最小化）」を求めるため、答えに対する二分探索と貪欲法を組み合わせて解くことができます。

考察

1. 判定問題への変換（二分探索の導入）

「すべての依頼を完了する最小の時間 \(X\) はいくつか？」という問題を直接解くのは難しいですが、時間を固定して、 「時間 \(X\) 以内にすべての依頼を完了させられるか？」 という判定問題（check(X)）に言い換えると、比較的容易に解くことができます。

この判定問題は、時間 \(X\) が大きくなればなるほど「可能」になりやすく、小さくなれば「不可能」になるという単調性を持っています。したがって、二分探索を用いて条件を満たす最小の \(X\) を探すことができます。

2. 判定問題 check(X) をどう解くか（貪欲法）

時間 \(X\) が固定されたとき、各プリンター \(i\) が時間 \(X\) 内に処理できる依頼の最大件数は \(\lfloor X / T_i \rfloor\) 件になります。

依頼には「ページ数 \(P_j\) 以上の最大ページ数 \(W_i\) を持つプリンターでなければ処理できない」という制約があります。 ページ数が大きい依頼ほど、使用できるプリンターの選択肢が少なくなります。そのため、ページ数の大きい依頼から優先的に処理を割り当てる貪欲法が最適になります。

具体的には、以下のように処理を行います： 1. プリンターを最大ページ数 \(W_i\) の降順、依頼をページ数 \(P_j\) の降順にソートします。 2. 依頼を大きい順に見ていきます。現在注目している依頼 \(P_j\) に対し、それを処理できる（\(W_i \geq P_j\) を満たす）プリンターをすべて「利用可能」な状態にします。 3. 利用可能なプリンターの「時間 \(X\) 内での合計処理可能件数」を管理します。 4. 依頼 \(P_j\) を処理するために、合計処理可能件数を \(1\) 減らします。もし処理可能件数が \(0\) になってしまった場合、その依頼を処理できないため、時間 \(X\) では不可能と判定します。

依頼を大きい順に処理しているため、今利用可能になったプリンターは、以降のより小さい依頼（\(P_{j'} \leq P_j\)）もすべて処理できます。したがって、利用可能な枠を現在の依頼に即座に割り当ててしまって問題ありません。

3. 不可能な場合の判定

最もページ数の大きい依頼 \(P_0\) が、最も最大ページ数の大きいプリンター \(W_0\) の容量を超えている場合（\(W_0 < P_0\) のとき）、どのように時間をかけても処理することは不可能です。この場合は即座に -1 を出力します。それ以外の場合は、時間を十分大きく取れば必ずすべての依頼を処理できます。

---

アルゴリズム

1. 初期判定:

   • プリンターを \(W_i\) の降順、依頼を \(P_j\) の降順にソートします。
   • もし \(W_0 < P_0\) であれば、処理不可能として -1 を出力して終了します。

2. 二分探索の範囲設定:

   • 最小時間 low = 1
   • 最大時間 high = 2 * 10^14 （最悪の場合、1台のプリンターですべての依頼を処理するため、\(M \times \max(T_i) = 2 \times 10^5 \times 10^9 = 2 \times 10^{14}\)）

3. 二分探索の実行:

   • mid = (low + high) / 2 とし、check(mid) を行います。
   • check(mid) が true なら、より短い時間で可能か探るため high = mid - 1 とし、答えの候補を更新します。
   • check(mid) が false なら、時間が足りないため low = mid + 1 とします。

---

計算量

• 時間計算量: \(O(N \log N + M \log M + (N + M) \log(\text{high}))\)

  • ソートに \(O(N \log N + M \log M)\) かかります。
  • 二分探索の判定回数は \(\log_2(2 \times 10^{14}) \approx 48\) 回です。
  • 各 check 関数内では、プリンターを指すポインタが全体で高々 \(N\) 回しか進まない（尺取り法の要領）ため、1回の判定は \(O(N + M)\) で動作します。
  • 全体として実行時間制限に十分間に合います。

• 空間計算量: \(O(N + M)\)

  • プリンターと依頼の情報を格納する配列のメモリのみを使用します。

---

実装のポイント

• オーバーフローの防止: check 関数内で各プリンターの処理可能数（\(X / T_i\)）を足し合わせる際、合計値が非常に大きくなり、long long 型であってもオーバーフローする可能性があります。 必要な合計処理可能数は最大でも依頼数 \(M\) 件分なので、合計値を加算する際に min(total_capacity + cap, (long long)M) のように上限を \(M\) でクリップ（制限）することで、オーバーフローを安全に防ぐことができます。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Printer {
    long long W, T;
    bool operator<(const Printer& other) const {
        return W > other.W; // Sort in descending order of W
    }
};

int main() {
    // Optimize standard I/O operations for performance
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<Printer> printers(N);
    for (int i = 0; i < N; ++i) {
        cin >> printers[i].W >> printers[i].T;
    }

    vector<long long> P(M);
    for (int j = 0; j < M; ++j) {
        cin >> P[j];
    }

    // Sort printers and requests in descending order
    sort(printers.begin(), printers.end());
    sort(P.begin(), P.end(), greater<long long>());

    // If the largest request cannot be handled by the best printer, it's impossible.
    if (printers[0].W < P[0]) {
        cout << -1 << "\n";
        return 0;
    }

    // Decision function to check if all requests can be completed within time X
    auto check = [&](long long X) -> bool {
        long long total_capacity = 0;
        int idx = 0;
        for (int j = 0; j < M; ++j) {
            // Add capacities of all printers that can handle the current request size
            while (idx < N && printers[idx].W >= P[j]) {
                long long cap = X / printers[idx].T;
                total_capacity = min(total_capacity + cap, (long long)M); // Prevent overflow
                idx++;
            }
            if (total_capacity == 0) {
                return false;
            }
            total_capacity--;
        }
        return true;
    };

    // Binary search for the minimum time
    long long low = 1;
    long long high = 2e14; // Max possible answer: M * max(T) = 2e5 * 1e9 = 2e14
    long long ans = high;

    while (low <= high) {
        long long mid = low + (high - low) / 2;
        if (check(mid)) {
            ans = mid;
            high = mid - 1; // Try to find a smaller valid time
        } else {
            low = mid + 1;  // Increase the time limit
        }
    }

    cout << ans << "\n";

    return 0;
}

---

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