Codeforces #767 : Div1 B. Peculiar Movie Preferences

後半もかなり解かれているな…。
https://codeforces.com/contest/1628/problem/B

問題

3文字以下の文字列の列が与えられる。
この部分列のうち、連結すると回文になるものは何通りか。

解法

以下のパターンだけ考えればよい。

• 2文字 + 2文字
• 3文字 + 2文字
• 2文字 + 3文字
• 3文字 + 3文字

よって前に出てきた文字列を反転したものや、3文字中前2文字を反転したものをそれぞれsetに入れておき、同じものが再び出てくるか判定すればよい。

int T,N;
string S[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) cin>>S[i];
		
		set<string> V[4];
		
		FOR(i,N) {
			if(S[i][0]==S[i].back()) break;
			string T=S[i];
			reverse(ALL(T));
			if(S[i].size()==2) {
				if(V[2].count(T)) break;
				if(V[1].count(T)) break;
				V[2].insert(S[i]);
			}
			if(S[i].size()==3) {
				if(V[2].count(T.substr(0,2))) break;
				if(V[3].count(T)) break;
				V[3].insert(S[i]);
				V[1].insert(S[i].substr(0,2));
			}
		}
		if(i!=N) {
			cout<<"YES"<<endl;
			continue;
		}
		else {
			cout<<"NO"<<endl;
		}
		
		
	}
}

まとめ

Bにしては簡単？と思ったら案の定750ptだった。