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:
