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: