AtCoder Begginer Contest ABC082 D - FT Robot
2020/2/7
ポイント
状態を前に持って、grid全体を使ったDPをすると$ O(N^3)でTLE
状態を減らすことを考える。
$ N回の操作を変えることは難しそうであることから、状態を減らそう
そもそも二次元に取る必要があるのかということから考える
最初右に向いていて、Tがきたら横どちらかを向き、進む
Tが連続するときは何回も回れるように見えるが、Tの間に0回のFがあると考えれば、偶奇で上下を独立に考えることができる
一つ実装上で注意が必要なのは、最初に移動するか、最初に回転するかどうかで最初の左への移動ができるかどうかが変わるので、注意
解説記事
code:c++
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i) #define rep1(i,N) for(int i=1;i<int(N);++i) #define all(a) (a).begin(),(a).end() typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const int INF = 1e9;
const ll INFLL = 1e18;
const ll MOD = 1e9+7;
const double PI = acos(-1.0);
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
cout << fixed << setprecision(20);
string s;
int x,y;
cin>>s>>x>>y;
int N = s.size();
vector<int> v;
int cnt = 0;
rep(i,N){
else{
v.push_back(cnt);
cnt = 0;
}
}
v.push_back(cnt);
//print(v);
vector<int> dx;
vector<int> dy;
rep(i,v.size()){
if(i % 2 == 0)dx.push_back(vi); }
print(v);
print(dx);
print(dy);
rep(i,8888)rep(j,8888 * 2){
}
int base = 8005;
bool first_flag = (s0 == 'F'); rep(i, (int)dx.size()){
rep(j, base * 2){
if(i == 0){
if(!first_flag)dp1i+1[j-dxi] = true; }
else{
}
}
}
}
rep(i, (int)dy.size()){
rep(j, base * 2){
}
}
}
cout<<"Yes"<<endl;
}
else{
cout<<"No"<<endl;
}
}