D - パソコンの販売 / Selling Computers Editorial by admin Editorial for printing
Claude Opus 5 (High)概要
各客は「性能が \(C_j\) 以上のパソコン」なら何でも買ってくれるので、客とパソコンの割り当て(マッチング)のうち価格の総和が最大になるものを求める問題です。要求性能の大きい客から順に「買える中で一番高いパソコン」を渡す貪欲法 + 優先度付きキュー(ヒープ)で解けます。
考察
観察 1: 価格は制約に無関係
客 \(j\) が買えるパソコンの集合は \(\{i : A_i \ge C_j\}\) であり、価格 \(B_i\) は「買えるかどうか」には一切影響しません。つまり売上を最大化するには「性能条件を満たしつつ、なるべく高いパソコンを配る」だけを考えればよいです。
観察 2: 選べる集合が入れ子(ネスト)になっている
\(C_j \ge C_k\) ならば、客 \(j\) が買えるパソコンの集合は客 \(k\) が買えるパソコンの集合に完全に含まれます。
\[C_j \ge C_k \implies \{i : A_i \ge C_j\} \subseteq \{i : A_i \ge C_k\}\]
つまり「要求が厳しい客ほど選択肢が少ない」という綺麗な構造があります。この場合、要求が厳しい(\(C_j\) が大きい)客から先に処理するのが自然です。選択肢の少ない客を後回しにすると、そのパソコンを他の客に取られてしまう恐れがあるからです。
観察 3: 厳しい客に「一番高いパソコン」を渡してよい
要求が最も厳しい客 \(j\) に対して、条件を満たすパソコンのうち最も価格が高いもの \(y\) を渡すのが最適です。
証明(交換論法):ある最適解で客 \(j\) がパソコン \(x\)(\(B_x \le B_y\))を受け取っているとします。 - \(y\) がどの客にも売られていない場合:\(x\) を \(y\) に置き換えても \(A_y \ge C_j\) なので有効で、売上は減りません。 - \(y\) が別の客 \(k\) に売られている場合:\(j\) が最も要求の厳しい客なので \(C_k \le C_j \le A_x\) が成り立ち、\(x\) と \(y\) を交換しても両方の条件を満たします。売上の総和は変わりません。
どちらの場合も「\(j\) に最も高いパソコンを渡す最適解」が作れるので、貪欲で構いません。以降は \(j\) と \(y\) を除いた小さな問題を同じ論法で処理できます。
素朴な実装だとどうなるか
各客について毎回「\(A_i \ge C_j\) を満たす未使用のパソコンの中で最大の \(B_i\)」を線形探索すると \(O(NM)\) となり、\(N, M \le 10^5\) では \(10^{10}\) 回程度の操作になって TLE します。
これを解決するために、候補パソコンの集合を優先度付きキュー(最大ヒープ)で管理します。客を \(C_j\) の降順に処理していくと、\(C_j\) は単調に小さくなっていくので、候補に「追加」されるパソコンはあっても「除外」されるパソコンは出てきません(観察 2 の入れ子構造)。よってパソコンを \(A_i\) の降順にソートしておけば、しゃくとり法(二重ポインタ)のように 1 回ずつヒープに追加するだけで候補集合を管理できます。
アルゴリズム
- パソコンを \(A_i\) の降順にソートする。
- 客の要求 \(C_j\) を降順にソートする。
- 最大ヒープ(
priority_queue<int>、キーは価格 \(B\))を空で用意し、パソコン側のポインタidx = 0とする。 - 客を \(j = 1, 2, \dots, M\)(\(C\) の降順)の順に見ていく:
idxの指すパソコンの性能が \(C_j\) 以上である間、その価格をヒープに push してidxを進める(今の客が買える全パソコンがヒープに入る)。- ヒープが空なら、この客に売れるパソコンが 1 台も残っていないので
-1を出力して終了。 - ヒープの最大値を取り出して売上に加算する。
- 全員に売れたら売上の総和を出力する。
具体例
\(N = 3\)、パソコン \((A, B) = (10, 5), (7, 100), (3, 50)\)、客 \(C = (3, 7)\) の場合。
降順ソートすると パソコンは \((10,5), (7,100), (3,50)\)、客は \(C = 7, 3\)。
- 客 \(C = 7\):\(A \ge 7\) のパソコン \((10,5), (7,100)\) をヒープへ → ヒープ \(\{5, 100\}\)。最大の \(100\) を売る。売上 \(100\)。
- 客 \(C = 3\):\((3,50)\) を追加 → ヒープ \(\{5, 50\}\)。最大の \(50\) を売る。売上 \(150\)。
答えは \(150\)。もし要求の緩い客から処理して \((10,5)\) ではなく安いものから配るなどすると最大にならないことが分かります。
「-1」になる条件について
\(M > N\) のときや、要求を満たすパソコン数が足りないときは、上の手順の途中で必ずヒープが空になります。理由は、要求が厳しい客から順に処理しているので、上位 \(k\) 人の客を処理し終えた時点で「使用可能だったパソコン数 \(<\) \(k\)」となるのは本当にマッチングが存在しない場合のみだからです(ホールの定理における「厳しい客だけを集めた集合」が反例になる)。したがってヒープが空になった時点で -1 を出力して打ち切ってよいです。
計算量
- 時間計算量: \(O((N + M) \log N)\)(ソートとヒープ操作。各パソコンは高々 1 回 push/pop される)
- 空間計算量: \(O(N + M)\)
実装のポイント
売上はオーバーフローに注意:\(M \le 10^5\)、\(B_i \le 10^9\) なので総和は最大 \(10^{14}\) 程度。
long long(Python 以外では 64bit 整数)を使います。idxはループの外で持つ:客ごとに 0 に戻してはいけません。全体で高々 \(N\) 回しか進まないので、これが \(O(N \log N)\) に抑える鍵です。ヒープに入れるのは「価格 \(B\)」だけで十分です(どのパソコンかを復元する必要はありません)。
ソートは「パソコンは \(A\) の降順」「客は \(C\) の降順」の 2 つ。降順で揃えるのを忘れないようにしましょう(
greater<int>()やラムダを利用)。入出力が最大 \(2 \times 10^5\) 行程度あるので、C++ では
scanfを使うかcinの同期を切る(ios::sync_with_stdio(false))と安全です。ソースコード
#include <bits/stdc++.h>
using namespace std;
int main(){
int N, M;
if(scanf("%d %d", &N, &M)!=2) return 0;
vector<pair<int,int>> pc(N);
for(int i=0;i<N;i++){
int a,b; scanf("%d %d",&a,&b);
pc[i]={a,b};
}
vector<int> C(M);
for(int j=0;j<M;j++) scanf("%d",&C[j]);
sort(pc.begin(), pc.end(), [](const pair<int,int>&x, const pair<int,int>&y){
return x.first > y.first;
});
sort(C.begin(), C.end(), greater<int>());
priority_queue<int> pq;
int idx = 0;
long long total = 0;
for(int j=0;j<M;j++){
while(idx < N && pc[idx].first >= C[j]){
pq.push(pc[idx].second);
idx++;
}
if(pq.empty()){
printf("-1\n");
return 0;
}
total += pq.top();
pq.pop();
}
printf("%lld\n", total);
return 0;
}
この解説は claude5opus-high によって生成されました。
posted:
last update: