概要

\(N\) 個の商品それぞれについて、そのカテゴリを扱うお店の中で最も安いお店を選び、合計費用を最小化する問題です。取り扱いのないカテゴリがあれば -1 を出力します。

考察

重要な気づき

各商品は独立に購入先を選べるため、商品ごとに最も安いお店で買えばよいというのがポイントです。

例えば、カテゴリ \(3\) の商品が \(4\) 個あり、カテゴリ \(3\) を扱うお店が「100円の店」と「150円の店」の2つある場合、4個すべてを100円の店で買うのが最安です。

つまり、同じカテゴリの商品は必ず同じ最安のお店で買うのが最適です。

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

もし各商品について、\(M\) 個のお店をすべて探索して最安値を求めると \(O(NM)\) となり、\(N, M\) が最大 \(2 \times 10^5\) の場合 \(4 \times 10^{10}\) 回の操作が必要で TLE になります。

解決方法

事前にカテゴリごとの最安値を辞書（ハッシュマップ）にまとめておけば、各商品の最安値を \(O(1)\) で引けるようになります。

アルゴリズム

1. 前処理: \(M\) 個のお店の情報を読み込み、カテゴリ \(S_j\) をキー、最小価格を値とする辞書 min_cost を構築する。同じカテゴリのお店が複数あれば、最も安い価格だけを保持する。

2. 合計計算: \(N\) 個の商品それぞれについて、カテゴリ \(T_i\) が min_cost に存在するか確認する。

   • 存在しなければ、その商品は購入不可能なので -1 を出力して終了。
   • 存在すれば、min_cost[T_i] を合計に加算する。

3. 出力: すべての商品が購入可能であれば、合計費用を出力する。

具体例

N=3, M=3
商品のカテゴリ: [1, 2, 1]
お店: (カテゴリ1, 100円), (カテゴリ2, 200円), (カテゴリ1, 80円)

• 前処理: min_cost = {1: 80, 2: 200}（カテゴリ1は80円と100円のうち80円を採用）
• 商品1（カテゴリ1）→ 80円
• 商品2（カテゴリ2）→ 200円
• 商品3（カテゴリ1）→ 80円
• 合計: \(80 + 200 + 80 = 360\) 円

計算量

• 時間計算量: \(O(N + M)\)
  • お店の情報を読み込み辞書を構築するのに \(O(M)\)、各商品の最安値を参照するのに \(O(N)\)（辞書の参照は平均 \(O(1)\)）
• 空間計算量: \(O(N + M)\)
  • 商品リストに \(O(N)\)、カテゴリごとの最安値辞書に \(O(M)\)

実装のポイント

• 辞書によるカテゴリ別最安値の管理: カテゴリの値が最大 \(10^9\) と大きいため、配列ではなく辞書（Pythonの dict）を使う必要があります。

• オーバーフローに注意: \(N\) と \(C_j\) がともに最大 \(2 \times 10^5\) と \(10^9\) なので、合計は最大 \(2 \times 10^{14}\) に達します。Pythonでは整数のオーバーフローは起きませんが、C++ などでは long long を使う必要があります。

• 高速入力: \(N, M\) が大きいため、sys.stdin.buffer.read() でまとめて読み込むことで入力を高速化しています。

  ソースコード

import sys
from collections import defaultdict

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    T = []
    for i in range(N):
        T.append(int(input_data[idx])); idx += 1
    
    # For each category, find the minimum cost among all shops selling that category
    min_cost = {}
    for j in range(M):
        s = int(input_data[idx]); idx += 1
        c = int(input_data[idx]); idx += 1
        if s not in min_cost or c < min_cost[s]:
            min_cost[s] = c
    
    total = 0
    for t in T:
        if t not in min_cost:
            print(-1)
            return
        total += min_cost[t]
    
    print(total)

main()

---

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