概要

各ショッピングモールを「訪れたときの純利益（店の得の合計 − 交通費）」にまとめ、純利益が大きいモールを上位 \(K\) 個まで選んだときの合計を最大化する問題です。

考察

重要な気づき

• モール \(i\) を訪れると、同じモール内では好きな店を好きな数だけ選べます（0店舗も可）。
• しかし制約より \(P_{i,j} \ge 1\) なので、訪れるなら得のある店は全部買うのが最適です。
  途中で買わない理由がありません（買うと必ず総得額が増えるため）。

よって、モール \(i\) を訪れたときの総得額への寄与は - 店の得の合計 \(S_i = \sum_{j=1}^{M_i} P_{i,j}\) - 交通費 \(C_i\) として、純利益
$\( \text{net}_i = S_i - C_i \)$ で表せます。

「訪れない」選択の扱い

• もし \(\text{net}_i \le 0\) なら、そのモールは訪れても得になりません（訪れない方が良い）。
• よって「訪れる候補」は \(\text{net}_i > 0\) のモールだけで十分です。

問題の言い換え

• 正の値の配列 \(\text{net}_i\)（モールごとの純利益）から、高々 \(K\) 個選んで合計を最大化せよ。

これは結局、 - 純利益が大きい順に最大 \(K\) 個取る のが最適です。

素朴な方法が危ない点

• 全モールの \(\text{net}_i\) を配列に入れてソートする方法は \(O(N \log N)\) で、この制約でも間に合うことが多いですが、
  • 余計なメモリを使う
  • 入力が最大 \(10^5\) 個の店舗情報を含み I/O が重い
    といった理由で実装次第では遅くなりがちです。
• そこで、「上位 \(K\) 個だけ」を管理するヒープを使うと、常に必要な分だけ保持でき、効率的です。

（例） - \(K=2\)、純利益が \([5, 1, 7, 3]\) なら上位2つは \(7\) と \(5\) で答えは \(12\)。

アルゴリズム

1. 各モール \(i\) について、店のお得度をすべて足して \(S_i\) を作る。
2. \(\text{net}_i = S_i - C_i\) を計算する。
3. \(\text{net}_i > 0\) のときだけ、サイズ最大 \(K\) の 最小ヒープに入れて「上位 \(K\) 個」を保つ。
   • ヒープの要素数が \(K\) 未満なら push
   • すでに \(K\) 個あるなら、ヒープ最小値（上位集合の中で最も小さい値）より大きいときだけ入れ替える
4. 最後にヒープ内の合計が答え（訪れるモールの純利益合計の最大値）。

最小ヒープを使う理由： - 「上位 \(K\) 個」を管理するとき、いちばん捨てたいのはその集合の最小要素 - 最小ヒープなら最小要素がすぐ取り出せる（\(O(1)\) で参照、入れ替えは \(O(\log K)\)）

計算量

• 時間計算量:
  店舗情報の総数を \(T=\sum M_i\) とすると、各店舗を1回読むので \(O(T)\)、ヒープ操作が各モールにつき最大1回で \(O(N \log K)\)。
  よって全体で
  $\(O(T + N \log K)\)$
• 空間計算量:
  ヒープが最大 \(K\) 個だけ保持するので
  $\(O(K)\)$

実装のポイント

• 訪れるなら全店舗を買う（\(P_{i,j} \ge 1\) が効いている）ため、モールごとの情報は「合計 \(S_i\)」だけ計算すれば十分です。

• \(\text{net}_i \le 0\) は答えを悪化させるだけなので無視してよいです。

• 入力サイズが大きいので、コードでは sys.stdin.buffer.read() を使った高速な整数パーサ（int_reader）で I/O を高速化しています。

• Pythonのヒープは heapq（最小ヒープ）を使い、サイズを \(K\) に保つことで無駄な保持やソートを避けています。

  ソースコード

import sys
import heapq

def int_reader():
    data = sys.stdin.buffer.read()
    num = 0
    sign = 1
    in_num = False
    for b in data:
        if 48 <= b <= 57:
            num = num * 10 + (b - 48)
            in_num = True
        else:
            if in_num:
                yield sign * num
                num = 0
                sign = 1
                in_num = False
            elif b == 45:  # '-'
                sign = -1
    if in_num:
        yield sign * num

def main():
    it = int_reader()
    N = next(it)
    K = next(it)

    heap = []  # min-heap for top-K positive net profits

    for _ in range(N):
        C = next(it)
        M = next(it)
        s = 0
        for _ in range(M):
            s += next(it)
        net = s - C
        if net > 0:
            if len(heap) < K:
                heapq.heappush(heap, net)
            elif net > heap[0]:
                heapq.heapreplace(heap, net)

    print(sum(heap))

if __name__ == "__main__":
    main()

---

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