Official

B - Search and Delete Editorial by mechanicalpenciI


\(M\) 回の操作を順にシミュレーションすることを考えます。
\(k\) 回目の操作のシミュレーションは、例えば以下のように行うことができます。

空列 \(A'=()\) を用意します。また、\(k\) 回目の操作において、すでに要素の削除を行ったかを管理するフラグ \(F_k\) を用意します。最初、\(F_k=\mathrm{False}\) です。
以下の手続きを \(i=1,2,\ldots,\lvert A\rvert\) について行います。ここで、\(\lvert A\rvert\) は、\(k\) 回目の操作を行う直前の時点における、\(A\) の長さです。

\(A_i=B_k\) かつ \(F_k=\mathrm{False}\) ならば、\(F_k\)\(\mathrm{True}\) に変更し、\(A_j\)\(A'\)追加しない。 そうでないとき、\(A'\) の末尾に \(A_i\) を追加する。

このようにして得られた \(A'\) が操作後の \(A\) にあたるため、\(A\)\(A'\) に置き換え、次の \(k\) について同様のことを繰り返すことで、\(M\) 回の操作をシミュレーションすることができます。 最後に \(M\) 回の操作のシミュレーション後の\(A\) を出力形式に従って出力すれば良いです。よって、この問題を解くことができました。
なお、余談ですが、この解法の時間計算量は \(O(NM)\) です。今回の制約下では十分高速ですが、別の解法を用いれば、\(O(N+M\log \min(N,M))\) などのより高速な手法で解くこともできます。

C++ による実装例:

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

int main(void){
	int n,m,x;
	bool flag;
	vector<int>a,nxt;

	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>x;
		a.push_back(x);
	}

	for(int i=0;i<m;i++){
		cin>>x;
		flag=true;
		n=a.size();
		nxt.clear();
		for(int j=0;j<n;j++){
			if((a[j]==x)&&flag)flag=false;
			else nxt.push_back(a[j]);
		}
		a=nxt;
	}

	n=a.size();
	for(int i=0;i<n;i++){
		cout<<a[i];
		if(i<(n-1))cout<<" ";
		else cout<<endl;
	}
	return 0;
}

Python による実装例:

n,m=map(int, input().split())
a=list(map(int, input().split()))
b=list(map(int, input().split()))

for x in b:
    nxt=[]
    flag=True
    for y in a:
        if x==y and flag:
            flag=False
        else:
            nxt.append(y)
    a=nxt
    
print(*a)

posted:
last update: