概要

各日について、購入可能な食材の中から最も安い野菜と最も安い肉類を1つずつ選び、その合計価格を求める問題です。

考察

重要な気づき

この問題では「野菜を1種類、肉類を1種類」選ぶ必要があります。価格の合計を最小化したいので、それぞれのカテゴリから最も安いものを1つずつ選べばよいことがわかります。

なぜ単純な方法で十分か

一見すると、全ての野菜と肉類の組み合わせを試す必要があるように思えます。しかし、野菜同士は互いに独立で、肉類同士も互いに独立です。つまり：

• 野菜の選び方は、選んだ肉類に影響しない
• 肉類の選び方は、選んだ野菜に影響しない

したがって、野菜の中で最小価格のものと肉類の中で最小価格のものを別々に求め、それらを足し合わせれば答えになります。

具体例

例えば、ある日に以下の食材が購入可能だとします： - 野菜A（100円）、野菜B（150円） - 肉C（200円）、肉D（180円）

全組み合わせを考えると： - A+C = 300円、A+D = 280円 - B+C = 350円、B+D = 330円

最小は280円ですが、これは最安の野菜A（100円）と最安の肉D（180円）の組み合わせです。

アルゴリズム

1. 各食材の価格 \(P_i\) と種類 \(T_i\) を読み込み、配列に保存する
2. 各日 \(j\) について以下を行う：
   • その日購入可能な食材リストを読み込む
   • 購入可能な食材を1つずつ確認し、野菜（\(T=0\)）の最小価格と肉類（\(T=1\)）の最小価格をそれぞれ求める
   • 両方のカテゴリに少なくとも1つずつ食材があれば、2つの最小価格の和を出力
   • どちらかのカテゴリに食材がなければ \(-1\) を出力

計算量

• 時間計算量: \(O(N + \sum_{j=1}^{M} K_j)\)

  • 食材情報の読み込みに \(O(N)\)
  • 各日の処理で、購入可能な食材を1回ずつ見るので、全日数の合計は \(O(\sum K_j)\)
  • 制約より \(\sum K_j \leq 2 \times 10^5\) なので十分高速

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

  • 食材の価格・種類を保存する配列に \(O(N)\)
  • 結果を保存する配列に \(O(M)\)

実装のポイント

1. 無限大の初期値: 最小値を求める際、初期値を float('inf') にしておくと、食材が存在しない場合の判定が容易になります。

2. 1-indexed の扱い: 食材番号が1から始まるため、配列サイズを \(N+1\) にして添字をそのまま使うと実装が楽です。

3. 出力の効率化: 各日の結果を毎回 print するのではなく、リストに溜めて最後にまとめて出力することで、I/O のオーバーヘッドを減らせます。

4. 入力の高速化: sys.stdin.readline を使うことで、大量の入力がある場合でも高速に読み込めます。

   ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    
    prices = [0] * (N + 1)
    types = [0] * (N + 1)
    
    for i in range(1, N + 1):
        P, T = map(int, input().split())
        prices[i] = P
        types[i] = T
    
    results = []
    
    for _ in range(M):
        line = list(map(int, input().split()))
        K = line[0]
        items = line[1:K+1]
        
        # Find minimum price for meat (T=1) and vegetable (T=0)
        min_meat = float('inf')
        min_veg = float('inf')
        
        for item in items:
            if types[item] == 1:  # meat
                if prices[item] < min_meat:
                    min_meat = prices[item]
            else:  # vegetable
                if prices[item] < min_veg:
                    min_veg = prices[item]
        
        if min_meat == float('inf') or min_veg == float('inf'):
            results.append(-1)
        else:
            results.append(min_meat + min_veg)
    
    print('\n'.join(map(str, results)))

if __name__ == "__main__":
    main()

---

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