概要

\(K\) 種類のカテゴリそれぞれから最大1つの企画を採用できるとき、集客の見込み数の合計を最大化する問題です。各カテゴリで最も集客見込みが大きい企画を選べばよい、という貪欲法で解けます。

考察

重要な気づき

各カテゴリから採用できる企画は 最大1つ です。つまり、カテゴリごとに独立に「どの企画を採用するか（または採用しないか）」を決められます。

あるカテゴリに複数の企画が属している場合、合計を最大化するには当然 そのカテゴリ内で集客見込み数 \(D_i\) が最大の企画 を選ぶのが最適です。集客見込み数は \(D_i \geq 1\) と正の値なので、企画が存在するカテゴリでは必ず1つ採用した方が得です。

具体例

例えば、\(K = 3\) で以下の企画があるとします：

企画	カテゴリ \(B_i\)	集客見込み \(D_i\)
1	1	100
2	1	200
3	2	150
4	3	300

• カテゴリ1：企画1（100）と企画2（200）→ 200 を選択
• カテゴリ2：企画3（150）→ 150 を選択
• カテゴリ3：企画4（300）→ 300 を選択

合計：\(200 + 150 + 300 = 650\)

素朴なアプローチとの比較

全ての企画の採用/不採用の組み合わせを試すと \(2^N\) 通りとなり、\(N\) が最大 \(2 \times 10^5\) では到底間に合いません。しかし、上記の考察から「各カテゴリの最大値を取るだけ」と分かるので、\(N\) 個の企画を1回走査するだけで十分です。

アルゴリズム

1. カテゴリごとに、そのカテゴリに属する企画の中での \(D_i\) の最大値を管理する辞書（連想配列）best を用意する。
2. \(N\) 個の企画を順に見て、カテゴリ \(B_i\) に対して best[B_i] を \(D_i\) と比較し、大きければ更新する。
3. best の全ての値の合計が答え。

これは典型的な 貪欲法（Greedy） です。カテゴリ間の選択が互いに独立であるため、各カテゴリで局所最適な選択がそのまま全体最適になります。

計算量

• 時間計算量: \(O(N)\) — 全企画を1回走査し、各企画について辞書への参照・更新は \(O(1)\)（平均）
• 空間計算量: \(O(K)\) — カテゴリごとの最大値を保持する辞書のサイズ（最大 \(K\) エントリ）

実装のポイント

• defaultdict(int) を使うことで、まだ登場していないカテゴリの初期値を \(0\) にできます。\(D_i \geq 1\) なので、初期値 \(0\) と比較すれば最初の企画は必ず採用候補になります。

• sys.stdin.buffer.read() で入力を一括読み込みし、split() で分割することで、\(N\) が大きい場合でも高速に入力を処理できます。これは Python で競技プログラミングを行う際の定番テクニックです。

• 集客見込み数が最大 \(10^9\) で、カテゴリ数が最大 \(2 \times 10^5\) なので、合計は最大約 \(2 \times 10^{14}\) になりえます。Python は整数のオーバーフローがないため、特別な対処は不要です。

  ソースコード

import sys
from collections import defaultdict

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    best = defaultdict(int)
    for i in range(N):
        b = int(input_data[idx]); idx += 1
        d = int(input_data[idx]); idx += 1
        if d > best[b]:
            best[b] = d
    
    print(sum(best.values()))

main()

---

この解説は claude4.6opus-thinking によって生成されました。