概要

傷のある果物のうち、糖度が \(K\) 未満のものだけを数え、その個数と糖度合計を求める問題です。

考察

求めたいのは「規格外品」＝ (傷がある) かつ (糖度が \(K\) 未満) の果物です。
つまり、傷のある果物の番号リスト \(B_1,\dots,B_M\) だけに注目し、それぞれの糖度 \(A_{B_j}\) を調べて \(A_{B_j} < K\) ならカウントし、合計に加えれば十分です。

ここで重要なのは、全ての果物 \(1..N\) を毎回探したり、傷リストとの照合を複雑に行う必要がないことです。
例えば「各果物 \(i\) について傷があるかを毎回探す（線形探索）」のような実装にすると、最悪で \(O(NM)\) となり（\(N,M \le 2\times 10^5\) なので）到底間に合いません。

この問題では、傷のある果物番号 \(B_j\) が最初から与えられているので、最初から \(B\) を順に見るだけで \(O(M)\) で処理できます。

（例）
\(A=[5,12,3,10],\ B=[2,3],\ K=10\) のとき
- 果物2の糖度は12（\(12 \ge 10\)）→規格外でない
- 果物3の糖度は3（\(3 < 10\)）→規格外
よって個数1、合計3になります。

アルゴリズム

1. 入力で糖度配列 \(A\)（長さ \(N\)）と、傷のある番号配列 \(B\)（長さ \(M\)）を受け取る。
2. 変数 cnt=0（規格外の個数）、total=0（糖度合計）を用意する。
3. 各 \(b \in B\) について以下を行う：
   • 糖度 \(a = A_{b}\) を取り出す（実装上は 1-indexed なので A[b-1]）。
   • もし \(a < K\) なら cnt += 1, total += a。
4. cnt total を出力する。

計算量

• 時間計算量: \(O(N+M)\)（配列読み込み \(O(N)\) + 傷リスト走査 \(O(M)\)）
• 空間計算量: \(O(N+M)\)（入力配列を保持するため。処理自体の追加領域は \(O(1)\)）

実装のポイント

• \(B_j\) は \(1\) から始まる番号なので、Pythonの0-indexed配列に合わせて A[b-1] とする。

• \(N,M\) が最大 \(2\times 10^5\) なので、Pythonでは sys.stdin.buffer.read() を使うと高速に入力できる。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M, K = data[0], data[1], data[2]
    A = data[3:3+N]
    B = data[3+N:3+N+M]

    cnt = 0
    total = 0
    for b in B:
        a = A[b-1]
        if a < K:
            cnt += 1
            total += a

    print(cnt, total)

if __name__ == "__main__":
    main()

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