概要

青木君が持っている \(K\) 枚の閲覧許可証のうち、最も高い許可レベルを \(L_{max}\) とすると、難易度が \(L_{max}\) 以下の本はすべて閲覧可能です。この性質を利用して、条件を満たす本の難易度の総和を効率的に求めます。

考察

重要な気づき

青木君は複数の閲覧許可証を持っていますが、ある本 \(i\) が閲覧できる条件は「持っている許可証の中に、許可レベルが \(P_i\) 以上のものが少なくとも 1 枚存在する」ことです。

これを言い換えると、「持っている許可証の中の最大レベルが \(P_i\) 以上である」ということになります。 つまり、青木君が持っている許可証の番号を \(T_1, T_2, \ldots, T_K\) としたとき、 $\(L_{max} = \max(L_{T_1}, L_{T_2}, \ldots, L_{T_K})\)\( をあらかじめ求めておけば、各本 \)i\( について \)Pi \le L{max}$ かどうかを判定するだけで、その本が読めるかどうかが分かります。

なぜこの工夫が必要か

もし、各本について「持っている \(K\) 枚の許可証のいずれかで読めるか」を愚直に 1 枚ずつ確認すると、最悪の場合で \(N \times K\) 回の比較が必要になります。 制約では \(N, K \le 2 \times 10^5\) であるため、計算回数は最大で \(4 \times 10^{10}\) 回に達し、制限時間内に終わりません。 最大値 \(L_{max}\) を先に求めることで、計算量を大幅に削減できます。

アルゴリズム

1. 最大許可レベルの特定: 青木君が持っている許可証の番号 \(T_1, \ldots, T_K\) を確認し、それに対応するレベル \(L_{T_k}\) の中から最大値 \(L_{max}\) を求めます。
2. 総和の計算: 各本 \(i = 1, \ldots, N\) について順番に難易度 \(P_i\) を確認します。
   • もし \(P_i \le L_{max}\) ならば、その本は読めるので合計値に \(P_i\) を加算します。
   • そうでなければ、その本は読めないので無視します。
3. 結果の出力: 最終的な合計値を出力します。

計算量

• 時間計算量: \(O(N + M + K)\)
  • 入力の読み込みに \(O(N + M + K)\)。
  • 最大レベル \(L_{max}\) の算出に \(O(K)\)。
  • 本の判定と総和の計算に \(O(N)\)。
  • 全体として線形時間で動作するため、十分に高速です。
• 空間計算量: \(O(N + M)\)
  • 本の難易度と許可証のレベルを保持するためのメモリが必要です。

実装のポイント

• 高速な入出力: Pythonで入力数が多い（今回は最大約 \(6 \times 10^5\) 個）場合、input() を繰り返すよりも sys.stdin.read().split() などで一括で読み込む方が実行時間を短縮できます。

• インデックスの調整: 問題文では許可証の番号が \(1\) から \(M\) の \(1\)-indexed で与えられますが、プログラムの配列（リスト）は通常 \(0\)-indexed であるため、L[t_id - 1] のように調整が必要です。

• 大きな数値の扱い: 本の難易度の総和は非常に大きな値になる可能性がありますが、Pythonの int 型は自動的に多倍長整数として扱われるため、オーバーフローの心配はありません。

  ソースコード

import sys

def main():
    # 競プロにおける高速な入出力のために、sys.stdin.read().split() を使用して
    # すべてのトークンを一度に読み込み、リストに格納します。
    # この手法は、多数の入力を個別に読み込むよりも高速です。
    data = sys.stdin.read().split()
    
    # 入力が空の場合は終了します。
    if not data:
        return
    
    # N: 本の冊数, M: 閲覧許可証の種類数, K: 青木君が持っている許可証の枚数
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    
    # 閲覧許可証の許可レベル L_j をリストとして取得します。
    # 本の難易度 P_i が N 個あるため、L はインデックス 3 + N から始まります。
    # 許可証番号 T_k で指定されたレベルを効率的に取得するために、int型のリストに変換します。
    L = list(map(int, data[3 + N : 3 + N + M]))
    
    # 青木君が持っている許可証の中で最大の許可レベルを求めます。
    # 青木君が持っている許可証番号 T_k は、インデックス 3 + N + M から始まります。
    # 本を閲覧できる条件は「難易度 <= いずれかの許可レベル」であるため、
    # 保持している許可証の「最大レベル」以下の本はすべて閲覧可能です。
    max_level = 0
    for i in range(3 + N + M, 3 + N + M + K):
        # 許可証番号 T_k は 1-indexed なので、0-indexed のリスト L に合わせるため -1 します。
        t_id = int(data[i])
        level = L[t_id - 1]
        if level > max_level:
            max_level = level
    
    # 青木君が閲覧できる本の難易度の総和を計算します。
    # 本の難易度 P_i はインデックス 3 から 3 + N - 1 までに格納されています。
    ans = 0
    for i in range(3, 3 + N):
        p_val = int(data[i])
        # 本の難易度が青木君の持つ最大許可レベル以下であれば、その本を閲覧できます。
        if p_val <= max_level:
            ans += p_val
    
    # 計算した総和を出力します。
    # Python の int 型は任意精度であるため、大きな合計値でもオーバーフローしません。
    print(ans)

if __name__ == '__main__':
    main()

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