概要

製品の品質スコアの配列が与えられ、各検査で基準値未満の製品を廃棄していくとき、各検査で何個廃棄されるかを求める問題です。一度廃棄された製品は再び廃棄されない点がポイントです。

考察

重要な気づき：基準値は「これまでの最大値」だけが意味を持つ

各検査では「品質スコアが \(T_j\) 未満の、まだ廃棄されていない製品」を廃棄します。ここで、過去の検査で既に基準値 \(T\) 未満の製品はすべて廃棄済みです。

つまり、これまでの検査で適用された基準値の最大値を \(M\) とすると、現時点でまだ残っている製品は品質スコアが \(M\) 以上のものだけです。

• 新しい基準値 \(T_j\) が \(M\) 以下の場合: 品質スコアが \(T_j\) 未満の製品はすべて過去の検査で廃棄済みなので、廃棄数は \(0\) です。
• 新しい基準値 \(T_j\) が \(M\) より大きい場合: 品質スコアが \(M\) 以上 \(T_j\) 未満の製品が新たに廃棄されます。

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

毎回すべての製品を走査して基準値未満かどうか判定すると、最悪 \(O(NQ)\) の計算量となり、\(N, Q\) が最大 \(2 \times 10^5\) のとき TLE になります。

解決策：ソート＋二分探索

品質スコアをあらかじめソートしておけば、「\(M\) 以上 \(T_j\) 未満の製品の個数」を二分探索で \(O(\log N)\) で求められます。

アルゴリズム

1. 品質スコアの配列 \(A\) を昇順にソートする。
2. これまでの基準値の最大値 \(M\) を \(0\) で初期化する（品質スコアは \(1\) 以上なので、初期状態では何も廃棄されていない）。
3. 各検査 \(j\) について：
   • \(T_j > M\) の場合：ソート済み配列で \(M\) 以上 \(T_j\) 未満の要素数を二分探索で求める。具体的には bisect_left(A, T_j) - bisect_left(A, M) が廃棄数。\(M\) を \(T_j\) に更新する。
   • \(T_j \leq M\) の場合：廃棄数は \(0\)。

具体例: \(A = [2, 5, 3, 1, 4]\)、検査の基準値が \(3, 2, 5\) の場合

• ソート後: \(A = [1, 2, 3, 4, 5]\), \(M = 0\)
• 検査1 (\(T=3\)): \(0\) 以上 \(3\) 未満 → \([1, 2]\) の \(2\) 個廃棄。\(M = 3\)
• 検査2 (\(T=2\)): \(T \leq M\) なので \(0\) 個
• 検査3 (\(T=5\)): \(3\) 以上 \(5\) 未満 → \([3, 4]\) の \(2\) 個廃棄。\(M = 5\)

計算量

• 時間計算量: \(O(N \log N + Q \log N)\)
  • ソートに \(O(N \log N)\)、各検査での二分探索に \(O(\log N)\) × \(Q\) 回
• 空間計算量: \(O(N + Q)\)
  • ソート済み配列と結果の格納

実装のポイント

• \(M\) の初期値を \(0\) にすることで、最初の検査から正しく動作する（品質スコアは \(1\) 以上のため）。

• bisect_left(A, T) は「\(A\) の中で \(T\) 未満の要素数」を返すので、区間 \([M, T)\) の要素数が bisect_left(A, T) - bisect_left(A, M) で正確に求まる。

• 出力を sys.stdout.write でまとめて行うことで、Python での I/O を高速化している。

  ソースコード

import bisect
import sys
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    
    max_threshold = 0
    results = []
    
    for _ in range(Q):
        T = int(input())
        prev = max_threshold
        if T > max_threshold:
            # Count elements with prev <= A[i] < T
            left = bisect.bisect_left(A, prev)
            right = bisect.bisect_left(A, T)
            results.append(right - left)
            max_threshold = T
        else:
            results.append(0)
    
    sys.stdout.write('\n'.join(map(str, results)) + '\n')

main()

---

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