AtCoder ARC #113 : E - Rvom and Rsrev

本番では割と時間ギリギリで通った。
https://atcoder.jp/contests/arc113/tasks/arc113_e

問題

abで構成された文字列Sが与えられる。
Sに対し、以下を任意回数行い、得られる文字列のうち辞書順最大のものを答えよ。

• S[i]=S[j]となる(i,j)を選び、S[i+1]～S[j-1]を反転したのち、S[i],S[j]を削除する。

解法

末尾がaの場合

Sから全部aを消すか、末尾以外のaを消せば、先頭にbを詰められる。よって、b同士を消す意味はない。
そこで、aを末尾に集められるならできるだけ集めよう。
末尾以外でaが2文字以上連続していたら、そのaの塊の先頭と、末尾のaの塊の先頭を反転させれば、a2文字と引き換えにaを末尾に寄せることができる。

末尾がbの場合

SをRLEしておくとやりやすい。
上記の場合同様に、aが2文字以上連続している箇所があれば、後ろのaと反転させよう。

さらに、1文字で孤立しているaがあれば組み合わせて消したり、2文字以上のaの連続も消しておこう。
細々コーナーケースがあるので注意。

int T;
int N;
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>S;
		N=S.size();
		int C[2]={};
		FORR(c,S) C[c-'a']++;
		
		if(C[1]==0||C[0]==0) {
			cout<<S<<endl;
			continue;
		}
		
		if(S.back()=='a') {
			vector<int> V;
			int cur=0;
			int sum=0,single=0;
			FORR(c,S) {
				if(c=='a') {
					cur++;
				}
				else {
					if(cur>1) sum+=cur-2;
					else if(cur==1) single^=1;
					cur=0;
				}
			}
			sum+=cur-single;
			cout<<string(C[1],'b')+string(sum,'a')<<endl;
		}
		else {
			string ret=S;
			
			FOR(k,2) {
				vector<pair<char,int>> V;
				FORR(c,S) {
					if(V.empty()||V.back().first!=c) V.push_back({c,0});
					V.back().second++;
				}
				x=-1;
				for(i=V.size()-1;i>=0;i--) if(V[i].first=='a') {
						if(k==0){
							if(x==-1) x=i;
							else if(V[i].second>1) {
								V[x].second+=V[i].second-2;
								V[i].second=0;
							}
						}
						else {
							if(V[i].second>1) {
								if(x==-1) x=i;
								else {
									V[x].second+=V[i].second-2;
									V[i].second=0;
								}
							}
						}
					}
				}
				x=-1;
				FOR(i,V.size()) if(V[i].first=='a'&&V[i].second==1) {
					if(x==-1) x=i;
					else V[i].second=V[x].second=0,x--;
				}
				if(x>=0) FOR(i,V.size()) if(V[i].first=='a'&&V[i].second>1) V[i].second--,V[x].second--,x=-1;
				string G;
				FORR(v,V) G+=string(v.second,v.first);
				ret=max(ret,G);
				FOR(i,G.size()) if(G[i]=='a') {
					int len=0;
					FOR(len,G.size()) if(G[i+len]!='a') break;
					
					ret=max(ret,string(i,'b')+string(len%2,'a')+string(G.size()-len-i,'b'));
					
					if(i) {
						string G2=G;
						G2.pop_back();
						G2.erase(G2.begin()+i-1);
						reverse(G2.begin()+i-1,G2.end());
						ret=max(ret,G2);
					}
					break;
				}
			}
			cout<<ret<<endl;
		}
		
	}
}

まとめ

かなり面倒だけど、これ綺麗に書けるのかな。