Official

D - パソコンの販売 / Selling Computers Editorial by admin Editorial for printing

Gemini 3.8 Flash (High)

概要

\(N\) 台のパソコンから \(M\) 人の客に条件を満たすように 1 台ずつ割り当て、売上金額の合計を最大化する問題です。

客を要求性能の昇順にソートすることで、本問題は「締め切り付きジョブスケジューリング問題」に帰着できます。パソコンを価格が高い順に見る貪欲法と、空きスロットを高速に探すための Union-Find を組み合わせることで、\(O(N \log N + M \log M)\) で解くことができます。

考察

1. 条件の整理と自明なケース

客 \(j\) にパソコン \(i\) を販売できる条件は \(A_i \ge C_j\) です。また、1 人の客に 1 台ずつ相異なるパソコンを割り当てるため、パソコンの台数が客の人数より少ない場合(\(N < M\))は、全員に販売することは絶対に不可能です(この場合は即座に -1 を出力します)。

2. 客のソートと「満たせる客の範囲」

客の要求性能 \(C\) を昇順にソートしてみましょう。 $\(C_1 \le C_2 \le \dots \le C_M\)$

このように並べると、あるパソコンの性能が \(A_i\) であるとき、このパソコンを購入できる客は「\(C_j \le A_i\) を満たす客」となります。\(C\) は昇順に並んでいるため、\(A_i \ge C_j\) を満たす最大の客のインデックスを \(r_i\) とすると、このパソコンは 客 \(1, 2, \dots, r_i\) の誰にでも販売可能 であり、客 \(r_i + 1\) 以降には販売できないことが分かります。 この値 \(r_i\) は、ソート済みの配列 \(C\) に対して二分探索(upper_bound)を用いることで、\(O(\log M)\) で高速に求められます。

3. ジョブスケジューリング問題への帰着

この問題は、以下のような「締め切り付きジョブスケジューリング問題」と言い換えることができます: - 客 \(1, 2, \dots, M\) を「時刻 \(1, 2, \dots, M\) のスロット」とみなす。 - パソコン \(i\) を「締め切り \(r_i\)、利益 \(B_i\) の仕事」とみなす。 - 各スロットには高々 1 つの仕事しか割り当てられない。 - 利益の総和を最大化し、\(M\) 個すべてのスロットを埋めることができるか判定する。

4. 貪欲法のアプローチ

利益(売上)を最大化するためには、価格 \(B_i\) が高いパソコンから優先して採用する のが直感的にも正しく、マトロイドの理論からも最適であることが保証されています。

では、採用するパソコン \(i\)(満たせる客の範囲が \(1 \dots r_i\))は、どの客に割り当てるべきでしょうか? 結論として、\(r_i\) 以下の空いている客の中で、最も番号が大きい客(最も後ろの空きスロット) に割り当てるのが最善です。 なぜなら、番号の小さい客(要求性能が低い客)のスロットを空けておいた方が、後から見る「性能が低くて \(r\) が小さいパソコン」を割り当てられる可能性が高くなるからです。

5. 高速化(Union-Findの利用)

各パソコンについて「\(r_i\) 以下の最大の空き番号」を線形探索すると、最悪で \(O(NM)\) の時間がかかり TLE(実行時間制限超過)してしまいます。

そこで、Union-Find(素集合データ構造) を用いて空き番号を管理します。 - スロット \(0\) から \(M\) を管理する Union-Find を用意し、初期状態では要素 \(x\) の代表元を \(x\) 自身としておきます(\(x\) が空いていることを表す)。 - スロット \(k\) を使用したら、\(k\) の代表元を \(k - 1\) のグループにマージ(統合)します。 - これにより、find(r) を呼び出すだけで、\(r\) 以下で現在空いている最大の番号がならし \(O(\alpha(M))\) というほぼ定数時間で取得できます(\(0\) が返ってきた場合は、割り当て可能な空きスロットが存在しないことを意味します)。

アルゴリズム

  1. \(N < M\) ならば -1 を出力して終了する。
  2. 客の要求性能の配列 \(C\) を昇順にソートする。
  3. 各パソコン \(i\) について、二分探索(std::upper_bound)を用いて \(A_i \ge C_j\) を満たす客の個数 \(r_i\) を求める。
  4. パソコンのリストを、価格 \(B_i\) の降順にソートする。
  5. Union-Find を初期化し(サイズ \(M + 1\))、価格が高いパソコンから順に以下を行う:
    • \(r_i\) 以下の最大の空きスロット \(s = \text{find}(r_i)\) を取得する。
    • \(s > 0\) であれば、その客に販売する:
      • 売上合計に \(B_i\) を加算する。
      • 販売台数カウントを \(1\) 増やす。
      • スロット \(s\) を \(s - 1\) に統合する(parent[s] = find(s - 1))。
    • \(s = 0\) であれば、このパソコンを販売できる空き客がいないためスキップする。
  6. 最終的に販売できたパソコンの台数がちょうど \(M\) 台であれば売上合計を出力し、そうでなければ全員に販売できなかったため -1 を出力する。

計算量

  • 時間計算量: \(O(N \log N + M \log M)\)
    • 客の配列 \(C\) のソート: \(O(M \log M)\)
    • 各パソコンの \(r_i\) の二分探索: \(O(N \log M)\)
    • パソコンのソート: \(O(N \log N)\)
    • 貪欲な割り当て処理: \(N\) 回の Union-Find 操作で \(O(N \alpha(M))\)
    • 全体として \(O(N \log N + M \log M)\) となり、制約 \(N, M \le 10^5\) に対して十分高速に動作します。
  • 空間計算量: \(O(N + M)\)
    • パソコンの情報、客の要求性能配列、Union-Find の配列の保持に \(O(N + M)\) のメモリを使用します。

実装のポイント

  • スロット \(0\) の番兵としての利用:

    • 客のインデックスを 1-indexed(\(1 \dots M\))として扱い、\(0\) 番を「割り当て不能」を表す番兵とします。find(r) が \(0\) を返した場合は、利用可能なスロットが存在しないとシンプルに判定できます。
  • オーバーフローの防止:

    • 売上金額の合計は最大で \(M \times \max(B_i) = 10^5 \times 10^9 = 10^{14}\) となり、32-bit 整数の上限(約 \(2 \times 10^9\))を超えてしまいます。合計金額を保持する変数は必ず 64-bit 整数型(C++ の long long)を使用してください。

      ソースコード

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

using namespace std;

struct Laptop {
    long long a;
    long long b;
};

struct Item {
    int r;
    long long b;
};

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

    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<Laptop> laptops(n);
    for (int i = 0; i < n; ++i) {
        cin >> laptops[i].a >> laptops[i].b;
    }

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

    if (n < m) {
        cout << -1 << "\n";
        return 0;
    }

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

    vector<Item> items(n);
    for (int i = 0; i < n; ++i) {
        auto it = upper_bound(c.begin(), c.end(), laptops[i].a);
        items[i].r = distance(c.begin(), it);
        items[i].b = laptops[i].b;
    }

    sort(items.begin(), items.end(), [](const Item& x, const Item& y) {
        return x.b > y.b;
    });

    vector<int> parent(m + 1);
    iota(parent.begin(), parent.end(), 0);

    auto find = [&](auto self, int x) -> int {
        return parent[x] == x ? x : parent[x] = self(self, parent[x]);
    };

    int count = 0;
    long long total_revenue = 0;

    for (const auto& item : items) {
        if (item.r == 0) continue;
        int slot = find(find, item.r);
        if (slot > 0) {
            total_revenue += item.b;
            count++;
            parent[slot] = find(find, slot - 1);
        }
    }

    if (count == m) {
        cout << total_revenue << "\n";
    } else {
        cout << -1 << "\n";
    }

    return 0;
}

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

posted:
last update: