概要

各日に購入可能な食材の中から、野菜と肉をそれぞれ1種類以上選んだときの、合計価格の最小値を求めよ。条件を満たす組み合わせが存在しない場合は \(-1\) を出力せよ。

考察

この問題では、各日ごとに「その日に買える食材」が制限されている中で、「野菜1種類＋肉1種類」の合計2種類を選ぶ必要があります。そして、その合計価格を最小化するのが目的です。

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

素朴には、毎日「使える食材リスト」から全ペアを試す方法が考えられますが、これは最大で \(O(K_j^2)\) かかり、最悪ケースで \(K_j\) が \(N\) に近づくと非常に遅くなります（全体で \(O(MN^2)\) などになり得る）。これでは制約 \(N, M \sim 2 \times 10^5\) に対応できません。

また、毎日ソートして最小の野菜と肉を探す方法も考えられますが、これも日数が多いと非効率です。

解決策：前処理と最小値の保持

重要な観察は、「どの日でも最終的に必要なのは、その日に使える食材の中での最小の野菜価格と最小の肉価格」だけだということです。

したがって、各食材を最初に分類しておき（野菜か肉か）、毎日の処理では「使える食材リスト」を走査しながら、その中での最小の野菜価格と肉価格を更新すれば十分です。

アルゴリズム

1. 最初に、全食材の価格と種類を読み込みます。
2. 各日について以下を行います：
   • その日に購入可能な食材番号をセットで管理します。
   • セット内の各食材を見て、種類（野菜 or 肉）に応じて価格の最小値を更新します。
   • 最後に、両方の最小値が見つかれば合計を、そうでなければ \(-1\) を記録します。
3. 全結果を出力します。

この方法では、各日について「使える食材数 \(K_j\)」に対して線形時間で処理できます。

計算量

• 時間計算量: \(O(N + \sum_{j=1}^{M} K_j)\)
  （各食材の読み込みが \(O(N)\)、各日で使える食材を走査するのが \(O(\sum K_j)\)）
• 空間計算量: \(O(N + \max K_j)\)
  （食材情報を保存する配列と、各日の利用可能食材を保持するセット）

実装のポイント

• 入力を高速に読み込むために sys.stdin.read を使用しています。

• 各食材の種類（\(T_i\)）が 0（野菜）または 1（肉）なので、リストや配列で簡単に分類できます。

• 各日で「使える食材」は重複がないため、set で管理することで探索を高速化できます。

• 最小値の初期化には float('inf') を使うのが一般的で安全です。

  ソースコード

import sys
import heapq
from collections import defaultdict

input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    
    # 食材の価格と種類を読み込む
    prices = [0] * (N + 1)
    types = [0] * (N + 1)
    
    for i in range(1, N + 1):
        prices[i] = int(data[idx])
        idx += 1
        types[i] = int(data[idx])
        idx += 1
    
    # 野菜と肉類の最小価格を保持するリスト
    veg_heap = []   # (price, id)
    meat_heap = []  # (price, id)
    
    # 全食材に対して最小ヒープを構築
    for i in range(1, N + 1):
        if types[i] == 0:
            heapq.heappush(veg_heap, (prices[i], i))
        else:
            heapq.heappush(meat_heap, (prices[i], i))
    
    # 各日について処理
    results = []
    for _ in range(M):
        K = int(data[idx])
        idx += 1
        available = set()
        for __ in range(K):
            s = int(data[idx])
            idx += 1
            available.add(s)
        
        # 利用可能な食材の中で最小の野菜と肉を求める
        min_veg = float('inf')
        min_meat = float('inf')
        
        for item_id in available:
            if types[item_id] == 0:
                if prices[item_id] < min_veg:
                    min_veg = prices[item_id]
            else:
                if prices[item_id] < min_meat:
                    min_meat = prices[item_id]
        
        if min_veg == float('inf') or min_meat == float('inf'):
            results.append("-1")
        else:
            results.append(str(min_veg + min_meat))
    
    print("\n".join(results))

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。