D - パソコンの販売 / Selling Computers Editorial by admin Editorial for printing
gpt-6-astra-medium概要
各客に要求性能を満たす相異なるパソコンを割り当て、販売価格の合計を最大化する問題です。
要求性能が高い客から順に、その客に販売できる未販売のパソコンのうち最も高価なものを選ぶ貪欲法で解けます。
考察
要求性能が高い客から処理する
要求性能が低い客から自由にパソコンを割り当てると、要求性能が高い客に必要なパソコンを先に使ってしまう可能性があります。
例えば、パソコンと客が次のような場合を考えます。
- パソコン:性能 \(10\)・価格 \(100\) 円、性能 \(5\)・価格 \(50\) 円
- 客の要求性能:\(5, 10\)
要求性能 \(5\) の客に最も高価な性能 \(10\) のパソコンを販売すると、要求性能 \(10\) の客には販売できなくなります。一方、要求性能 \(10\) の客を先に処理すれば、両方の客に販売できます。
そこで、客を要求性能の降順に処理します。すると、現在の客に販売できるパソコンは、後に処理するどの客にも販売できます。
販売できる中で最も高価なものを選んでよい理由
現在の客に販売できる未販売のパソコンのうち、最も高価なものを \(x\) とします。
これまでの割り当てを固定したうえで、残りの客全員への売上が最大となる割り当てを考えます。その割り当てで現在の客に販売するパソコンを \(y\) とすると、\(B_x \ge B_y\) です。
- \(x\) が誰にも販売されていない場合
現在の客に販売するものを \(y\) から \(x\) に変更しても、条件を満たし、売上は減りません。 - \(x\) が後の客に販売されている場合
現在の客に \(x\)、その後の客に \(y\) を販売するように交換します。後の客の要求性能は現在の客以下なので、\(y\) でも条件を満たします。販売するパソコンの集合は変わらず、売上も変わりません。
したがって、全員に販売できる割り当てが存在するなら、現在の客に最も高価な候補を選んでも、最適な割り当てを実現できます。これを繰り返すことで、最大の売上が得られます。
最も高価な候補を効率よく探す
客ごとにすべてのパソコンを調べると、時間計算量は \(O(NM)\) です。\(N, M \le 10^5\) では間に合いません。
ここで、客の要求性能は処理が進むにつれて下がるため、販売可能なパソコンの範囲は広がっていきます。
この性質を利用し、次のように管理します。
- パソコンも性能の降順に並べる。
- 現在の要求性能を満たすパソコンを、まだ追加していないものから順に追加する。
- 候補の価格を最大ヒープ(優先度付きキュー)で管理する。
最大ヒープを使えば、候補の中で最も高い価格を効率よく取り出せます。
アルゴリズム
- \(M > N\) なら、台数が足りないため \(-1\) を出力する。
- パソコンを性能 \(A_i\) の降順にソートする。
- 客を要求性能 \(C_j\) の降順にソートする。
- 空の最大ヒープ
prices、パソコンを走査する位置pos = 0、売上合計answer = 0を用意する。 - 各客について、要求性能を
requiredとして次を行う。pos番目のパソコンが性能条件を満たす間、その価格をヒープに追加し、posを進める。- ヒープが空なら、現在の客に販売できる未販売のパソコンがない。\(-1\) を出力して終了する。
- ヒープの最大値を
answerに加え、その要素を取り除く。
- 全員の処理が終わったら
answerを出力する。
各客を処理するとき、ヒープにはその客に販売できる未販売のパソコンの価格がすべて入っています。前の客の処理で追加したパソコンも、現在の客の要求性能を満たすため、そのまま候補として使えます。
また、貪欲な選択は全員への販売可能性を保つので、途中でヒープが空になった場合は、元の問題でも全員への販売は不可能です。
計算量
- 時間計算量: \(O(N \log N + M \log M)\)
- 空間計算量: \(O(N + M)\)
ソートに \(O(N \log N + M \log M)\) かかります。ヒープへの追加は各パソコンにつき高々 \(1\) 回、取り出しは各客につき \(1\) 回です。\(M > N\) の場合は先に終了するため、ヒープ操作の合計は \(O(N \log N)\) に収まります。
実装のポイント
売上合計には
long longを使います。
最大で \(10^5 \times 10^9 = 10^{14}\) 円になるため、32 ビット整数では収まりません。性能条件は「以上」です。
ヒープへの追加条件はcomputers[pos].first >= requiredとします。C++ の
priority_queue<int>は最大ヒープです。
top()で最大価格を取得し、pop()で販売済みのパソコンを候補から取り除けます。posは戻しません。
パソコンと客をどちらも降順に並べることで、各パソコンを一度だけヒープへ追加できます。同価格のパソコンも別々の要素として管理されます。
この問題では最大売上だけを求めるので、ヒープにはパソコンの番号ではなく価格だけを格納すれば十分です。ソースコード
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
cin >> N >> M;
vector<pair<int, int>> computers(N);
for (auto& [a, b] : computers) {
cin >> a >> b;
}
vector<int> customers(M);
for (int& c : customers) {
cin >> c;
}
if (M > N) {
cout << -1 << '\n';
return 0;
}
sort(computers.begin(), computers.end(), greater<pair<int, int>>());
sort(customers.begin(), customers.end(), greater<int>());
priority_queue<int> prices;
long long answer = 0;
int pos = 0;
for (int required : customers) {
while (pos < N && computers[pos].first >= required) {
prices.push(computers[pos].second);
++pos;
}
if (prices.empty()) {
cout << -1 << '\n';
return 0;
}
answer += prices.top();
prices.pop();
}
cout << answer << '\n';
return 0;
}
この解説は gpt-6-astra-medium によって生成されました。
posted:
last update: