概要

お客さんの予算とチケットの価格、および各チケットの最大販売枚数の制限がある中で、順番にチケットを販売したとき、何人のお客さんにチケットを売ることができるかを求める問題です。

考察

この問題では、各お客さんに対して「その予算内で買える最も高額なチケット」を選び、かつそのチケットがまだ \(K\) 枚以上売れていない場合に限り販売を行います。

重要な観察

• 各お客さんに対し、購入可能な最も高額なチケットを選ぶ必要がある。
• チケットの価格はすべて異なるため、このようなチケットは一意に定まる。
• チケットの販売上限（\(K\)枚）を超えてはいけない。

素朴なアプローチでは？

もし毎回線形探索で該当するチケットを探していたら、最悪ケースで \(O(NM)\) となり、\(N, M \sim 2 \times 10^5\) では間に合いません。

また、単純に安い順にチケットを割り当てると、高額のチケットを欲しがる人を満足させられず、結果として売れるチケット数が減る可能性があります。

解決方法

チケットの価格リスト \(G\) をソートしておけば、二分探索によって各お客さんの予算以下の範囲で最も高い価格のチケットを高速に求めることができます。

さらに、各チケットの販売数を管理することで、販売上限を超えないようにできます。

アルゴリズム

1. チケットの価格リスト \(G\) を昇順にソートします。
2. 各お客さんの予算 \(S_i\) に対して以下を行います：
   • 二分探索（bisect_right を使用）により、「\(S_i\) 以下の最大の価格」を持つチケットのインデックスを求めます。
   • そのチケットの現在の販売数が \(K\) 未満であれば、そのチケットを 1 枚販売し、販売数を増やします。
   • 売れれば結果のカウントを増やします。
3. 全てのお客さんを処理したら、販売できた人数を出力します。

例

例えば、 - お客さんの予算: \([5, 10, 15]\) - チケットの価格: \([3, 7, 9, 12]\)、\(K=1\)

という場合： - 1人目（予算5）→ 最も高いのは3 → 販売可能 → 販売数1に → 成功 - 2人目（予算10）→ 最も高いのは9 → 販売可能 → 販売数1に → 成功 - 3人目（予算15）→ 最も高いのは12 → しかし販売数がまだ0なのでOK → 成功

よって答えは3人。

計算量

• 時間計算量: \(O((N + M) \log M)\)
  • ソートに \(O(M \log M)\)
  • 各お客さんに対する二分探索と処理が \(O(N \log M)\)
• 空間計算量: \(O(M + N)\)
  • チケット価格リスト、お客さんのリスト、販売数管理用の辞書など

実装のポイント

• bisect.bisect_right(G, s) を使うことで、\(s\) 以下の最大要素の位置を効率的に取得できる。

• defaultdict(int) を使うことで、販売数の初期値を0として扱える。

• 各チケットの販売上限を正確に守ることが重要で、超えた場合は売らないことに注意。

  ソースコード

import bisect
from collections import defaultdict
import sys

input = sys.stdin.read

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N, M, K = map(int, data[:3])
    S = list(map(int, data[3:3+N]))
    G = list(map(int, data[3+N:3+N+M]))
    
    # Sort ticket prices
    G.sort()
    
    # Count of tickets sold per type
    sold_count = defaultdict(int)
    
    res = 0
    
    for s in S:
        # Binary search for the most expensive ticket <= s
        idx = bisect.bisect_right(G, s) - 1
        if idx >= 0:
            best_ticket = G[idx]
            if sold_count[best_ticket] < K:
                sold_count[best_ticket] += 1
                res += 1
            # else: do nothing, cannot sell
        # else: no ticket affordable, do nothing
    
    print(res)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。