公式

D - パソコンの販売 / Selling Computers 解説 by admin 印刷ページ

gpt-6-astra-medium

概要

要求性能の高い客から順に、条件を満たす未販売のパソコンのうち、最も価格が高いものを販売します。この貪欲法を、ソートと優先度付きキュー(ヒープ)で効率よく実装します。

考察

要求性能の高い客を先に処理する

要求性能が低い客は多くのパソコンを購入できますが、要求性能が高い客が購入できるパソコンは限られています。

例えば、パソコンが次の \(2\) 台だとします。

性能 価格
\(10\) \(100\)
\(5\) \(50\)

要求性能が \(5\) の客と \(10\) の客がいるとき、要求性能が \(5\) の客に最も高価なパソコンを先に販売すると、要求性能が \(10\) の客に販売できなくなります。

そこで、要求性能の高い客から順に処理することを考えます。

条件を満たす中で、最も高価なものを選んでよい

現在の客の要求性能を \(c\) とします。残りの客は要求性能の降順に並んでいるため、全員の要求性能が \(c\) 以下です。

したがって、現在の客に販売できるパソコンは、残りのどの客にも販売できます。

この性質から、現在の客には、販売可能な未販売のパソコンのうち最も高価なものを選んで構いません。交換によって説明できます。

これまでの選択が同じである最適な割り当てを考え、そこで現在の客に販売するパソコンを \(x\)、貪欲法で選ぶ最も高価なパソコンを \(y\) とします。

  • \(y\) が現在の客に割り当てられているなら、そのままでよいです。
  • \(y\) が誰にも割り当てられていないなら、\(x\) を \(y\) に置き換えます。\(B_y \ge B_x\) なので、売上は減りません。
  • \(y\) が後の客に割り当てられているなら、現在の客に \(y\)、その後の客に \(x\) を販売するよう交換します。\(x\) は現在の客の要求を満たすので、要求性能がそれ以下の後の客にも販売できます。売上の総和も変わりません。

よって、各段階で最も高価なものを選ぶ貪欲法により、最大売上を求められます。

候補の管理を高速化する

客ごとにすべてのパソコンを調べると、時間計算量は \(O(NM)\) となり、最大で \(10^{10}\) 回程度の確認が必要です。

これを避けるため、パソコンも性能の降順に並べます。

客の要求性能は処理が進むにつれて下がるため、販売可能なパソコンは順次増えていきます。新しく条件を満たしたパソコンだけをヒープに追加すれば、毎回すべてを調べる必要はありません。

ヒープには候補の価格を入れ、最も高い価格を取り出せるようにします。

アルゴリズム

  1. \(N < M\) なら、台数が足りないため \(-1\) を出力します。
  2. パソコンを性能 \(A_i\) の降順にソートします。
  3. 客を要求性能 \(C_j\) の降順にソートします。
  4. 空のヒープと、売上の合計 total = 0 を用意します。また、まだヒープに追加していない最初のパソコンを指す添字 i を管理します。
  5. 各客について、要求性能を requirement として次を行います。
    • computers[i] の性能が requirement 以上である間、その価格をヒープに追加して i を進めます。
    • ヒープが空なら、その客に販売できる未販売のパソコンがないため、\(-1\) を出力して終了します。
    • ヒープから最も高い価格を取り出し、total に加えます。
  6. 全員に販売できたら、total を出力します。

各客を処理する際、追加処理後のヒープには「その客に販売できる未販売のパソコン」がすべて入っています。取り出したパソコンはヒープから削除されるため、同じパソコンを複数の客に販売することもありません。

また、交換の議論から、これまでの貪欲な選択によって全員への販売が不可能になることはありません。したがって、途中でヒープが空になった場合は、もともと全員に販売できないと判断できます。

計算量

  • 時間計算量: \(O(N \log N + M \log M + (N+M)\log N)\)
  • 空間計算量: \(O(N+M)\)

パソコンと客のソートに、それぞれ \(O(N \log N)\)、\(O(M \log M)\) かかります。各パソコンのヒープへの追加は高々 \(1\) 回、取り出しは客ごとに \(1\) 回です。

なお、\(N < M\) の場合は先に終了するため、処理を続ける場合は \(M \le N\) であり、時間計算量は \(O(N \log N)\) とも表せます。

実装のポイント

  • Python の heapq は最小値を取り出すヒープです。
    価格 \(B_i\) の代わりに \(-B_i\) を格納すると、最も高い価格から取り出せます。コードでは total -= pop(heap) により、元の価格を売上に加えています。

  • 性能が要求値と等しい場合も販売できます。
    ヒープへの追加条件は computers[i][0] >= requirement です。

  • 客ごとにヒープを空にしないようにします。
    前の客に販売できたパソコンは、それ以降の客にも販売できます。選ばれなかった候補は、そのまま残して使います。

  • 売上の合計は最大 \(10^{14}\) になります。
    Python の整数なら問題ありませんが、他の言語では \(64\) ビット整数を使用する必要があります。

    ソースコード

import sys
import heapq


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n, m = data[0], data[1]

    if n < m:
        print(-1)
        return

    end = 2 + 2 * n
    computers = [(data[i], data[i + 1]) for i in range(2, end, 2)]
    customers = data[end:end + m]
    del data

    computers.sort(reverse=True)
    customers.sort(reverse=True)

    heap = []
    push = heapq.heappush
    pop = heapq.heappop
    total = 0
    i = 0

    for requirement in customers:
        while i < n and computers[i][0] >= requirement:
            push(heap, -computers[i][1])
            i += 1

        if not heap:
            print(-1)
            return

        total -= pop(heap)

    print(total)


if __name__ == "__main__":
    main()

この解説は gpt-6-astra-medium によって生成されました。

投稿日時:
最終更新: