Codeforces #336 Div1 C. Marbles

これ本番思い浮かばなかったけど結構正答者多いんだよな…。
http://codeforces.com/contest/607/problem/C

問題

原点から、距離1の格子点を順に結んでできるN点からなるパスが２つ与えられる。

ここで両方のパスに対応する２個のトークンを準備する。
プレイヤーは、これらトークンを上下左右どちらに動かすか宣言する。
両パスにおいて、それぞれ対応する方向に移動可能なパスがある場合、トークンをその格子点に移動する。
移動可能なパスがない場合、そちらのトークンは動かさない。

両トークンをパスの末尾に同時に到達させることは可能か判定せよ。

解法

Editorialを見て回答。
ある連続する移動経路に対し、それを逆順にたどる経路（すなわち逆の順番で逆の向きに移動していく）を反転経路と呼ぶ。

条件を満たす移動は不可能な条件は、片方のパスのsuffixの反転経路が、もう片方のパスのsuffixとなっていることである。
よってそのようなsuffixが存在するか判定しよう。
まず１つ目のパスを示す文字列について順番を逆転、２つ目のパスを示す文字列について、上下左右を反転させる。
そして(処理後の１つ目のパスを示す文字列)+"#"+(処理後の２つ目のパスを示す文字列)という文字列を生成すれば、Zアルゴリズムを用いて末尾n文字と先頭n文字が一致するかチェックすることで判定できる。

int N;
string S[2],T;

vector<int> Zalgo(string s) {
	vector<int> v(1,s.size());
	for(int i=1,l=-1,r=-1;i<s.size();i++) {
		if(i<=r && v[i-l]<r-i+1) v.push_back(v[i-l]);
		else {
			l=i; r=(i>r)?i:(r+1);
			while(r<s.size() && s[r-i]==s[r]) r++;
			v.push_back((r--)-l);
		}
	}
	return v;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S[0]>>S[1];
	N--;
	FOR(i,N) {
		if(S[1][i]=='N') S[1][i]='S';
		else if(S[1][i]=='S') S[1][i]='N';
		else if(S[1][i]=='E') S[1][i]='W';
		else if(S[1][i]=='W') S[1][i]='E';
	}
	reverse(ALL(S[0]));
	T=S[0]+"#"+S[1];
	auto v=Zalgo(T);
	
	for(i=1;i<=N;i++) if(v[v.size()-i]==i) return _P("NO\n");
	return _P("YES\n");
}

まとめ

考察さえできればコードは非常に簡単なんだよな。