概要

傷のある果物のうち、糖度が基準値 \(K\) 未満のものだけを「規格外品」として数え上げ、その個数と糖度の合計を求める問題です。

考察

問題の整理

この問題で求めるべきは以下の条件を両方満たす果物です： 1. 傷がある（リスト \(B\) に含まれている） 2. 糖度が \(K\) 未満である（高級品の基準を満たさない）

つまり、「傷があっても糖度が \(K\) 以上なら規格外品にならない」というルールがポイントです。

具体例で理解

例えば、\(N=5, M=3, K=50\) で、糖度が \(A = [30, 60, 45, 80, 25]\)、傷のある果物が \(B = [1, 2, 4]\) の場合：

結果：規格外品は1個、糖度の合計は30

アプローチ

傷のある果物は最大 \(M\) 個（\(M \leq N \leq 2 \times 10^5\)）なので、\(M\) 個すべてをチェックしても十分高速です。特別なアルゴリズムは必要なく、単純なループで解けます。

アルゴリズム

1. 果物の糖度リスト \(A\) と、傷のある果物の番号リスト \(B\) を入力として受け取る
2. 規格外品の個数 count と糖度の合計 total を0で初期化
3. 傷のある果物の番号 \(b\) それぞれについて：
   • 果物 \(b\) の糖度 \(A_{b}\) を取得（配列は0-indexedなので \(A[b-1]\)）
   • もし糖度が \(K\) 未満なら、count を1増やし、total に糖度を加算
4. 最終的な count と total を出力

計算量

• 時間計算量: \(O(N + M)\)
  • 糖度リスト \(A\) の入力に \(O(N)\)
  • 傷のある果物リスト \(B\) の入力と走査に \(O(M)\)
  • 各果物の糖度の参照は \(O(1)\)
• 空間計算量: \(O(N + M)\)
  • 糖度リスト \(A\) の保存に \(O(N)\)
  • 傷のある果物リスト \(B\) の保存に \(O(M)\)

実装のポイント

• インデックスの変換: 問題文では果物の番号は1から始まる（1-indexed）が、Pythonのリストは0から始まる（0-indexed）ため、果物番号 \(b\) の糖度を取得するには A[b - 1] とする必要がある

• データ型: 糖度は最大 \(10^9\)、果物は最大 \(2 \times 10^5\) 個なので、合計値は最大約 \(2 \times 10^{14}\) になりうる。Pythonでは整数のオーバーフローを気にする必要はないが、他の言語では64ビット整数型を使う必要がある

  ソースコード

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

count = 0
total = 0

for b in B:
    sweetness = A[b - 1]  # 果物の番号は1-indexed
    if sweetness < K:  # 糖度がK未満の場合のみ規格外品
        count += 1
        total += sweetness

print(count, total)

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