概要

製品の品質スコアと検査の基準値に基づいて、各検査で廃棄される製品の個数を求めます。

考察

この問題では、複数回の検査を通じて「まだ残っている製品」から「基準値未満の品質スコアを持つもの」を選び出して除去する必要があります。

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

例えば、毎回すべての製品を見て、生きているものをチェックし、基準未満ならカウントアップ…という処理を行うと、最悪ケースで \(O(NQ)\) かかります。これは最大で \(4 \times 10^{10}\) 回の計算が必要になり、TLE（時間超過）になります。

また、製品が削除されるたびにリストから実際に削除すると、これもコストがかかります。

改善策

重要な観察として、「製品の品質スコアは固定」「検査のたびに基準値だけが変わる」という点があります。

そこで、以下のように工夫します： - 製品の品質スコアをソートして保持しておきます。 - 「生きているスコア」だけを持つリスト current_scores を管理します。 - 各検査ごとに、二分探索を使って「基準値未満の個数」を高速に求めます。 - 求めた個数分だけリストの先頭から削除すれば、次の検査に備えることができます。

こうすることで、毎回の検索が \(O(\log N)\)、合計で \(O(Q \log N)\) 程度になります。

アルゴリズム

1. 製品の品質スコアのリスト \(A\) をソートして sorted_A を作る。
2. current_scores を sorted_A で初期化する（すべての製品が生きているとする）。
3. 各検査について：
   • 基準値 \(T_j\) を受け取る。
   • bisect.bisect_left(current_scores, T_j) を使って、\(T_j\) 未満の要素数（= 廃棄される個数）を求める。
   • その個数を答えに追加。
   • current_scores の先頭からその個数分を削除する（廃棄された扱いにする）。

計算量

• 時間計算量: \(O(N \log N + Q \log N)\)
  （初期ソートに \(O(N \log N)\)、各クエリで二分探索とリストの一部削除に \(O(\log N + k)\)、ただし全体で削除は高々 \(N\) 回なので amortized で許容）
• 空間計算量: \(O(N)\)

実装のポイント

• bisect.bisect_left はソートされたリストに対して、「指定値未満の要素の個数」を返すのに非常に有効。
• del current_scores[:count] でリストの前から要素をまとめて削除できるが、Python ではこの操作が比較的効率的に行える。
• 入力を高速に読み込むために sys.stdin.read を使用している。

## ソースコード

```python
import bisect
import sys

input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    Q = int(data[1])
    A = list(map(int, data[2:N+2]))
    T = list(map(int, data[N+2:N+2+Q]))
    
    # 製品の品質スコアをソートしたリスト
    sorted_A = sorted(A)
    # 各要素がまだ存在しているかを管理するフラグリスト
    alive = [True] * N
    
    # 現在生きている製品の品質スコアを管理するリスト（ソートされた状態）
    current_scores = sorted_A[:]
    
    results = []
    
    for threshold in T:
        # 基準値未満の製品の数を二分探索で求める
        idx = bisect.bisect_left(current_scores, threshold)
        count = idx
        results.append(count)
        
        # 廃棄された製品をcurrent_scoresから削除
        # ここでは、current_scoresの最初のcount個を削除
        del current_scores[:count]
    
    print('\n'.join(map(str, results)))

if __name__ == "__main__":
    main()

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