概要

各カテゴリごとに「必要個数」と「そのカテゴリを最安で買える店の単価」を突き合わせ、すべて揃うなら合計最小費用を計算し、揃わないカテゴリがあれば -1 を出力する問題です。

考察

重要な観察は次の2点です。

1. カテゴリごとに独立に最適化できる
   商品同士・カテゴリ同士で制約の絡み合いがありません。
   あるカテゴリ \(x\) の商品は、カテゴリ \(x\) を扱う店でしか買えず、しかも各店は何個でも売れるので、結局カテゴリ \(x\) の商品は 「そのカテゴリを扱う店の中で最安単価の店」で全部買う のが最適です。

2. 必要なのは「各カテゴリの個数」と「各カテゴリの最小単価」だけ

   • 商品側：カテゴリ \(T_i\) の出現回数（必要個数）
     
   • 店側：カテゴリ \(S_j\) の最小価格
     これらが分かれば、答えは
     $\( \sum_{\text{カテゴリ } c} (\text{必要個数 } \mathrm{cnt}[c]) \times (\text{最小単価 } \mathrm{minPrice}[c]) \)\( で求まります。ただし、必要なカテゴリ \)c\( に対して \)\mathrm{minPrice}[c]$ が存在しない（扱う店がない）なら購入不可能で -1 です。

素朴に「各商品ごとに全店舗を見て最安を探す」と、最悪で \(N \times M = 4 \times 10^{10}\) 回程度の比較になり、確実にTLEになります。
そこで、先に店舗情報からカテゴリごとの最小単価をまとめておき、その後にカテゴリごとの必要個数と掛け算することで \(O(N+M)\) 程度に落とします。

具体例： - 商品カテゴリ：[1, 1, 3] → 必要個数：カテゴリ1が2個、カテゴリ3が1個 - 店：(1, 100), (1, 80), (2, 50) → 最小単価：カテゴリ1は80、カテゴリ2は50
このときカテゴリ3を扱う店がないので、答えは -1 になります。

アルゴリズム

1. 商品カテゴリ列 \(T\) を数え上げ、カテゴリごとの必要個数 need[cat] を作る（Counter を利用）。
2. 各店 \((S_j, C_j)\) を読み、カテゴリごとの最小単価 min_price[cat] を更新する（min を取る）。
3. need に含まれる各カテゴリ cat について：
   • min_price[cat] が存在しなければ -1 を出力して終了。
   • 存在するなら total += need[cat] * min_price[cat]。
4. total を出力。

計算量

• 時間計算量: \(O(N + M)\)（ハッシュ表操作は平均 \(O(1)\) とみなす）
• 空間計算量: \(O(K)\)（\(K\) は登場するカテゴリ種類数、最大で \(N+M\) 程度）

実装のポイント

• カテゴリ値が最大 \(10^9\) なので配列添字にはできません。辞書（dict）や Counter で管理します。

• 同じカテゴリの店が複数あるので、min_price[s] は「見つけた最小値」だけ保持すれば十分です。

• 入力が最大 \(2 \times 10^5\) 行規模なので、sys.stdin.buffer.read() でまとめて読み、速度を確保しています。

  ソースコード

import sys
from collections import Counter

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)

    T = [next(it) for _ in range(N)]
    need = Counter(T)

    min_price = {}
    for _ in range(M):
        s = next(it)
        c = next(it)
        prev = min_price.get(s)
        if prev is None or c < prev:
            min_price[s] = c

    total = 0
    for cat, cnt in need.items():
        price = min_price.get(cat)
        if price is None:
            print(-1)
            return
        total += cnt * price

    print(total)

if __name__ == "__main__":
    main()

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