Official

D - パソコンの販売 / Selling Computers Editorial by admin Editorial for printing

Gemini 3.8 Flash (High)

概要

客とパソコンをそれぞれ性能の降順(大きい順)にソートし、要求性能が厳しい客から順に「その客が購入可能なパソコンの中で最も価格が高いもの」を優先度付きキュー(ヒープ)を用いて選ぶ貪欲法によって解くことができます。

考察

1. 自明なケースの確認

まず、\(N < M\)(パソコンの台数より客の人数の方が多い)の場合は、全員に異なるパソコンを販売することは不可能なため、即座に -1 を出力します。

2. なぜ「要求性能が高い客」から考えるのか?

客によって購入できるパソコンの選択肢の広さが異なります。 - 要求性能 \(C_j\) が高い客:選べるパソコンが少ない(条件が厳しい) - 要求性能 \(C_j\) が低い客:選べるパソコンが多い(条件が緩い)

要求性能が低い客は高性能なパソコンでも低性能なパソコンでも購入できますが、要求性能が高い客は高性能なパソコンしか購入できません。そのため、選択肢が限られている「要求性能が高い客」から優先的にパソコンを割り当てていく必要があります。

3. 選択肢の包含関係と貪欲法

客を要求性能の高い順(\(C_1 \ge C_2 \ge \dots \ge C_M\))に並べ替えて考えます。

客 \(j\) が購入できるパソコンの集合を \(S_j = \{ i \mid A_i \ge C_j \}\) とすると、 $\(S_1 \subseteq S_2 \subseteq \dots \subseteq S_M\)$ という包含関係が成り立ちます。つまり、客を順番に見ていくにつれて、購入可能なパソコンの選択肢は増える一方であり、一度選択可能になったパソコンが後から選択不可能になることはありません。

この性質から、以下の貪欲法が正当であることが分かります: - 客 \(j\) を見るとき、まだ候補に入っていないパソコンのうち性能が \(C_j\) 以上のものをすべて候補プールに追加する。 - 候補プールの中から最も価格が高いパソコンを客 \(j\) に割り当てる。 - なぜなら、現在プールにあるパソコンはこれ以降の客(より要求が緩い客)も全員購入できますが、客 \(j\) に売るパソコンとして候補の中で最も高価なものを確定させてしまっても、将来の客の選択肢を狭める損が生じないためです。 - もし候補プールが空であれば、客 \(j\) の条件を満たせるパソコンが存在しないため、全員に販売することはできません(-1 を出力)。

具体例

  • パソコン: \(P_1(性能 10, 価格 100), P_2(性能 10, 価格 50), P_3(性能 5, 価格 200)\)
  • 客: \(K_1(要求 10), K_2(要求 5)\)
  1. \(K_1\) (要求 10) の処理:
    • 性能 10 以上のパソコンは \(P_1(100), P_2(50)\) です。これをプールに追加します。
    • プールの中で最も高い \(P_1(100)\) を \(K_1\) に割り当てます。(プールの残り: \(P_2(50)\))
  2. \(K_2\) (要求 5) の処理:
    • 新たに性能 5 以上のパソコン \(P_3(200)\) をプールに追加します。(プール: \(P_2(50), P_3(200)\))
    • 最も高い \(P_3(200)\) を \(K_2\) に割り当てます。
  3. 結果: \(100 + 200 = 300\) となり、最大売上が達成されます。

アルゴリズム

  1. \(N < M\) であれば -1 を出力して終了する。
  2. パソコンを性能 \(A_i\) の降順にソートする。
  3. 客を要求性能 \(C_j\) の降順にソートする。
  4. 価格を管理する最大ヒープ(Pythonでは価格を負の値にした最小ヒープ)を用意する。
  5. 各客 \(c \in C\) について、要求性能の高い順に走査する:
    • まだヒープに追加されていないパソコンのうち、性能が \(c\) 以上のものをすべてヒープに追加する。
    • ヒープが空であれば、この客に売れるパソコンがないため -1 を出力して終了する。
    • ヒープから最大価格を取り出し、合計売上に加算する。
  6. 全員の客に割り当てが終わったら、合計売上を出力する。

計算量

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

    • パソコンのソートに \(O(N \log N)\)
    • 客のソートに \(O(M \log M)\)
    • パソコンはヒープに高々 1 回追加されるため、ヒープ操作の合計時間は \(O(N \log N)\)
    • 客ごとにヒープから最大値を取り出す操作は \(O(M \log N)\)
    • 全体として \(O(N \log N + M \log M)\) となり、\(N, M \le 10^5\) でも十分に高速です。
  • 空間計算量: \(O(N + M)\)

    • パソコンおよび客のデータを保持する配列と、ヒープで最大 \(O(N)\) のメモリを使用します。

実装のポイント

  • 優先度付きキュー(最大ヒープ)の利用: Pythonの heapq モジュールは標準で「最小ヒープ」を提供します。そのため、価格に -1 を掛けてヒープに格納することで最大ヒープとして機能させます。

  • 2ポインタ(尺取り法)によるパソコンの走査: パソコンのリストを走査するインデックス pc_idx を保持し、1度ヒープに入れたパソコンを再度見ないようにすることで、パソコン全体の走査にかかる時間を \(O(N)\) に抑えています。

  • 高速な入出力: \(N, M \le 10^5\) と入力サイズが大きいため、sys.stdin.read().split() を用いて一度に入力を読み込むことで入出力のボトルネックを防いでいます。

    ソースコード

import sys
import heapq

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    if N < M:
        print(-1)
        return
    
    pcs = [(int(input_data[i]), int(input_data[i+1])) for i in range(2, 2 + 2 * N, 2)]
    C = [int(x) for x in input_data[2 + 2 * N : 2 + 2 * N + M]]
    
    pcs.sort(key=lambda x: x[0], reverse=True)
    C.sort(reverse=True)
    
    heap = []
    pc_idx = 0
    total_sales = 0
    
    for c in C:
        while pc_idx < N and pcs[pc_idx][0] >= c:
            heapq.heappush(heap, -pcs[pc_idx][1])
            pc_idx += 1
        
        if not heap:
            print(-1)
            return
        
        total_sales += -heapq.heappop(heap)
        
    print(total_sales)

if __name__ == '__main__':
    main()

この解説は gemini-3.8-flash-high によって生成されました。

posted:
last update: