自分含め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落としたんだろ。