概要

青木君が持っている複数の閲覧許可証のうち、どれか1枚でも使える本を集めたとき、それらの本の難易度の総和を求めます。

考察

まず、青木君が持っている各閲覧許可証には「許可レベル」があり、そのレベル以下の難易度の本を読むことができます。
したがって、青木君が読める本とは、「少なくとも1つの許可証で閲覧可能」である本のことです。
これは言い換えれば、「青木君が持っている許可証の中で最も高い許可レベル」以下の本すべてということになります。

たとえば、青木君が持っている許可証の許可レベルが \([3, 7, 5]\) だった場合、最大値の \(7\) 以下の本なら読むことができます。
このようにして、複数の許可証がある場合でも、その最大値さえわかれば良いことがわかります。

もし素朴に「各本に対して、持っているすべての許可証を確認して読めるかどうか判定」しようとすると、最悪ケースで \(N \times K\) の計算が必要になり、制約が大きいためTLEします（\(N, K \leq 2 \times 10^5\)）。

そこで、「最大の許可レベル」だけを求めて、それに基づいて読める本をまとめて扱うことで効率的に計算できます。
さらに、本の難易度がソートされていれば、二分探索を使って「どの位置までが読める本か」を高速に求めることができます。

アルゴリズム

1. 青木君が持っている閲覧許可証に対応する許可レベルをすべて見て、その中の最大値 \(max\_level\) を求めます。
2. 本の難易度リスト \(P\) を昇順にソートします。
3. ソートされた \(P\) の中で、難易度が \(max\_level\) 以下の本の個数を二分探索で求めます（Pythonでは bisect.bisect_right を使う）。
4. それらの本の難易度の総和を計算して出力します。

例

入力例：

N=5, M=3, K=2
P = [1, 4, 6, 2, 8]
L = [3, 7, 5]
T = [1, 3] （青木君が持っているのは1番目と3番目の許可証）

• 青木君が持つ許可証の許可レベルは：\(L[0]=3\), \(L[2]=5\) → 最大値は \(5\)
• 本の難易度をソート：\(P = [1, 2, 4, 6, 8]\)
• 難易度が \(5\) 以下の本は最初の3冊：\(1, 2, 4\)
• 総和：\(1 + 2 + 4 = 7\)

計算量

• 時間計算量: \(O(N \log N + K)\)
  • ソートに \(O(N \log N)\)
  • 閲覧許可証の最大値を求めるのに \(O(K)\)
  • 二分探索と部分列の和の計算は \(O(N)\) 未満
• 空間計算量: \(O(N + M + K)\) （入力をすべてリストに格納するため）

実装のポイント

• 閲覧許可証のインデックスは1始まりなので、配列アクセス時には -1 することに注意。

• 本の難易度の総和は非常に大きくなる可能性があるので、Pythonのような言語では特に気にせず計算できるが、C++などではオーバーフローに注意。

• 入力を高速に読み込む工夫（例：sys.stdin.read）を行うことで、大きな入力にも対応できる。

  ソースコード

import sys
import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    
    P = list(map(int, data[idx:idx+N])); idx += N
    L = list(map(int, data[idx:idx+M])); idx += M
    T = list(map(int, data[idx:idx+K])); idx += K
    
    # 閲覧許可証の許可レベルを取得し、最大値を求める
    max_level = 0
    for t in T:
        max_level = max(max_level, L[t - 1])
    
    # 本の難易度をソート
    P.sort()
    
    # 難易度がmax_level以下である本の数を二分探索で求める
    pos = bisect.bisect_right(P, max_level)
    
    # 総和を計算
    total = sum(P[:pos])
    print(total)

if __name__ == "__main__":
    main()

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