概要

\(N\) 個の製品の品質スコアが与えられ、\(Q\) 回の検査で「基準値 \(T_j\) 未満の製品を廃棄する」という操作を繰り返します。各検査において、その時点で新たに廃棄される製品の個数を求める問題です。

考察

素朴な方法とその限界

各検査ごとに、まだ廃棄されていないすべての製品をチェックして基準値と比較する方法が考えられます。しかし、製品の数 \(N\) と検査の回数 \(Q\) がともに最大 \(2 \times 10^5\) であるため、この方法（計算量 \(O(N \times Q)\)）では最大で \(4 \times 10^{10}\) 回程度の計算が必要になり、実行時間制限に間に合いません。

重要な気づき：製品の順番は関係ない

製品が廃棄されるかどうかは「品質スコア」のみによって決まり、製品の元の番号（並び順）は関係ありません。また、一度廃棄された製品は二度と現れないため、品質スコアが低い順に並べて管理することで効率的に処理できそうです。

例えば、スコアが \([10, 2, 5, 8]\) の製品があるとき、これを昇順にソートして \([2, 5, 8, 10]\) とします。 1. 基準値 \(T_1 = 6\) のとき、スコア \(2, 5\) の 2 つが廃棄されます。残りは \([8, 10]\) です。 2. 基準値 \(T_2 = 4\) のとき、すでに \(6\) 未満のものは廃棄されているため、新たに廃棄されるものは 0 個です。 3. 基準値 \(T_3 = 9\) のとき、残っているもののうち \(9\) 未満のスコア \(8\) が廃棄されます。

このように、スコアをソートしておけば、「現在の基準値 \(T_j\) 未満のものがどこまでか」を二分探索で高速に見つけることができます。

アルゴリズム

1. ソート: 全製品の品質スコア \(A_1, \dots, A_N\) を昇順（小さい順）にソートします。
2. ポインタの管理: 「まだ廃棄されていない最小の製品」を指すインデックス current_idx を 0 で初期化します。
3. 各検査の処理: \(j = 1\) から \(Q\) までの各基準値 \(T_j\) について以下を行います。
   • ソート済みのリスト \(A\) に対して、値が \(T_j\) 以上となる最初の位置 new_idx を二分探索（Python では bisect_left 関数）で探します。
   • このとき、探索範囲の左端を current_idx とすることで、既に廃棄済みの製品を無視できます。
   • 新たに廃棄される個数は new_idx - current_idx となります。
   • 次の検査に備えて、current_idx を new_idx に更新します。

計算量

• 時間計算量: \(O(N \log N + Q \log N)\)
  • 最初のソートに \(O(N \log N)\) かかります。
  • 各クエリに対して二分探索を行うため、クエリ全体で \(O(Q \log N)\) かかります。
  • \(N, Q \leq 2 \times 10^5\) なので、この計算量は十分高速です。
• 空間計算量: \(O(N)\)
  • 製品のスコアを保持するための配列に \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N\) や \(Q\) が大きいため、Python では input() を繰り返すよりも sys.stdin.read().split() などで一括で読み込む方が実行時間を短縮できます。

• 二分探索の活用: 標準ライブラリの bisect モジュールを使用することで、二分探索を簡潔かつ高速に実装できます。

• 累積的な処理: current_idx を更新していくことで、「一度廃棄したものは二度と数えない」という条件を自然に満たすことができます。

  ソースコード

import sys
from bisect import bisect_left

def solve():
    # 標準入力からすべての入力を一括で読み込み、空白文字で分割してトークン化します。
    # これにより、大量の入力を高速に処理できます。
    tokens = sys.stdin.read().split()
    if not tokens:
        return
    
    # N: 製品の個数, Q: 品質検査の回数
    N = int(tokens[0])
    Q = int(tokens[1])
    
    # 各製品の品質スコアを取得し、昇順にソートします。
    # ソートしておくことで、二分探索を用いて効率的に廃棄対象を特定できます。
    A = list(map(int, tokens[2:2+N]))
    A.sort()
    
    # 品質検査の基準値 T_j をリストとして取得します。
    T = list(map(int, tokens[2+N:2+N+Q]))
    
    # current_idx は、まだ廃棄されていない製品のうち、
    # ソートされた品質スコアリスト A における最小のインデックスを指します。
    current_idx = 0
    results = []
    
    # 各検査について順番に処理を行います。
    for threshold in T:
        # bisect_left を使用して、品質スコアが threshold 以上である最初のインデックスを探します。
        # lo=current_idx を指定することで、すでに廃棄された製品を探索範囲から除外します。
        new_idx = bisect_left(A, threshold, lo=current_idx)
        
        # 以前の検査で廃棄されず、今回の検査で新たに廃棄される製品の個数は、
        # (今回の基準値未満の最初のインデックス) - (前回までの検査で廃棄された最後のインデックス) となります。
        discarded_count = new_idx - current_idx
        results.append(str(discarded_count))
        
        # 廃棄された製品の分、current_idx を進めます。
        current_idx = new_idx
        
    # すべての検査結果を改行で結合し、一括で出力します。
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

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