概要

各カテゴリから最大1つまで企画を選べるとき、集客見込み数の合計を最大化する問題です。結論として「各カテゴリで最も大きい \(D_i\) を1つ選んで足す」だけで最適になります。

考察

重要な条件は「各カテゴリから採用できる企画は最大1つ」「カテゴリが重複してはいけない」の2点です。
このとき、カテゴリ同士は互いに影響しません。なぜなら、カテゴリ \(c\) から何を選ぶかは「カテゴリ \(c\) の中の企画」だけで決まり、他カテゴリの選択と競合しないからです（カテゴリが違えば同時に採用できる）。

したがって、各カテゴリごとに次のことが言えます。

• カテゴリ \(c\) に属する企画の中から1つ選ぶなら、集客見込み数 \(D\) が最大の企画を選ぶのが常に最適
• そもそもカテゴリ \(c\) に企画が無ければ \(0\) とみなせばよい（何も採用しない）

例：
\(K=3\) で、企画が
- カテゴリ1: \(D=10, 30\)
- カテゴリ2: \(D=5\)
- カテゴリ3: （なし）
なら、最適は \(30 + 5 + 0 = 35\) です。

素朴に「採用する企画の組合せ」を全探索すると、最大で \(2^N\) 通りになり \(N \le 2\times 10^5\) では到底間に合いません。
しかし上の観察により、全体最適が「カテゴリごとの最大値の総和」に分解でき、1回の走査で解けます。

アルゴリズム

1. 長さ \(K\) の配列 best を用意し、best[c] を「カテゴリ \(c\) で見た最大の \(D\)」として管理する（初期値は \(0\)）。
2. 各企画 \((B_i, D_i)\) を読み込み、best[B_i] = max(best[B_i], D_i) で更新する。
3. 最後に \(\sum_{c=1}^{K} best[c]\) を出力する。
   企画が存在しないカテゴリは best[c]=0 のままなので自然に無視されます。

計算量

• 時間計算量: \(O(N + K)\)（更新が \(N\) 回、最後の総和が \(K\) 要素）
• 空間計算量: \(O(K)\)（カテゴリごとの最大値を保持）

実装のポイント

• \(D_i\) は最大 \(10^9\)、\(K\) も大きいので合計は最大で \(K \times 10^9\) 程度になり得ますが、Python の int ならオーバーフローしません。

• 高速入出力のために sys.stdin.buffer.readline を使うと安全です。

• best を K+1 サイズにして 1-indexed（カテゴリが \(1 \sim K\)）で扱うと実装が簡単です。

  ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline
    N, K = map(int, input().split())
    best = [0] * (K + 1)
    for _ in range(N):
        b, d = map(int, input().split())
        if d > best[b]:
            best[b] = d
    print(sum(best))

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。