Codeforces #910 : Div2 E. Sofia and Strings

順調に全完できた回。
https://codeforces.com/contest/1898/problem/E

問題

文字列S,Tが与えられる。
Sに以下の処理を任意に繰り返し、Tに構築できるか。

• Sから1文字消す
• Sの部分列を指定し、ソートする

解法

Tを先頭からそろえることを考える。
今Sの何文字かから、Tの先頭m文字を作れたとする。
次にT[m]を作りたい。
残ったSのうち、T[m]と一致する文字のインデックスをxとする。
S[x]の手前に、未使用かつS[x]より大きなアルファベットがあればすべて消す、とすればよい。

int t,N,M;
string S,T;
set<int> X[26];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>t;
	while(t--) {
		cin>>N>>M>>S>>T;
		FOR(i,26) {
			X[i].clear();
		}
		FOR(i,N) {
			X[S[i]-'a'].insert(i);
		}
		int ok=1;
		FORR(c,T) {
			x=c-'a';
			if(X[x].empty()) {
				ok=0;
				break;
			}
			r=*X[x].begin();
			X[x].erase(r);
			FOR(i,x) while(X[i].size()&&*X[i].begin()<r) X[i].erase(X[i].begin());
		}
		if(ok) {
			cout<<"YES"<<endl;
		}
		else {
			cout<<"NO"<<endl;
		}
	}
}

まとめ

これは割とすんなりだな。