【AtCoder】ABC 417 B - Search and Delete | 緑コーダーが解くAtCoder

https://atcoder.jp/contests/abc417/tasks/abc417_batcoder.jp

配点: 200 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 41 / NoviSteps: 6Q

問題概要
制約
考察
実装例
コメント

問題概要

長さ $N$ の広義単調増加整数列 $A$ が与えられる。この整数列に対して、 $M$ 回の操作を行う。 $i$ 回目の操作では、次の操作を行う。

数列 $A$ が $B_i$ を要素として持つならば、そのような要素を1つ選び削除する。そのような要素が存在しないならば何もしない。

$M$ 回の操作を行った後の $A$ を求めよ。

制約

$1 \leq N, M \leq 100$
$1 \leq A_i,B_i \leq 10^9$
入力はすべて整数

考察

$A$ は単調増加数列なので、 $B_i$ の位置(正確には $B_i$ 以上の要素の中で最小のもののイテレータ)は二分探索できる。

位置が特定出来たら、そのイテレータが $B_i$ を指しているかをチェックして、erase関数で実際に要素を削除すればよい。

計算量は $O(M \log N)$ となる。

実装例

#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

int main()
{
    int N, M;
    cin >> N >> M;
    vector<int> A(N), B(M);
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, M) cin >> B[i];

    rep(i, 0, M)
    {
        auto itr = lower_bound(all(A), B[i]);
        if (itr != A.end() && *itr == B[i])
        {
            A.erase(itr);
        }
    }

    for (auto &&x : A)
    {
        cout << x << ' ';
    }
    cout << endl;
}