これも割とすんなり。
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; } }
まとめ
なんかこの回序盤で時間かかってるな。一時離席でもしてたかな?