概要

収穫された \(N\) 個の果物のうち、「傷がある」かつ「糖度が \(K\) 未満」という 2 つの条件を満たす「規格外品」の個数と、その糖度の合計を求める問題です。

考察

この問題を解くために重要なのは、「どの果物をチェックすべきか」を整理することです。

規格外品となる条件は以下の 2 つを同時に満たすことです。 1. 果物に傷がついている（番号が \(B_1, \dots, B_M\) のいずれかである） 2. その果物の糖度 \(A_i\) が \(K\) 未満である

すべての果物（\(N\) 個）を 1 つずつ確認し、それが「傷があるリスト \(B\) に含まれているか」を毎回探すと、リストの検索に時間がかかりすぎてしまいます（\(O(N \times M)\) となり、実行時間制限に間に合いません）。

しかし、今回は「傷がある果物の番号」が最初から \(M\) 個与えられています。 したがって、最初から傷がある果物だけを対象にして、その糖度が \(K\) 未満かどうかを判定すれば、効率よく答えを求めることができます。

アルゴリズム

1. 糖度データの保持: すべての果物の糖度 \(A_1, A_2, \dots, A_N\) を配列（リスト）に格納します。果物番号 \(i\) の糖度は、配列の \(i-1\) 番目の要素として高速に参照できるようにします。
2. 傷のある果物の走査: 与えられた \(M\) 個の「傷のある果物の番号 \(B_j\)」を 1 つずつ取り出します。
3. 条件判定:
   • 果物 \(B_j\) の糖度 \(A_{B_j}\) を配列から取得します。
   • \(A_{B_j} < K\) であれば、その果物は規格外品です。
   • 「規格外品の個数」に 1 を加え、「糖度の合計」に \(A_{B_j}\) を加算します。
4. 出力: 最終的な個数と合計金額を出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • 入力の読み込みに \(O(N + M)\)、傷のある果物 \(M\) 個の判定に \(O(M)\) かかります。\(N, M \leq 2 \times 10^5\) なので、十分高速に動作します。
• 空間計算量: \(O(N)\)
  • 全果物の糖度を保持するために、長さ \(N\) の配列を使用します。

実装のポイント

• 1-indexed と 0-indexed: 問題文の果物番号は \(1\) から始まりますが、プログラミング言語の配列は通常 \(0\) から始まります。果物 \(B_j\) の糖度を参照する際は、インデックスを B[j] - 1 と調整する必要があります。

• 高速な入出力: \(N\) や \(M\) が大きいため、Python では sys.stdin.read().split() などを用いて一括で入力を読み込むことで、実行時間を短縮できます。

• 大きな数値の扱い: 糖度の合計は非常に大きな値になる可能性がありますが、Python は標準で多倍長整数を扱えるため、オーバーフローを気にせず計算できます。

  ソースコード

import sys

def main():
    # 標準入力からすべてのデータを読み込み、空白文字で分割してリストにする
    # この手法は大量の入力を高速に処理するのに適している
    try:
        data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not data:
        return
    
    # N: 果物の総数
    # M: 傷のある果物の個数
    # K: 高級品として扱う基準となる糖度
    n = int(data[0])
    m = int(data[1])
    k = int(data[2])
    
    # A: 各果物の糖度 (1番目からN番目まで)
    # インデックスによる高速なアクセスのため、整数のリストに変換して保持する
    # a[0] が果物1の糖度 A_1 に対応する
    a = list(map(int, data[3:3+n]))
    
    # B: 傷のある果物の番号 (M個)
    # 傷のある果物のインデックスは data[3+n] 以降に格納されている
    b_indices = map(int, data[3+n:3+n+m])
    
    # 規格外品として出荷すべき果物の個数と糖度の合計を管理する変数
    count = 0
    total_sugar = 0
    
    # 傷のある果物それぞれについて、糖度が K 未満であるか判定する
    # 規格外品の条件：傷があり、かつ糖度が K 未満
    for fruit_idx in b_indices:
        # 果物の番号は1から始まるため、リストのインデックス(0から開始)に合わせる
        sugar_content = a[fruit_idx - 1]
        
        if sugar_content < k:
            count += 1
            total_sugar += sugar_content
    
    # 結果を1行にスペース区切りで出力する
    print(count, total_sugar)

if __name__ == "__main__":
    main()

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