kmjp's blog

競技プログラミング参加記です

Codeforces #710 : Div3. G. Maximize the Remaining String

これも割とすんなり。
https://codeforces.com/contest/1506/problem/G

問題

文字列Sが与えられる。
Sのうち、2回以上登場する文字があると、そのうち1か所を消せる、という処理を繰り返せるとする。
Sを辞書順最大化せよ。

解法

貪欲に、大きい文字を手前に持ってこれるかを判定すればよい。
大きい文字を手前に持ってくるには、その前にある文字をすべて消せるか考えればよく、それらがその大きい文字よりも後ろにあればよい。

int T,N;
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>S;
		N=S.size();
		set<int> P[26];
		FOR(i,N) P[S[i]-'a'].insert(i);
		string T;
		FOR(i,26) {
			for(j=25;j>=0;j--) if(P[j].size()) {
				x=*P[j].begin();
				int ok=1;
				FOR(y,26) if(P[y].size()) {
					if(*P[y].rbegin()<x) ok=0;
				}
				if(ok) {
					P[j].clear();
					T+=(char)('a'+j);
					FOR(j,26) while(P[j].size()&&*P[j].begin()<=x) P[j].erase(P[j].begin());
					break;
				}
			}
		}
		cout<<T<<endl;
		
	}
}

まとめ

なんかこの回序盤で時間かかってるな。一時離席でもしてたかな?