概要

各ショッピングモールから得られる「純利益」を計算し、純利益が正のモールの中から上位 \(K\) 個を選ぶ貪欲法の問題です。

考察

重要な気づき

1. 各モールは独立に判断できる: あるモールを訪れるかどうかは、他のモールとは独立に判断できます。

2. モール内での最適行動: 一度モールを訪れたら、お得度が正の店舗はすべて回るのが得です。お得度は必ず正（\(P_{i,j} \geq 1\)）なので、実際にはそのモールのすべての店舗で買い物をするのが最適です。

3. モールの「純利益」: モール \(i\) を訪れた場合の純利益は次のように計算できます： $\(\text{純利益}_i = \sum_{j=1}^{M_i} P_{i,j} - C_i\)$

4. 訪れないという選択肢: 純利益が負のモールは訪れない方が得です。また、どのモールにも訪れなければ総得額は \(0\) なので、負の総得額になるくらいなら訪れない方が良いです。

素朴なアプローチの問題点

「\(N\) 個のモールから \(K\) 個を選ぶすべての組み合わせを試す」という方法では、\({N \choose K}\) 通りの組み合わせがあり、\(N = 10^5\) では到底間に合いません。

解決策

各モールの価値（純利益）が独立に計算できることを利用します。純利益が大きいモールから貪欲に選べばよいので、ソートして上位を選ぶだけで解けます。

アルゴリズム

1. 各モールの純利益を計算: モール \(i\) について、全店舗のお得度の合計から交通費 \(C_i\) を引いた値を計算します。

2. 純利益でソート: すべてのモールの純利益を降順（大きい順）にソートします。

3. 貪欲に選択: 純利益が大きい方から最大 \(K\) 個を選びます。ただし、純利益が負になったらそこで選択を止めます（選ばない方が得だから）。

4. 答えを出力: 選んだモールの純利益の合計が答えです。

具体例

例えば、\(N = 3, K = 2\) で以下のモールがあるとします： - モール1: \(C_1 = 100\), 店舗のお得度 \([50, 60]\) → 純利益 = \(110 - 100 = 10\) - モール2: \(C_2 = 200\), 店舗のお得度 \([300]\) → 純利益 = \(300 - 200 = 100\) - モール3: \(C_3 = 500\), 店舗のお得度 \([100, 100]\) → 純利益 = \(200 - 500 = -300\)

純利益の降順: \([100, 10, -300]\)

上位2個で正のものを選ぶ: モール2とモール1 → 総得額 = \(100 + 10 = 110\)

計算量

• 時間計算量: \(O\left(\sum_{i=1}^{N} M_i + N \log N\right)\)

  • 全店舗のお得度を読み込むのに \(O\left(\sum M_i\right)\)
  • \(N\) 個の純利益をソートするのに \(O(N \log N)\)

• 空間計算量: \(O(N)\)

  • 各モールの純利益を保存する配列

実装のポイント

• \(P_{i,j} \geq 1\) という制約があるため、実際にはすべての店舗のお得度が正です。よって「正のお得度だけを足す」という処理は「全部足す」と同じになります。

• 純利益が負のモールは選ばないため、ソート後にループで純利益が \(0\) 以下になったら break して早期終了できます。

• 値が最大 \(10^9\) になり得るので、合計が大きくなる可能性があります。Pythonでは整数のオーバーフローを気にする必要はありませんが、C++などでは long long を使う必要があります。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    # 各モールの「純利益」を計算
    # 純利益 = (正のお得度の合計) - C_i
    profits = []
    
    for i in range(N):
        C = int(input_data[idx]); idx += 1
        M = int(input_data[idx]); idx += 1
        
        total_positive = 0
        for j in range(M):
            P = int(input_data[idx]); idx += 1
            if P > 0:
                total_positive += P
        
        # このモールを訪れた場合の純利益
        net_profit = total_positive - C
        profits.append(net_profit)
    
    # 純利益が正のモールだけを選び、上位K個を選ぶ
    # ただし、純利益が負のモールは選ばない方が得
    profits.sort(reverse=True)
    
    total = 0
    for i in range(min(K, N)):
        if profits[i] > 0:
            total += profits[i]
        else:
            break
    
    print(total)

if __name__ == "__main__":
    main()

---

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