Official

C - LRUD Instructions 2 Editorial by kyopro_friends


それぞれの移動後の座標を求め、それらの中に重複があるかどうかを調べればよいです。

要素の重複を探す際、配列/リストから探すと、1回あたり配列/リストの長さに比例する時間がかかり、全体で \(\Theta(N^2)\) 時間となりTLEとなります。setなどを用いることで 1回あたり \(O(\log N)\) 時間、全体で \(O(N\log N)\) 時間となます。

実装例(C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
	int N;
	cin >> N;
	string S;
	cin >> S;
	set<pair<int,int>>used({{0,0}});
	int x=0,y=0;
	for(auto c:S){
		if(c=='U')y++;
		if(c=='D')y--;
		if(c=='R')x++;
		if(c=='L')x--;
		if(used.find({x,y})!=used.end()){
			cout << "Yes" << endl;
			return 0;
		}
		used.insert({x,y});
	}
	cout << "No" << endl;
}

posted:
last update: