D - パソコンの販売 / Selling Computers Editorial by admin Editorial for printing
Claude Opus 5 (High)概要
\(N\) 台のパソコン(性能 \(A_i\)、価格 \(B_i\))を \(M\) 人の客(要求性能 \(C_j\))に、それぞれ相異なる 1 台ずつ「性能が要求以上」となるように割り当て、価格の総和を最大化する問題です。要求の厳しい客から順に処理する貪欲法と優先度付きキュー(ヒープ)で解けます。
考察
重要な観察 1:要求が厳しい客ほど選択肢が少ない
客 \(j\) が買えるパソコンは「\(A_i \ge C_j\)」を満たすものです。\(C_j\) が大きいほど候補は狭くなり、\(C_j\) が小さい客の候補集合は \(C_j\) が大きい客の候補集合を必ず含みます(候補集合が包含関係になっている、という点が本質です)。
したがって、\(C_j\) が大きい客から順に決めていくのが自然です。選択肢の少ない客を後回しにすると、その客が買えるパソコンを別の客に取られてしまう危険があるからです。
重要な観察 2:候補の中から最も高いものを取ればよい
\(C\) を降順に処理していくとき、ある客の時点で「使用可能な候補集合」は、\(A_i \ge C_j\) を満たすまだ売れていないパソコン全体です。ここで 価格が最大のパソコンを選ぶのが最適 です。
理由(交換論法):ある最適解で、この客に価格 \(b\) のパソコン \(x\) を割り当てていて、候補の中に価格 \(b' > b\) のパソコン \(y\) があるとします。 - \(y\) が誰にも売られていないなら、\(x \to y\) に取り替えれば売上が増えるので矛盾(もっと良い解がある)。 - \(y\) が後の客 \(k\)(\(C_k \le C_j\))に売られているなら、\(x\) と \(y\) を交換します。客 \(k\) は \(A_x \ge C_j \ge C_k\) なので \(x\) を買えるため、交換後も条件を満たし、売上の総和は変わりません。よって「最も高いものを選ぶ」解も最適解になります。
つまり「\(C\) の降順に、候補の中から最も価格が高いものを貪欲に取る」で最大値が得られます。
素朴な実装だと遅い
毎回「\(A_i \ge C_j\) を満たす未使用のパソコンを全部見て最大の \(B_i\) を探す」と、1 人あたり \(O(N)\) かかり全体で \(O(NM) = 10^{10}\) となって TLE します。
そこで、 - パソコンも \(A_i\) の降順にソートしておき、 - 客を \(C_j\) の降順に見るときに「新しく条件を満たすようになったパソコン」だけを候補集合に追加する(追加は全体で合計 \(N\) 回だけ) - 候補集合から最大値を取り出す操作を 最大ヒープ(優先度付きキュー) で \(O(\log N)\) で行う
とすることで高速化できます。これはいわゆる「しゃくとり的にポインタを進めながらヒープに入れる」典型テクニックです。
判定(-1)について
ある客の順番でヒープが空なら、その客に売れるパソコンが 1 台も残っていません。この時点で(最も選択肢の狭い客から処理しているので)全員に販売することは不可能であり、\(-1\) を出力します。
アルゴリズム
- パソコンを \((A_i, B_i)\) のペアとして、\(A_i\) の降順にソートする。
- 客の要求 \(C_j\) を降順にソートする。
- 空の最大ヒープ
heapとポインタidx = 0、答えtotal = 0を用意する。 - 降順の \(C\) を先頭から順に \(c\) として見ていき、
idx < Nかつsa[idx] >= cである間、sb[idx]をヒープに入れてidx += 1(=この客が買える全パソコンが候補に入る)。- ヒープが空なら
-1を出力して終了。 - そうでなければヒープから最大値を取り出し
totalに加算する。
- すべての客を処理できたら
totalを出力する。
具体例:\(N=3\)、パソコン \((A,B) = (10, 5), (7, 100), (3, 50)\)、客 \(C = (3, 7)\)。
- 降順ソート:パソコンは \((10,5), (7,100), (3,50)\)、客は \(7, 3\)。
- \(c=7\):\(A \ge 7\) の \((10,5), (7,100)\) を追加 → ヒープ \(\{5, 100\}\) → 最大 \(100\) を取る(
total = 100)。 - \(c=3\):\(A \ge 3\) の \((3,50)\) を追加 → ヒープ \(\{5, 50\}\) → 最大 \(50\) を取る(
total = 150)。 - 答え \(150\)。
もし客を昇順に処理して安易に最大を取ると、\(c=3\) で \(100\) を取ってしまい \(c=7\) 側が損をする(この例だと \(100+5=105\))ので、降順に処理することが重要です。
計算量
- 時間計算量: \(O((N + M) \log N)\)(ソートとヒープ操作。各パソコンは高々 1 回 push / pop される)
- 空間計算量: \(O(N + M)\)
実装のポイント
Python の
heapqは最小ヒープなので、最大値を取りたい場合は値を負にして push し、pop した値の符号を戻します(コードではtotal -= pop(heap)としてマイナスのマイナスで加算しています)。入力が最大 \(2 \times 10^5\) 行規模なので、
sys.stdin.buffer.read().split()で一括読み込みすると高速です。答えは最大で \(10^5 \times 10^9 = 10^{14}\) 程度になるため、C++ 等では 64bit 整数(
long long)を使う必要があります(Python は多倍長なので気にしなくてよい)。\(M > N\) のときは必ず \(-1\) ですが、上のアルゴリズムでは「途中でヒープが空になる」ことで自動的に検出されるため、特別扱いは不要です。
ソートは「値の配列を作ってソート」でも構いません(インデックスを保持する必要はなく、\((A_i, B_i)\) のペアを \(A\) 降順に並べるだけで十分です)。
ソースコード
import sys, heapq
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); m = int(data[1])
A = [0]*n
B = [0]*n
for i in range(n):
A[i] = int(data[2+2*i])
B[i] = int(data[3+2*i])
order = sorted(range(n), key=lambda i: -A[i])
sa = [A[i] for i in order]
sb = [B[i] for i in order]
base = 2 + 2*n
C = [int(x) for x in data[base:base+m]]
C.sort(reverse=True)
heap = []
push = heapq.heappush
pop = heapq.heappop
idx = 0
total = 0
for c in C:
while idx < n and sa[idx] >= c:
push(heap, -sb[idx])
idx += 1
if not heap:
sys.stdout.write("-1\n")
return
total -= pop(heap)
sys.stdout.write(str(total) + "\n")
main()
この解説は claude5opus-high によって生成されました。
posted:
last update: