概要

傷のある果物のうち、糖度が \(K\) 未満のものだけを規格外品として出荷するとき、その個数と糖度の合計を求めよ。

考察

この問題では、各果物について「傷があるか」「糖度が \(K\) 未満か」の2つの条件を確認し、両方を満たすものをカウントしていく必要があります。

素朴な方法として、各果物に対して、その番号が \(B_1, B_2, \ldots, B_M\) の中に含まれているかどうかを毎回線形探索すると、最悪で \(O(N \times M)\) の計算量になります。制約より \(N, M\) は最大で \(2 \times 10^5\) なので、このままだと最大で \(4 \times 10^{10}\) 回の比較が必要になり、時間内に処理できません（TLE）。

これを解決するために、「傷のある果物の番号」を集合（set）などのデータ構造に事前に格納しておけば、各果物が傷を持っているかを \(O(1)\) で判定できます。これにより全体の計算量を \(O(N + M)\) まで抑えることができます。

アルゴリズム

1. 入力を読み込む：果物の総数 \(N\)、傷のある果物の数 \(M\)、基準糖度 \(K\)、各果物の糖度リスト \(A\)、傷のある果物番号リスト \(B\)。
2. 傷のある果物の番号を集合 damaged に変換しておく（高速な存在判定のため）。
3. 各果物 \(i = 1, 2, ..., N\) に対して：
   • 果物の番号が damaged に含まれるか（すなわち傷があるか）を確認。
   • 含まれていた場合、さらにその糖度 \(A[i-1]\) が \(K\) 未満であるかを判定。
   • 両方とも条件を満たすなら、カウンタと糖度合計を更新する。
4. 最終的なカウンタと糖度合計を出力する。

計算量

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

実装のポイント

• 果物の番号は1-indexed（1から始まる）だが、配列の添字は0-indexedなので、注意してアクセスすること（例：A[i - 1]）。
• 傷のある果物のリスト \(B\) を集合型 set() に変換することで、高速な要素チェックが可能になる。

ソースコード

# 入力の読み込み
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# 規格外品の個数と糖度合計
count = 0
total_sugar = 0

# 傷のある果物を集合で管理して高速に検索できるようにする
damaged = set(B)

# 各果物について判定
for i in range(N):
    fruit_index = i + 1  # 果物の番号は1-indexed
    if fruit_index in damaged:  # 傷があるか？
        if A[i] < K:  # 糖度がK未満か？
            count += 1
            total_sugar += A[i]

# 結果の出力
print(count, total_sugar)

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