kmjp's blog

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

Codeforces #675 Div2 E. Minlexes

自分含めEでsystestを落とした人が多い。
https://codeforces.com/contest/1422/problem/E

問題

文字列Sが与えられる。
Sの1~|S|文字のsuffixそれぞれについて、以下を求めよ。

  • 連続する同じ2文字を取り除くことを任意回数行える時、得られる辞書順最小の文字列

解法

Sをひっくり返して、先頭から1文字ずつ追加していくことを考える。
文字列をRLEで圧縮して表現しつつ、もし同じ文字が偶数個続き、かつそれらを消した方が辞書順最小になる(後ろにより辞書順で手前の文字がある)なら消していこう。

string S;
int N;
string ret[101010];
int len[101010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	vector<vector<int>> T;
	
	int num=0;
	for(i=N-1;i>=0;i--) {
		char c=S[i];
		if(T.size()&&T.back()[0]==c) {
			if((T.size()==1 || T[T.size()-2][0]<c)&&T.back()[1]==i+1) {
				T.back()[2]--;
				if(T.back()[2]==0) T.pop_back();
				num--;
			}
			else {
				T.back()[1]=i;
				T.back()[2]++;
				num++;
			}
		}
		else {
			T.push_back({c,i,1});
			num++;
		}
		
		len[i]=num;
		if(num>10) {
			x=T.size()-1;
			y=T[x][2];
			FOR(j,5) {
				ret[i].push_back(T[x][0]);
				y--;
				if(y==0) {
					x--;
					y=T[x][2];
				}
			}
			ret[i]+="...";
			if(T[0][2]==1) {
				ret[i].push_back(T[1][0]);
				ret[i].push_back(T[0][0]);
			}
			else {
				ret[i].push_back(T[0][0]);
				ret[i].push_back(T[0][0]);
			}
			
		}
		else {
			FORR(t,T) FOR(j,t[2]) ret[i]+=(char)t[0];
			reverse(ALL(ret[i]));
		}
	}
	
	FOR(i,N) {
		cout<<len[i]<<" "<<ret[i]<<endl;
	}
	
}

まとめ

本番なんでsystest落としたんだろ。