概要

すべての依頼を完了できる最小の時刻を求める問題です。この問題は、答えとなる時刻 \(X\) について二分探索を行い、「時刻 \(X\) 以内にすべての依頼を処理できるか？」という判定問題を、ソートと累積和を用いて高速に解くことで効率的に解決できます。

考察

1. 判定問題への帰着（二分探索）

「すべての依頼を完了できる最小の時刻を求める」という最適化問題は、直接解くのが困難です。しかし、時刻 \(X\) を固定したときに「時刻 \(X\) 以内にすべての依頼を処理できるか？」という判定問題（真偽値）に置き換えると、以下のような単調性が成り立ちます。 - 時刻 \(X\) が十分に大きければ、すべての依頼を処理できる（True）。 - 時刻 \(X\) が小さすぎると、処理しきれない（False）。

したがって、この判定問題を解く関数 check(X) を作成し、二分探索を用いることで、最小の時刻 \(X\) を効率的に見つけることができます。

2. 時刻 \(X\) における処理能力

時刻 \(X\) が与えられたとき、プリンター \(i\) が処理できる依頼の最大件数は、端数を切り捨てて \(\lfloor X / T_i \rfloor\) 件となります。

3. 割り当て可能かの判定（ソートと累積和）

依頼をどのプリンターに割り当てられるかには「容量 \(W_i \ge\) ページ数 \(P_j\)」という制約があります。 これを整理するために、プリンターを容量の降順、依頼をページ数の降順にソートします。

ソートした状態で、大きい依頼から順に \(0, 1, \dots, j\) 番目（計 \(j+1\) 個）の依頼に注目します。 - ページ数の降順に並んでいるため、これら \(j+1\) 個の依頼はすべて \(P_j\) 以上のページ数を持っています。 - これらを処理できるのは、容量が \(P_j\) 以上のプリンターに限られます。 - プリンターも容量の降順にソートされているため、処理可能なプリンターは先頭から特定のインデックス \(k\) までのプリンター群（プリンター \(0 \dots k-1\)）になります。

このとき、これらの依頼をすべて処理するためには、「処理可能なプリンター群の処理能力の合計が、依頼の個数 \(j+1\) 以上であること」 がすべての \(j\) について成り立つ必要があります。

具体的には、プリンターの処理能力の累積和を \(S\) とすると、各 \(j\) について以下が成り立てば割り当て可能です。 $\(S[\text{依頼 } j \text{ を処理できるプリンター数}] \ge j + 1\)$

この判定は、累積和を事前に計算しておくことで、各 \(j\) に対して \(O(1)\)、全体で \(O(N + M)\) で高速に行うことができます。

---

アルゴリズム

事前準備

1. 処理可能性の判定: 最大の依頼ページ数 \(\max(P)\) が、最大のプリンター容量 \(\max(W)\) を超えている場合は、どのようにしても処理できないため、即座に -1 を出力します。
2. ソート: プリンターを容量 \(W_i\) の降順、依頼をページ数 \(P_j\) の降順にソートします。
3. 限界インデックスの計算（尺取り法）: 各依頼 \(j\) について、その依頼を処理できる（容量が \(P_j\) 以上である）プリンターが先頭から何台あるか（idx_plus_1[j]）を、尺取り法（Two-pointer）を用いて事前に計算しておきます。
4. 不要なプリンターの除外: 最も小さい依頼すら処理できない（容量が足りない）プリンターは、どのような割り当てでも使われないため、あらかじめ除外（無視）しておきます。

二分探索

• 探索範囲:
  • low = 0
  • high = (最大の依頼を処理できるプリンターのうち、最も処理時間が短いものの時間) × M（1台で全依頼を処理する場合の最悪時間）
• 判定関数 check(X):
  1. 各プリンターの時刻 \(X\) における最大処理件数 \(\lfloor X / T_i \rfloor\) を求め、その累積和 \(S\) を計算します。
  2. 各依頼 \(j\) (\(0 \le j < M\)) について、 \(S[\text{idx\_plus\_1}[j]] < j + 1\) となるものが1つでもあれば False を返します。
  3. すべての \(j\) で条件を満たせば True を返します。

---

計算量

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

  • ソートに \(O(N \log N + M \log M)\) かかります。
  • 尺取り法による事前計算に \(O(N + M)\) かかります。
  • 二分探索のステップ数は \(O(\log(\text{high}))\) 回であり、各ステップの判定関数 check(X) は \(O(N + M)\) で動作します。全体の制約において \(\log(\text{high})\) は高々 \(60\) 程度であるため、実行時間制限に十分間に合います。

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

  • プリンターと依頼の情報を格納する配列、および累積和配列やインデックス配列の保持に必要なメモリ量です。

---

実装のポイント

• 尺取り法の活用: 各依頼に対して処理可能なプリンターの境界を求める際、二分探索（bisect）を何度も呼ぶのではなく、降順ソートされた性質を利用して尺取り法で一方向に走査することで、 \(O(N + M)\) で高速に処理できます。

• 最悪値の見積もり: 二分探索の初期上界 high は、最大の依頼を処理できるプリンターの中で最も速いものがすべての依頼を処理する場合の時間 \(T_{\min} \times M\) とすることで、探索範囲を必要最小限に抑えています。

  ソースコード

import sys


def solve():
    # Fast I/O
    input = sys.stdin.read
    data = input().split()
    if not data:
        return

    N = int(data[0])
    M = int(data[1])

    printers = []
    idx_data = 2
    for _ in range(N):
        w = int(data[idx_data])
        t = int(data[idx_data + 1])
        printers.append((w, t))
        idx_data += 2

    P = []
    for _ in range(M):
        P.append(int(data[idx_data]))
        idx_data += 1

    # Preliminary check: if the largest job is larger than the largest printer capacity
    max_P = max(P)
    max_W = max(w for w, t in printers)
    if max_P > max_W:
        print(-1)
        return

    # Sort printers and jobs in descending order
    printers.sort(key=lambda x: x[0], reverse=True)
    P.sort(reverse=True)

    W = [w for w, t in printers]
    T = [t for w, t in printers]

    # Two-pointer approach to find the number of eligible printers for each job
    idx_plus_1 = [0] * M
    i = -1
    for j in range(M):
        pj = P[j]
        while i + 1 < N and W[i + 1] >= pj:
            i += 1
        idx_plus_1[j] = i + 1

    # Optimization: Only consider printers that can process at least the smallest job
    limit = idx_plus_1[-1]
    T_limit = T[:limit]

    # Find the minimum time T_i among printers capable of processing the largest job
    k = idx_plus_1[0]
    T_min = min(T[:k])

    # Binary search range
    high = T_min * M
    low = 0

    j_plus_1 = list(range(1, M + 1))
    S = [0] * (limit + 1)

    # Feasibility check for a given time X
    def check(X):
        curr = 0
        for i in range(limit):
            curr += X // T_limit[i]
            S[i + 1] = curr

        for j in range(M):
            if S[idx_plus_1[j]] < j_plus_1[j]:
                return False
        return True

    # Binary search for the minimum time
    while high - low > 1:
        mid = (low + high) // 2
        if check(mid):
            high = mid
        else:
            low = mid

    print(high)


if __name__ == "__main__":
    solve()

---

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