概要

\(N\) 個のショッピングモールがあり、それぞれに複数の店舗があります。各店舗では買い物をすることで「お得度」が得られ、モールに訪れるには交通費がかかります。最大 \(K\) 個のモールに訪問できるとき、得られる「総得額（お得度の合計 − 交通費の合計）」の最大値を求めます。

考察

この問題では、「どのモールに行くか」「そのモールでどの店舗から買い物をするか」がポイントになります。

各モールでの戦略

各ショッピングモールについて、以下のように考えます： - そのモールに訪れるかどうかを決めます（訪問しない場合は利益もコストもなし）。 - 訪れるなら、そのモールにあるすべての店舗の中から「お得度が正のもの」だけを選ぶのが最適です（負のお得度の商品は買わなければいい）。 - このときの「純利益」は、
$\( \text{純利益} = \left(\sum_{j=1}^{M_i} \max(0, P_{i,j})\right) - C_i \)$
となります。

訪問するモールの選び方

次に、どのモールに訪問するかですが、最大で \(K\) 個まで選べます。そして、訪問するモールは「純利益が大きい上位 \(K\) 個（ただし非負のものに限る）」を選ぶのが最適です。

なぜなら、純利益が負のモールに訪問しても損をするだけで得をしないため、訪問すべきではありません。また、利益が大きい順に \(K\) 個選べば、全体の利益が最大になります。

たとえば、以下の例を見てみましょう。

具体例

入力：

3 2
10 3 5 6 7
5 2 3 4
8 2 1 2

各モールのお得度の合計と交通費から純利益を計算します： - モール1: \((5+6+7) - 10 = 8\) - モール2: \((3+4) - 5 = 2\) - モール3: \((1+2) - 8 = -5\)

この中で、純利益が非負のものはモール1（8）とモール2（2）です。上位2つなので、両方訪問するのが最適で、合計利益は \(8 + 2 = 10\) です。

もし負の利益のモール3を選んだり、より少ない個数を選んでも利益が増えないので、このように選ぶのが最適です。

アルゴリズム

1. 各モールについて、そのモール内のお得度のうち正のものをすべて足し合わせ、そこから交通費を引いて「純利益」を計算します。
2. すべてのモールの「純利益」をリストにまとめ、降順にソートします。
3. 上位 \(K\) 個のうち、正のものだけを合計して答えとします（負のものは無視）。

計算量

• 時間計算量: \(O\left(\sum_{i=1}^{N} M_i \log M_i + N \log N\right)\)
  • 各モール内で商品のお得度をソートするのに \(O(M_i \log M_i)\)
  • 最後に純利益のリストをソートするのに \(O(N \log N)\)
• 空間計算量: \(O(N + \sum M_i)\)

実装のポイント

• 各モールの純利益は「正のお得度の合計 − 交通費」で求めること。

• 非負の純利益だけを上位 \(K\) 個選ぶことを忘れないこと。

• 入力を高速に読み込むために sys.stdin.read を使うとよい（特に \(N\) が大きいケースに対応できる）。

  ソースコード

import sys
import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx])
    idx += 1
    K = int(data[idx])
    idx += 1
    
    malls = []
    for _ in range(N):
        C = int(data[idx])
        idx += 1
        M = int(data[idx])
        idx += 1
        P = []
        for _ in range(M):
            p = int(data[idx])
            idx += 1
            P.append(p)
        # 各モールで得られる純利益（お得度の合計 - 交通費）を計算
        profit = sum(P) - C
        # お得度を降順にソートして、先頭から選べるようにする
        P.sort(reverse=True)
        malls.append((profit, P, C))
    
    # 各モールのお得度の累積和を前計算
    cum_profits = []
    for profit, P, C in malls:
        cum = [0]
        for p in P:
            cum.append(cum[-1] + p)
        cum_profits.append((cum, C))
    
    # 各モールの純利益でソート（降順）
    # 各要素: (純利益, cum配列, 交通費C)
    sorted_malls = []
    for i in range(N):
        profit, P, C = malls[i]
        cum, _ = cum_profits[i]
        sorted_malls.append((profit, cum, C))
    
    sorted_malls.sort(reverse=True)
    
    max_total = 0
    # 訪れるモールの数 k を 0 から K まで試す
    # ただし、k個のモールを選ぶときに、純利益が高い上位k個を選ぶのが最適
    # しかし、純利益=sum(P)-C なので、単純にこれでソートしても最適ではない可能性がある
    # 実際には、選ぶモールの組み合わせと、各モールで買う商品の数を考慮する必要がある
    
    # より正確には、各モールについて「訪問する場合の最大利益」を計算し、
    # それを基に上位K個を選ぶのが良い
    
    # 各モールの利益を「そのモールに訪問したとき得られる最大利益」として定義
    # それは、そのモール内の商品をいくつか選んで買うことで最大化される
    # つまり、各商品のお得度が正なら買うべき。負なら買わない
    
    # 各モールの「純利益」を再定義：そのモールに訪問したときに得られる最大利益（非負）
    profits = []
    for _, P, C in malls:
        gain = sum(max(0, p) for p in P)
        net_profit = gain - C
        profits.append(net_profit)
    
    # 上位K個の非負の利益を選ぶ
    profits.sort(reverse=True)
    current_sum = 0
    for i in range(K):
        if profits[i] > 0:
            current_sum += profits[i]
        else:
            break
    max_total = current_sum
    
    print(max_total)

if __name__ == "__main__":
    main()

---

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