概要

\(N\) 個のショッピングモールの中から最大 \(K\) 個を選び、「選んだモール内の店舗で得られるお得度の合計」から「交通費・駐車料金」を引いた値（純利益）を最大化する問題です。

考察

この問題を解くためのポイントは、以下の3点に集約されます。

1. 各モールでどの店舗を回るべきか 制約を見ると、各店舗のお得度 \(P_{i,j}\) は必ず \(1\) 以上です。そのため、あるモール \(i\) に立ち寄ることを決めた場合、そのモール内にあるすべての店舗で買い物をすることが、そのモールから得られる利益を最大化する最善の戦略となります。 したがって、モール \(i\) を訪れた際に得られる利益（純利益）は次のように計算できます。 $\(\text{（純利益）}_i = \left( \sum_{j=1}^{M_i} P_{i,j} \right) - C_i\)$

2. どのモールを訪れるべきか 各モールについて計算した「純利益」が正（\(0\) より大きい）であるものだけが、訪れる価値のある候補となります。純利益が負のモールは、訪れると総得額が減ってしまうため、無視して構いません。

3. 最大 \(K\) 個という制約をどう扱うか 訪れることができるモールは最大 \(K\) 個です。したがって、先ほど計算した「正の純利益」のうち、値が大きいものから順に最大 \(K\) 個選んで合計すれば、それが答えとなります。もし正の純利益が得られるモールが \(K\) 個未満であれば、それらすべてを訪れるのが最適です。

アルゴリズム

1. 各モール \(i = 1, 2, \ldots, N\) について、以下の処理を行います。
   • モール内の全店舗のお得度の総和 \(S_i = \sum P_{i,j}\) を計算する。
   • 純利益 \(X_i = S_i - C_i\) を計算する。
   • \(X_i > 0\) であれば、リスト（またはヒープ）に \(X_i\) を追加する。
2. 保存した純利益のリストを降順（大きい順）に並べ替えます。
3. リストの先頭から最大 \(K\) 個を取り出し、その合計を出力します。

計算量

• 時間計算量: \(O(\sum M_i + N \log K)\)
  • 全店舗のお得度を読み込むのに \(O(\sum M_i)\) かかります。
  • \(N\) 個の要素から上位 \(K\) 個を取り出す操作は、ソートを用いると \(O(N \log N)\)、ヒープを用いると \(O(N \log K)\) となります。
• 空間計算量: \(O(N)\)
  • 各モールの純利益を保持するために最大 \(N\) 個分のメモリを使用します。

実装のポイント

• 大量の入力データ: \(N\) や \(\sum M_i\) が \(10^5\) と大きいため、Pythonでは sys.stdin を使った高速な読み込みが推奨されます。

• メモリ効率: コード例ではジェネレータ（yield）や itertools.islice を活用することで、大量のデータを一度にリスト化せず、メモリ消費を抑えつつ効率的に処理しています。

• 上位 \(K\) 個の取得: heapq.nlargest(k, list) を使うと、リスト全体を完全にソートするよりも効率的に上位 \(K\) 個を取得できる場合があります。

  ソースコード

import sys
import heapq
from itertools import islice

def solve():
    # Use a generator to fetch tokens from standard input one by one.
    # This approach is memory-efficient and differs from loading all data into a list.
    def token_stream():
        for line in sys.stdin:
            for word in line.split():
                yield int(word)

    tokens = token_stream()

    # Read the number of malls (N) and the maximum number of malls to visit (K)
    try:
        n = next(tokens)
        k = next(tokens)
    except StopIteration:
        return

    def get_mall_net_profits():
        # Iterate through the N malls provided in the input
        for _ in range(n):
            # Each mall starts with its cost (C_i) and number of shops (M_i)
            cost = next(tokens)
            m_i = next(tokens)
            
            # Sum up the benefits (P_i,j) of all shops in this mall.
            # islice(tokens, m_i) takes exactly the next m_i shop values from the generator.
            # Since shop benefits are at least 1, we always include all shops if we visit the mall.
            mall_benefit = sum(islice(tokens, m_i))
            
            # The net profit for visiting this mall is the benefit minus the travel/parking cost.
            net_profit = mall_benefit - cost
            
            # We only consider malls that result in a positive net profit.
            if net_profit > 0:
                yield net_profit

    # heapq.nlargest(k, ...) efficiently finds the k largest items from the generator.
    # This is an O(N log K) operation, providing a different approach to sorting the entire list.
    # If fewer than k positive profits exist, it correctly returns all of them.
    top_profits = heapq.nlargest(k, get_mall_net_profits())
    
    # The total maximum profit is the sum of these top-performing malls.
    # If no malls are profitable, the sum will naturally be 0.
    print(sum(top_profits))

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-preview によって生成されました。