Codeforces #541 Div2 E. String Multiplication

不参加の回でした。
https://codeforces.com/contest/1131/problem/E

問題

文字列S,Tの積S*TをT+S[0]+T+S[1]+T+...+S[|S|-1]+Tとする。
ここでN個の文字列P[i]が与えられる。
(((P[0]*P[1])*P[2])*P[3]... と順次掛けていってできる文字列において、同じ文字が続くのは最長何文字か。

解法

文字列をランレングス圧縮し、先頭と末尾の値を覚えつつ順次積を取って行けばよい。

int N;
string S;
vector<pair<char,int>> V;
int ma;

int from[26];
int to[26];

vector<pair<char,int> > RLE(string S) {
	vector<pair<char,int> > V;
	FORR(r,S) {
		r-='a';
		if(V.size() && V.back().first==r) V.back().second++;
		else V.push_back({r,1});
	}
	return V;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>S;
		auto A=RLE(S);
		
		FOR(j,26) to[j]=(from[j]>0?1:0);
		FORR(a,A) to[a.first]=max(to[a.first],a.second);
		if(A.size()==1) {
			to[A[0].first]=max(to[A[0].first],(from[A[0].first]+1)*A[0].second+from[A[0].first]);
		}
		else {
			if(A[0].first==A.back().first && from[A[0].first]) {
				to[A[0].first]=max(to[A[0].first],1+A[0].second+A.back().second);
			}
			if(from[A[0].first]) {
				to[A[0].first]=max(to[A[0].first],1+A[0].second);
			}
			if(from[A.back().first]) {
				to[A[0].first]=max(to[A[0].first],1+A.back().second);
			}
		}
		memmove(from,to,sizeof(from));
	}
	FOR(j,26) ma=max(ma,from[j]);
	
	cout<<ma<<endl;
}

まとめ

今回EよりFの方が大量に解かれているの謎。