概要

各日ごとに「その日に買える食材の中から、野菜( \(T=0\) )を1つ・肉( \(T=1\) )を1つ選ぶ」ときの合計金額の最小値を求める問題です。どちらかが買えない日は \(-1\) を出力します。

考察

重要な気づき

1日分の答えは、その日に買える食材のうち - 野菜の最安値 - 肉の最安値
をそれぞれ求めて足すだけで決まります。

なぜなら、条件は「野菜1種類＋肉1種類」のみで、他の制約（同じ食材を複数回買う、相性、個数など）はありません。したがって最適解は独立に「野菜は最安を選ぶ」「肉も最安を選ぶ」でよいです。

素朴なアプローチがダメになりうる点

• 各日について候補の食材リストを見て最安の組を探すのは自然ですが、もし「全食材から毎日探す」ような実装（各日 \(O(N)\)）をすると、最悪で \(O(NM)\) となり \(2\times 10^5\) では到底間に合いません。
• 本問では各日の候補数 \(K_j\) の総和に制約があり、 \(\sum K_j \le 2\times 10^5\) です。
  つまり「与えられた候補だけをなめる」方針にすれば高速にできます。

解決策

各日について、入力で与えられる候補食材だけを走査し、 - \(T=0\) の最小価格 min0 - \(T=1\) の最小価格 min1 を更新します。どちらかが存在しなければ \(-1\)、両方あれば min0 + min1 が答えです。

例：その日の候補が
- 野菜: 120円, 200円
- 肉: 300円, 250円
なら最小は \(120 + 250 = 370\) 円です。

アルゴリズム

1. 食材ごとの価格 \(P_i\) と種類 \(T_i\) を配列に保存する。
2. 各日について以下を行う：
   • min0 = INF, min1 = INF で初期化
   • その日の候補食材番号 \(s\) を順に読む
     • \(T_s=0\) なら min0 = min(min0, P_s)
     • \(T_s=1\) なら min1 = min(min1, P_s)
   • min0 または min1 が更新されていなければ -1
   • そうでなければ min0 + min1 を出力
3. 入力は大きいので、高速入力（sys.stdin.buffer.read()）でまとめて読み、イテレータで消費する。

計算量

• 時間計算量: \(O\!\left(N + \sum_{j=1}^{M} K_j\right)\)
  （各食材情報を1回、各日の候補食材を合計で1回ずつ見るだけ）
• 空間計算量: \(O(N)\)
  （\(P, T\) の配列）

実装のポイント

• INF は十分大きい値（例： \(10^{30}\) ）を使い、「最安が更新されたか」を判定します。

• 各日で必要なのは「野菜の最小」「肉の最小」だけなので、候補を保存せずその場で更新すればメモリも節約できます。

• 入力サイズが大きいため、Pythonでは input() を繰り返すより sys.stdin.buffer.read() で一括読み込みが安定して高速です。

  ソースコード

import sys

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

    P = [0] * (N + 1)
    T = [0] * (N + 1)
    for i in range(1, N + 1):
        P[i] = next(it)
        T[i] = next(it)

    INF = 10**30
    out_lines = []
    for _ in range(M):
        k = next(it)
        min0 = INF
        min1 = INF
        for _ in range(k):
            s = next(it)
            if T[s] == 0:
                if P[s] < min0:
                    min0 = P[s]
            else:
                if P[s] < min1:
                    min1 = P[s]
        if min0 == INF or min1 == INF:
            out_lines.append("-1")
        else:
            out_lines.append(str(min0 + min1))

    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

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