AtCoder AGC #026 : E - Synchronized Subsequence

Dよりもこちら頑張った方がまだよかったかも…。
https://beta.atcoder.jp/contests/agc026/tasks/agc026_e

問題

N個の'a'とN個の'b'で構成される文字列Sが与えられる。
Sの部分列のうち、辞書順最大の物を答えよ。
ただし、Sの先頭からi番目の'a'とi番目の'b'は両方含むか両方含まないのいずれかにしなければならない。

解法

まずaとbの登場回数が同じになる部分でSを分割する。
そうすると対応する'a'と'b'は分割の境界をまたがないため、構成する文字列は分割した個々の部分文字列毎に考えることができる。

個々の部分文字列について、その範囲で条件を満たす最大の（さらに部分の）部分文字列を求め、あとはそれを連結しよう。
個々の部分文字列について、先頭文字が'a'か'b'かで場合分けする。

先頭文字が'a'の場合

'a'のあとは早く'b'が来てほしい。
よって'a'のあと最初の'b'が来るまでの'a'（およびそれに対応する'b')は消してしまおう。
残った文字は先ほどの'b'のあとはまた'a'が続くはずなので、以下同様に繰り返し、ababab...を構築する。

先頭文字が'b'の場合

証明はEditorialに任せるとして、ある'b'以降のすべての'b'（およびそれに対応する'a')を取るパターンが最適である。
よって先頭にくる'b'の位置を総当たりし、辞書順最大になるものを残そう。

最後の連結処理だが、単に連結するだけではなく、結果的に辞書順で大きくなるなら、一部の部分文字列は解に含めないことも重要である。
これはスライド最小値じゃないけど文字列のstackに対し、先の個々の部分文字列を順に積む際、新たな要素を積む前に既存の最上段の内容があらなた要素より小さいなら取り除く、ということを繰り返して行うことで実現できる。

int N;
string S;

string hoge(string S) {
	int cnt[6030]={};
	int vis[6030]={};
	vector<int> As,Bs;
	
	int a=0,b=0,i,j;
	FOR(i,S.size()) {
		if(S[i]=='a') {
			cnt[i]=a++;
			As.push_back(i);
		}
		else {
			cnt[i]=b++;
			Bs.push_back(i);
		}
	}
	
	string R;
	
	if(S[0]=='a') {
		FOR(i,S.size()) {
			if(vis[i]==0) {
				R+=S[i];
				if(S[i]=='a') {
					for(int j=i+1;j<Bs[cnt[i]];j++) vis[j]=vis[Bs[cnt[j]]]=1;
				}
			}
		}
	}
	else {
		FOR(i,S.size()/2) {
			string T;
			FOR(j,S.size()) {
				if(cnt[j]>=i) T+=S[j];
			}
			R=max(R,T);
		}
	}
	return R;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	string T;
	vector<string> V;
	
	x=0;
	FORR(c,S) {
		T+=c;
		if(c=='a') x++;
		else x--;
		if(x==0) {
			string P=hoge(T);
			
			while(V.size() && P > V.back()+P) V.pop_back();
			V.push_back(P);
			T="";
		}
	}
	
	FORR(c,V) cout<<c;
	cout<<endl;
	
}

まとめ

これ先に解いてたら思いつけたかな…どうだろ。