概要

この問題は、サイズ制限のある印刷機を使って、指定された枚数のポスターを印刷するのに必要な最小日数を求める問題です。

「最小日数を求める」という最適化問題は、「\(D\) 日以内ですべての注文を完了できるか？」という判定問題に言い換えることで、二分探索と貪欲法を用いて効率的に解くことができます。

---

考察

1. 判定問題への言い換え（二分探索）

「\(D\) 日ですべての注文を完了できるか？」という判定問題を \(f(D)\) とします。 もし \(D\) 日で完了できるなら、それより多い \(D+1\) 日でも当然完了できます。逆に \(D\) 日で完了できないなら、それより少ない \(D-1\) 日でも完了できません。

このように、判定結果 \(f(D)\) は \(D\) に関して単調性（False, False, ..., True, True のように境界を境に結果が切り替わる性質）を持つため、二分探索（Binary Search）を適用して最小の \(D\) を求めることができます。

\(D\) 日間使えると仮定すると、各印刷機は最大で \(D\) 枚のポスターを印刷できることになります。

2. \(D\) 日で印刷可能かどうかの判定（貪欲法）

注文を横幅 \(W_i\) が小さい順に処理していくことを考えます。 サイズ \(W_i\) の注文を処理する際、使用可能な印刷機は \(L_j \leq W_i \leq R_j\) を満たすものです。

\(W_i\) を昇順に見ていくとき、現時点で「横幅の下限を満たしている（\(L_j \leq W_i\)）」印刷機のうち、どの印刷機を優先して使うべきでしょうか？

結論から言うと、対応できる右端（上限 \(R_j\)）が最も小さい印刷機から優先的に使用するのが最適です。 なぜなら、右端 \(R_j\) が大きい印刷機は、今後登場するかもしれない「より横幅 \(W\) が大きい注文」のために温存しておく方が、全体のスケジュールが破綻しにくくなるからです。これは区間スケジューリング問題などでもよく使われる典型的な貪欲法の考え方です。

---

アルゴリズム

具体的には、以下の手順で解を求めます。

事前準備

1. 注文のマージとソート: 同じ横幅 \(W_i\) の注文は、必要な枚数 \(C_i\) を合算して1つの注文にまとめておきます。その後、注文を横幅 \(W_i\) の昇順にソートします。
2. 印刷機のソート: 印刷機を対応下限 \(L_j\) の昇順にソートします。

二分探索の実行

探索範囲を low = 1, high = (すべてのポスターの枚数の総和) とし、判定関数 check(D) が真となる最小の \(D\) を二分探索します。

判定関数 check(D) の処理

現在使用可能な印刷機を管理するために、優先度付きキュー（最小ヒープ、priority_queue）を使用します。キューには、印刷機の「対応上限 \(R_j\)」と「残り印刷可能枚数（初期値 \(D\)）」のペアを格納し、\(R_j\) が小さい順に取り出せるようにします。

1. 注文 \(i\) を横幅 \(W_i\) が小さい順に見ていきます。
2. まだキューに追加していない印刷機のうち、\(L_j \leq W_i\) を満たすものをすべてキューに追加します。
3. 注文 \(i\) の必要枚数 \(C_i\) が \(0\) になるまで、以下の処理を繰り返します：
   • キューが空になった場合、印刷できる機械がないため false を返します。
   • キューから \(R_j\) が最小の印刷機を1つ取り出します。
   • 取り出した印刷機の \(R_j\) が \(W_i\) 未満の場合、その印刷機は今回の注文を印刷できません。さらに、今後の注文はすべて \(W_i\) 以上であるため、この印刷機は今後も一切使えません。したがって、この印刷機は破棄して次の印刷機をキューから取り出します。
   • \(R_j \geq W_i\) の場合、印刷可能です。
     • この印刷機で印刷する枚数 \(take = \min(\text{必要枚数}, \text{印刷機の残り可能枚数})\) を決定します。
     • 注文の必要枚数を \(take\) 減らし、印刷機の残り可能枚数も \(take\) 減らします。
     • 印刷機にまだ残り可能枚数がある場合は、再びキューに戻します。
4. すべての注文を処理しきれたら true を返します。

---

計算量

時間計算量

• 事前準備: 注文のソートに \(O(N \log N)\)、印刷機のソートに \(O(M \log M)\) 時間かかります。
• 二分探索の判定: 二分探索のステップ数は \(O(\log(\sum C_i))\) 回です。 1回の check(D) において、各印刷機はキューに高々1回追加され、高々1回（または注文をちょうど満たしたときの分割分を含めてわずかな回数）取り出されます。したがって、1回の判定にかかる時間は \(O((N + M) \log M)\) です。

全体の時間計算量は、 $\(O((N + M) \log M \log(\sum C_i) + N \log N)\)\( となります。制約 \)N + M \leq 10^5\(、\)\sum C_i \leq 10^9$ のもとで、実行時間制限（通常 2.0 秒）に十分間に合います。

空間計算量

• 空間計算量: \(O(N + M)\) 注文と印刷機の情報を格納する配列、および優先度付きキューのメモリとして、入力のサイズに比例する領域が必要です。

---

実装のポイント

• 同じ横幅の注文のマージ: 同じ横幅の注文が複数ある場合、あらかじめ \(C_i\) を合算しておくことで、check 関数内での無駄なループや条件分岐を減らし、実装をシンプルかつ高速に保つことができます。

• 印刷機の破棄条件: R < W となった印刷機は、以降の注文（横幅は \(W\) 以上）でも絶対に印刷に使えません。そのため、キューに戻さずにそのまま破棄（continue）してしまって問題ありません。

• オーバーフローへの注意: ポスターの枚数の総和 \(\sum C_i\) や日数 \(D\) は最大で \(10^9\) 程度になり、掛け算や足し算の過程で 32bit 整数型（int）の上限を超える可能性があるため、C++ では long long 型を使用しています。

  ソースコード

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

using namespace std;

struct Order {
    long long W;
    long long C;
    bool operator<(const Order& other) const {
        return W < other.W;
    }
};

struct Machine {
    long long L, R;
    bool operator<(const Machine& other) const {
        if (L != other.L) return L < other.L;
        return R < other.R;
    }
};

bool check(long long D, const vector<Order>& orders, const vector<Machine>& machines) {
    using P = pair<long long, long long>; // {R, remaining_capacity}
    priority_queue<P, vector<P>, greater<P>> pq;

    int m_idx = 0;
    int M = machines.size();

    for (const auto& order : orders) {
        long long W = order.W;
        long long req = order.C;

        while (m_idx < M && machines[m_idx].L <= W) {
            pq.push({machines[m_idx].R, D});
            m_idx++;
        }

        while (req > 0) {
            if (pq.empty()) {
                return false;
            }
            auto [R, rem] = pq.top();
            pq.pop();

            if (R < W) {
                continue;
            }

            long long take = min(req, rem);
            req -= take;
            rem -= take;

            if (rem > 0) {
                pq.push({R, rem});
            }
        }
    }
    return true;
}

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

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

    vector<Order> raw_orders(N);
    for (int i = 0; i < N; ++i) {
        long long h;
        cin >> raw_orders[i].W >> h >> raw_orders[i].C;
    }

    vector<Machine> machines(M);
    for (int j = 0; j < M; ++j) {
        cin >> machines[j].L >> machines[j].R;
    }

    sort(raw_orders.begin(), raw_orders.end());
    vector<Order> orders;
    for (const auto& order : raw_orders) {
        if (!orders.empty() && orders.back().W == order.W) {
            orders.back().C += order.C;
        } else {
            orders.push_back(order);
        }
    }

    sort(machines.begin(), machines.end());

    long long low = 1;
    long long high = 0;
    for (const auto& order : orders) {
        high += order.C;
    }

    if (!check(high, orders, machines)) {
        cout << -1 << "\n";
        return 0;
    }

    long long ans = high;
    while (low <= high) {
        long long mid = low + (high - low) / 2;
        if (check(mid, orders, machines)) {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    cout << ans << "\n";

    return 0;
}

---

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