Official

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

Claude Opus 5 (High)

Overview

In this problem, we are given \(N\) computers (with performance \(A_i\) and price \(B_i\)) and \(M\) customers (with required performance \(C_j\)). We need to assign a distinct computer to each customer such that each computer’s performance meets or exceeds the customer’s requirement, while maximizing the total price. This problem can be solved using a greedy approach that processes customers in descending order of requirement strictness, along with a priority queue (heap).

Analysis

Key Observation 1: Customers with stricter requirements have fewer options

A customer \(j\) can only purchase computers that satisfy \(A_i \ge C_j\). The larger \(C_j\) is, the smaller the set of candidate computers becomes. Furthermore, the candidate set for a customer with a smaller \(C_j\) always contains the candidate set for a customer with a larger \(C_j\) (the essential property is that the candidate sets form an inclusion hierarchy).

Therefore, it is natural to process customers in descending order of \(C_j\). If we postpone customers with fewer options, we risk having the computers they could have bought taken by other customers.

Key Observation 2: Greedily pick the most expensive candidate

When processing \(C\) in descending order, the “available candidate set” for a customer consists of all unsold computers satisfying \(A_i \ge C_j\). Here, choosing the computer with the maximum price is optimal.

Reason (Exchange Argument): Suppose that in some optimal solution, computer \(x\) with price \(b\) is assigned to this customer, and there exists an available candidate computer \(y\) with price \(b' > b\). - If \(y\) is not sold to anyone, replacing \(x\) with \(y\) increases the total revenue, which contradicts optimality (a better solution exists). - If \(y\) is sold to a later customer \(k\) (\(C_k \le C_j\)), we can swap \(x\) and \(y\). Since \(A_x \ge C_j \ge C_k\), customer \(k\) can buy \(x\), so the condition remains satisfied after the swap, and the total revenue does not change. Thus, the solution that picks the most expensive computer is also optimal.

In short, greedily picking the highest-priced computer among the candidates in descending order of \(C\) achieves the maximum total value.

A Naive Implementation is Too Slow

If we search for the maximum \(B_i\) by checking all unused computers satisfying \(A_i \ge C_j\) for each customer, it takes \(O(N)\) time per customer, leading to \(O(NM) = 10^{10}\) in total, which results in TLE.

We can speed this up by: - Sorting the computers in descending order of \(A_i\), - As we iterate through customers in descending order of \(C_j\), adding only the “newly eligible computers” to the candidate set (each computer is added at most once, totaling \(N\) additions), - Using a max-heap (priority queue) to extract the maximum price in \(O(\log N)\) time.

This is a standard two-pointer technique where we advance a pointer and insert elements into a heap.

Determining Infeasibility (-1)

If the heap is empty when processing a customer, no computer is left that can be sold to them. Because we are processing customers with the fewest options first, it is impossible to satisfy all customers at this point, so we output \(-1\).

Algorithm

  1. Treat the computers as pairs \((A_i, B_i)\) and sort them in descending order of \(A_i\).
  2. Sort the customers’ requirements \(C_j\) in descending order.
  3. Initialize an empty max-heap heap, a pointer idx = 0, and the answer total = 0.
  4. Iterate through the sorted \(C\) from the beginning, considering each value as \(c\):
    • While idx < N and sa[idx] >= c, push sb[idx] into the heap and increment idx += 1 (i.e., all computers this customer can purchase are added to the candidate set).
    • If the heap is empty, output -1 and terminate.
    • Otherwise, pop the maximum value from the heap and add it to total.
  5. After successfully processing all customers, output total.

Concrete example: \(N=3\), computers \((A,B) = (10, 5), (7, 100), (3, 50)\), customers \(C = (3, 7)\).

  • Descending sort: computers are \((10,5), (7,100), (3,50)\), customers are \(7, 3\).
  • \(c=7\): Add \((10,5), (7,100)\) with \(A \ge 7\) \(\to\) heap \(\{5, 100\}\) \(\to\) pick the maximum \(100\) (total = 100).
  • \(c=3\): Add \((3,50)\) with \(A \ge 3\) \(\to\) heap \(\{5, 50\}\) \(\to\) pick the maximum \(50\) (total = 150).
  • Answer: \(150\).

If we had processed customers in ascending order and simply taken the maximum, customer \(c=3\) would take \(100\), leaving \(c=7\) with fewer options (yielding \(100+5=105\) in this example). Thus, processing in descending order is essential.

Complexity

  • Time Complexity: \(O((N + M) \log N)\) (sorting and heap operations; each computer is pushed and popped at most once)
  • Space Complexity: \(O(N + M)\)

Implementation Notes

  • Python’s heapq is a min-heap, so to extract maximum values, push the negated values and negate them back when popping (in code, this can be written as total -= pop(heap) to add by subtracting a negative number).

  • Since the input can have up to around \(2 \times 10^5\) lines, using sys.stdin.buffer.read().split() to read everything at once provides fast I/O.

  • The answer can reach up to around \(10^5 \times 10^9 = 10^{14}\), so in languages like C++, you must use a 64-bit integer (long long) (not an issue in Python due to its arbitrary-precision integers).

  • When \(M > N\), the answer is always \(-1\). The algorithm above automatically detects this when the heap runs empty, so no special edge-case handling is required.

  • For sorting, simply creating an array of values and sorting it is sufficient (there is no need to keep track of original indices; just sorting the pairs \((A_i, B_i)\) by \(A\) in descending order is enough).

    Source Code

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()

This editorial was generated by claude5opus-high.

posted:
last update: