概要

各カテゴリから最大1つの企画を選んで採用するとき、集客の見込み数の合計の最大値を求める問題です。

考察

重要な観察は、同じカテゴリ内の複数の企画を同時に採用できないという制約です。そのため、各カテゴリでは集客の見込み数が最大の企画のみを候補として考えれば十分です。なぜなら、もしあるカテゴリから企画を採用するなら、そのカテゴリ内で最も集客の見込み数が大きいものを選ぶのが最適だからです。

素朴なアプローチとして、全てのカテゴリの全ての企画を考慮すると、最大で \(N\) 個の企画を扱う必要があり、さらに組み合わせを考えると計算量が爆発してしまいます。しかし、上記の観察により、各カテゴリの最大値のみに注目することで、問題を単純化できます。

アルゴリズム

1. 各カテゴリごとに、属する企画の集客の見込み数をリストに格納します
2. 各カテゴリについて、集客の見込み数の最大値を求めます（企画が存在しないカテゴリは無視します）
3. 得られた最大値を大きい順にソートします
4. ソートされた最大値の合計を計算して出力します

各カテゴリから最大1つしか選べないため、全てのカテゴリの最大値を足し合わせるのが最適解となります。企画が存在しないカテゴリは採用できないので無視します。

計算量

• 時間計算量: \(O(N + K \log K)\)
  • 入力データの読み込みとカテゴリごとの分類に \(O(N)\)
  • 各カテゴリの最大値計算に \(O(N)\)（各企画は1回ずつ処理される）
  • 最大値のソートに \(O(K \log K)\)（\(K\) はカテゴリ数）
• 空間計算量: \(O(N + K)\)
  • カテゴリごとのリストを格納するために \(O(N)\)
  • 最大値を格納するリストに \(O(K)\)

実装のポイント

• カテゴリ番号が \(K\) 以下かどうかをチェック（問題文では \(B_i \leq K\) だが、念のため）

• 空のカテゴリは結果に影響しないので無視

• 最大値のリストを降順ソートする必要は実際にはない（合計するだけなので）が、直感的に分かりやすい

• 入力データが空の場合の処理を忘れずに

  ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
    
    n = int(data[0])
    k = int(data[1])
    categories = [[] for _ in range(k+1)]
    
    index = 2
    for i in range(n):
        b = int(data[index])
        d = int(data[index+1])
        index += 2
        if b <= k:
            categories[b].append(d)
    
    max_values = []
    for i in range(1, k+1):
        if categories[i]:
            max_val = max(categories[i])
            max_values.append(max_val)
    
    max_values.sort(reverse=True)
    total = sum(max_values)
    print(total)

if __name__ == "__main__":
    main()

---

この解説は deepseekv3 によって生成されました。