Codeforces Global Round 4 : E. Archaeology

Fまでの早解きでHighestをたたき出した回。
https://codeforces.com/contest/1178/problem/E

問題

abcだけで構成される文字列Sが与えられる。
S中で同じ文字は連続していないことが保障される。

Sの半分以上の長さの部分列で、回文となるものを構成せよ。

解法

Sが4文字以上ある場合、先端と末尾の2文字ずつを見ると、必ず1つは先端と末尾両方に含まれる文字がある。
よって両端からそれを残すことにしよう。
Sが3文字以下になったらどれでも1文字残せばよい。

int N;
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	
	string ret;
	int L=0,R=N;
	while(R-L>=4) {
		if(S[L]==S[R-1] || S[L]==S[R-2]) {
			ret+=S[L];
		}
		else if(S[L+1]==S[R-1] || S[L+1]==S[R-2]) {
			ret+=S[L+1];
		}
		L+=2;
		R-=2;
	}
	string ret2=ret;
	reverse(ALL(ret2));
	if(L<R) ret+=S[L];
	ret+=ret2;
	cout<<ret<<endl;
}

まとめ

Eとはいえ、ポイント的にはDiv1B相当なのでそこまで難しくない。