概要

青木君が持っている閲覧許可証で閲覧できる本の難易度の総和を求める問題です。複数の許可証がある場合、最も許可レベルが高いものだけを考えれば十分であることがポイントです。

考察

重要な気づき

閲覧許可証の許可レベル \(L_j\) は「難易度が \(L_j\) 以下の本すべて」を閲覧可能にします。

例えば、青木君が以下の2枚の閲覧許可証を持っているとします： - 許可証A：許可レベル 5（難易度 1, 2, 3, 4, 5 の本が読める） - 許可証B：許可レベル 10（難易度 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 の本が読める）

このとき、許可証Aで読める本は、許可証Bでもすべて読めます。つまり、許可証Aは許可証Bに完全に含まれています。

したがって、最大の許可レベルを持つ許可証1枚だけを考えれば、読める本の集合が決まります。

素朴なアプローチの問題点

もし各許可証ごとに読める本を列挙して集合の和を取ると、計算量が \(O(K \times N)\) となり、\(K\) と \(N\) がともに \(2 \times 10^5\) のとき、\(4 \times 10^{10}\) 回の操作が必要でTLEになる可能性があります。

解決策

上記の気づきから、以下の2ステップで解けます： 1. 青木君が持つ許可証の中で最大の許可レベルを求める 2. 難易度がその最大レベル以下の本の難易度を合計する

アルゴリズム

1. 入力を読み込む

   • 本の難易度の配列 \(P\)
   • 閲覧許可証の許可レベルの配列 \(L\)
   • 青木君が持っている許可証の番号の配列 \(T\)

2. 最大許可レベルを求める

   • \(T\) に含まれる各番号 \(t\) について、\(L[t-1]\)（0-indexed）を調べる
   • その中の最大値を max_level とする

3. 総和を計算する

   • 各本の難易度 \(p\) について、\(p \leq\) max_level なら総和に加える

4. 結果を出力する

具体例

入力例： - 本の難易度：\(P = [3, 7, 2, 9, 5]\) - 許可レベル：\(L = [4, 8, 6]\) - 持っている許可証：\(T = [1, 3]\)（番号1と3）

処理： - 許可証1の許可レベル：\(L[0] = 4\) - 許可証3の許可レベル：\(L[2] = 6\) - 最大許可レベル：\(\max(4, 6) = 6\) - 難易度6以下の本：3, 2, 5（難易度7, 9の本は読めない） - 総和：\(3 + 2 + 5 = 10\)

計算量

• 時間計算量: \(O(K + N)\)
  • 最大許可レベルを求める: \(O(K)\)
  • 本の難易度の総和を求める: \(O(N)\)
• 空間計算量: \(O(N + M + K)\)
  • 配列 \(P\), \(L\), \(T\) を保持するため

実装のポイント

• 1-indexed と 0-indexed の変換: 許可証の番号 \(T_k\) は1から始まるため、配列 \(L\) にアクセスする際は L[t - 1] とする必要があります。

• オーバーフローに注意: 難易度の最大値が \(10^9\)、本の冊数が \(2 \times 10^5\) なので、総和は最大で \(2 \times 10^{14}\) 程度になります。Pythonでは整数のオーバーフローがないため問題ありませんが、他の言語では64bit整数型を使う必要があります。

  ソースコード

def main():
    import sys
    input = sys.stdin.readline
    
    N, M, K = map(int, input().split())
    P = list(map(int, input().split()))
    L = list(map(int, input().split()))
    T = list(map(int, input().split()))
    
    # 青木君が持っている閲覧許可証の中で最大の許可レベルを求める
    max_level = 0
    for t in T:
        max_level = max(max_level, L[t - 1])
    
    # 難易度がmax_level以下の本の難易度の総和を求める
    total = 0
    for p in P:
        if p <= max_level:
            total += p
    
    print(total)

if __name__ == "__main__":
    main()

---

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