概要

この問題は、各商品のカテゴリに対応する最安値のお店を見つけ、全ての商品を購入できるかどうかを判定し、可能なら最小総費用を求める問題です。

考察

重要な観察点は以下の通りです： - 同じカテゴリの商品は、そのカテゴリを取り扱うお店の中で最も安い価格で購入するのが最適です - もし1つでもカテゴリに対応するお店が存在しない商品があれば、全ての商品を購入することは不可能です - 素朴なアプローチとして、各商品ごとに全てのお店を調べて最安値を探すと、計算量が \(O(N \times M)\) となり、制約条件（\(N, M \leq 2 \times 10^5\)）では最大 \(4 \times 10^{10}\) 回の操作が必要になるため、時間制限に間に合いません

アルゴリズム

1. 前処理: 全てのお店の情報を走査し、各カテゴリごとの最安価格を辞書に記録します
2. チェック: 買い物リストの各商品カテゴリが辞書に存在するか確認します。1つでも存在しないカテゴリがあれば -1 を出力します
3. 計算: 全てのカテゴリが存在する場合、各商品の最安価格を合計して総費用を計算します

計算量

• 時間計算量: \(O(N + M)\)
  • お店の情報を処理するのに \(O(M)\)
  • 商品リストを処理するのに \(O(N)\)
• 空間計算量: \(O(K)\)（\(K\) は異なるカテゴリの数）
  • 最安価格を記録する辞書のサイズ

実装のポイント

• defaultdict を使用して、存在しないキーへのアクセスを float('inf') で初期化することで、後で存在チェックが簡単になります

• 入力データのパース時に、インデックス管理を正確に行う必要があります

• お店の情報を処理する際、同じカテゴリが出てくるたびに最小価格を更新します

• 早期リターン: 不可能なカテゴリが見つかった時点で即座に -1 を出力して処理を終了します

  ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    if not data:
        print(-1)
        return
        
    n = int(data[0])
    m = int(data[1])
    T = list(map(int, data[2:2+n]))
    shops = []
    index = 2 + n
    for i in range(m):
        s = int(data[index])
        c = int(data[index+1])
        index += 2
        shops.append((s, c))
        
    from collections import defaultdict
    category_min_price = defaultdict(lambda: float('inf'))
    
    for s, c in shops:
        if c < category_min_price[s]:
            category_min_price[s] = c
            
    total = 0
    for t in T:
        if t not in category_min_price:
            print(-1)
            return
        total += category_min_price[t]
        
    print(total)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。