D - パソコンの販売 / Selling Computers 解説 by admin
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\) が返ってきた場合は、割り当て可能な空きスロットが存在しないことを意味します)。
アルゴリズム
- \(N < M\) ならば
-1を出力して終了する。 - 客の要求性能の配列 \(C\) を昇順にソートする。
- 各パソコン \(i\) について、二分探索(
std::upper_bound)を用いて \(A_i \ge C_j\) を満たす客の個数 \(r_i\) を求める。 - パソコンのリストを、価格 \(B_i\) の降順にソートする。
- 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\) であれば、このパソコンを販売できる空き客がいないためスキップする。
- 最終的に販売できたパソコンの台数がちょうど \(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\) を返した場合は、利用可能なスロットが存在しないとシンプルに判定できます。
- 客のインデックスを 1-indexed(\(1 \dots M\))として扱い、\(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 によって生成されました。