概要

\(N\) 種類の食材（野菜または肉類）から、各日に購入可能なリストが与えられます。各日において「野菜の最小価格」と「肉類の最小価格」をそれぞれ独立に求め、その合計の最小値を計算する問題です。

考察

この問題のポイントは、「各日の最小値は、その日に購入可能な食材だけを調べれば決まる」という点です。

重要な観察

各日において、条件（野菜1つ、肉類1つ）を満たす最小価格を求めるには、以下の2つがわかれば十分です。 1. その日に購入可能な「野菜（タイプ0）」の中での最小価格 2. その日に購入可能な「肉類（タイプ1）」の中での最小価格

これらが両方存在すれば、その和がその日の答えになります。どちらか一方が存在しない場合は、条件を満たせないため \(-1\) を出力します。

効率的な処理

「毎日すべての食材を確認する」と、最悪の場合 \(M \times N\) 回の計算が必要になり、実行時間制限に間に合いません。しかし、問題文の制約を見ると \(\sum K_j \leq 2 \times 10^5\) （全日程の購入可能リストの延べ数）とあります。

これは、各日に指定された食材だけを順番にチェックしていけば、合計の計算回数は \(2 \times 10^5\) 程度に収まることを意味しています。したがって、各日ごとにリストを走査する素直な方法で十分に間に合います。

アルゴリズム

1. 食材データの準備: 各食材の価格 \(P_i\) と種類 \(T_i\) を配列などに格納します。
2. 各日の処理: \(M\) 日分、以下の処理を繰り返します。
   • その日の野菜の最小価格 min_veg と肉類の最小価格 min_meat を、非常に大きな値（無限大）で初期化します。
   • その日に購入可能な食材の番号を1つずつ確認します。
     • 食材が野菜なら、min_veg を現在の食材価格と比較して小さい方で更新します。
     • 食材が肉類なら、min_meat を現在の食材価格と比較して小さい方で更新します。
   • ループ終了後、min_veg と min_meat の両方が更新されていれば（無限大でなければ）、その和を出力します。そうでなければ \(-1\) を出力します。

計算量

• 時間計算量: \(O(N + \sum K_j)\)
  • 食材情報の読み込みに \(O(N)\)、各日の食材チェックの合計回数が \(O(\sum K_j)\) となります。制約よりどちらも \(2 \times 10^5\) 程度であるため、高速に動作します。
• 空間計算量: \(O(N + \sum K_j)\)
  • 食材情報および入力された買い物リストを保持するためのメモリが必要です。

実装のポイント

• 高速な入出力: 入力データ数が多いため、Pythonでは sys.stdin.read().split() を使って一括で読み込んだり、sys.stdout.write を使って一括で出力したりすることで、実行時間を大幅に短縮できます。

• 無限大の扱い: 最小値を更新する際の初期値には、価格の最大値（\(10^9\)）よりも十分に大きな値（例: 10**18）を使用します。

• インデックスの調整: 問題文の食材番号は 1-indexed（1から始まる）ですが、プログラム内の配列は通常 0-indexed（0から始まる）であるため、番号を \(-1\) するなどの調整が必要です。

  ソースコード

import sys

def solve():
    # 全ての入力を一度に読み込み、空白文字で分割してリスト化します。
    # これにより、大量の入力データを高速に処理できます。
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # 全てのトークンを整数に変換します。
    data = list(map(int, input_data))
    
    # N: 食材の種類数, M: 買い物日数
    N = data[0]
    M = data[1]
    
    # 各食材の価格と種類を格納するリストを作成します。
    # 食材番号は1からNで与えられるため、0からN-1のインデックスで管理します。
    prices = [0] * N
    types = [0] * N
    
    # dataリスト内の現在の読み込み位置を示すポインタ
    ptr = 2
    for i in range(N):
        prices[i] = data[ptr]
        types[i] = data[ptr + 1]
        ptr += 2
        
    results = []
    # 最小値を求めるための初期値として、十分大きな値を設定します。
    INF = 10**18
    
    for _ in range(M):
        # その日に購入可能な食材の数 K
        K = data[ptr]
        ptr += 1
        
        min_veg = INF  # 野菜(タイプ0)の最小価格
        min_meat = INF # 肉類(タイプ1)の最小価格
        
        # その日に購入可能な食材を1つずつ確認し、それぞれのタイプの最小価格を更新します。
        for _ in range(K):
            # 食材番号(1-indexed)をインデックス(0-indexed)に変換
            item_idx = data[ptr] - 1
            ptr += 1
            
            p = prices[item_idx]
            t = types[item_idx]
            
            if t == 0:  # 野菜
                if p < min_veg:
                    min_veg = p
            else:       # 肉類
                if p < min_meat:
                    min_meat = p
        
        # 野菜と肉類の両方が見つかった場合、その合計の最小値を記録します。
        # どちらか一方でも見つからない場合は -1 を記録します。
        if min_veg == INF or min_meat == INF:
            results.append("-1")
        else:
            results.append(str(min_veg + min_meat))
    
    # 全ての日付の結果を改行区切りで一括出力します。
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-preview によって生成されました。