概要

各カテゴリから高々1つの企画を選ぶことができるとき、選んだ企画の集客見込み数の合計を最大化する問題。

考察

この問題では、各カテゴリにつき高々1つの企画しか選べません。つまり、同じカテゴリに複数の企画があっても、その中から最も集客見込み数が多いものを1つだけ選ぶのが最適です。

たとえば、カテゴリ1に集客見込み数が3と5の2つの企画がある場合、カテゴリ1からは5の方を選ぶべきです。他のカテゴリについても同様に、各カテゴリ内で最大の集客数を持つ企画を選ぶのが最適戦略です。

したがって、各カテゴリに対して最も大きい \(D_i\) を記録しておき、それらの和を求めればよいです。素朴な方法として、全企画を走査しながらカテゴリごとに最大値を更新していく方法があります。これは効率的であり、特に工夫なしでも間に合います。

アルゴリズム

1. 各カテゴリに対応する最大の集客見込み数を記録するための辞書（または配列）を用意する。
2. 全企画を読み込みながら、それぞれの企画が属するカテゴリに対応する最大値を更新する。
3. 最後に、すべてのカテゴリの最大値の合計を取る。

このようにして、各カテゴリからの選択を最適に行い、全体の合計を最大化できます。

計算量

• 時間計算量: \(O(N)\)
  （各企画を1回ずつ処理するため）
• 空間計算量: \(O(K)\)
  （カテゴリ数分の情報を保持するため）

実装のポイント

• カテゴリ番号は1-indexedなので、配列を使う場合は注意が必要ですが、辞書を使えば気にしなくてよい。

• 高速化のため、sys.stdin.read を使って一度に標準入力を読み込むと良い。

• 各カテゴリの最大値を管理する際に、すでに値があるかどうかを毎回確認せずとも、単純に比較して更新すれば十分。

  ソースコード

import sys
from collections import defaultdict

input = sys.stdin.read
data = input().split()

N = int(data[0])
K = int(data[1])

# カテゴリごとの最大集客数を保持する辞書
category_max = defaultdict(int)

index = 2
for _ in range(N):
    B = int(data[index])
    D = int(data[index+1])
    index += 2
    if D > category_max[B]:
        category_max[B] = D

# 各カテゴリから最大1つ選べるので、カテゴリごとの最大値の和が答え
result = sum(category_max.values())
print(result)

---

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