概要

製品の品質スコアが格納された配列に対して、複数回の品質検査（基準値未満の製品を廃棄）を行い、各検査で廃棄される製品の個数を求める問題です。

考察

素朴なアプローチとしては、各検査ごとにすべての製品をチェックし、基準値未満の製品を廃棄する方法が考えられます。しかし、製品数 \(N\) と検査回数 \(Q\) が最大で \(2 \times 10^5\) ずつあるため、最悪の場合 \(O(N \times Q)\) の計算量となり、時間内に処理できません。

効率的に解くためには、以下の観察が重要です： 1. 製品は一度ソートすれば、基準値未満の製品は常に配列の先頭部分に集中する 2. 廃棄処理は累積的に行われるため、前回の廃棄位置を覚えておけば、次の検査ではその位置からだけ調べればよい 3. 二分探索を用いることで、基準値 \(T_j\) 未満の製品の境界を高速に見つけられる

アルゴリズム

1. 製品の品質スコア配列 \(A\) を昇順にソートする
2. 現在の有効な製品の開始位置を表すポインタ ptr を 0 で初期化
3. 各検査 \(j\) について：
   • 二分探索で基準値 \(T_j\) 以上の最初の位置 idx を求める
   • ptr から idx までの製品数 (idx - ptr) が今回廃棄される個数
   • ポインタ ptr を idx に更新して、次回の検査に備える
4. 各検査で求めた廃棄個数を順次出力する

計算量

• 時間計算量: \(O(N \log N + Q \log N)\)
  • ソートに \(O(N \log N)\)
  • 各検査での二分探索に \(O(\log N)\) ずつ、合計 \(O(Q \log N)\)
• 空間計算量: \(O(N)\)
  • 製品配列の格納に必要なメモリ

実装のポイント

• bisect_left 関数を使って、基準値以上の最初の位置を効率的に検索

• ポインタ ptr で現在残っている製品の開始位置を管理

• 各検査で廃棄される個数が 0 の場合も正しく処理する

• 一括読み込みで入力を効率的に処理

  ソースコード

import sys
import bisect

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    q = int(data[1])
    A = list(map(int, data[2:2+n]))
    T_list = list(map(int, data[2+n:2+n+q]))
    
    A.sort()
    count = n
    removed = 0
    ptr = 0
    
    for T in T_list:
        idx = bisect.bisect_left(A, T)
        to_remove = idx - ptr
        if to_remove > 0:
            ptr += to_remove
            removed = to_remove
        else:
            removed = 0
        print(removed)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。