AtCoder Regular Contest 087 D - FT Robot

• 問題

D - FT Robot

• 解法

中でが出て来るたびにロボットが動く方向が軸方向→軸方向→軸方向となる。ここで軸方向と軸方向の動きは独立に考えても良い。
軸方向について動いているときを考える。このときロボットが移動できる点は(1回前に軸方向について動いたときに到達した点)±(今回動ける距離)となる。
したがって、のペアを保持すれば回目にロボットが到達できる座標がわかる。
軸方向について動いているときも同様に求められる。

文字列の最初がのときは軸の正の方向にしか動けないことに注意する。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

typedef long long int ll;

const ll MAXN = 8020;

int main()
{
  string s;
  cin >> s;
  int x,y;
  cin >> x >> y;

  vector<int> t;
  int cnt = 0;
//文字列を変形する
  for(int i = 0; i < s.size(); i++){
    if(s[i] == 'T'){
      if(cnt != 0) t.push_back(cnt);
      t.push_back(0);
      cnt = 0;
    }else{
      cnt++;
      if(i == s.size()-1) t.push_back(cnt);
    }
  }

  bool dp_x[MAXN][MAXN*2] = {false}, dp_y[MAXN][MAXN*2] = {false};
  dp_x[0][8000] = true;
  dp_y[0][8000] = true;

  bool flag = false;
  bool xy = true; // trueならx軸について見ている
  int cnt_x = 0,cnt_y = 0;

  for(int i = 0; i < t.size(); i++){
    if(t[i] == 0){
      xy  = !xy;
    }else if(xy){
      cnt_x++;
      for(int j = 0; j < MAXN*2; j++){
        if(dp_x[cnt_x-1][j]){
          if(j+t[i] < MAXN*2) dp_x[cnt_x][j+t[i]] = true;
          if(j-t[i] >= 0 && flag) dp_x[cnt_x][j-t[i]] = true;
        }
      }
    }else if(!xy){
      cnt_y++;
      for(int j = 0; j < MAXN*2; j++){
        if(dp_y[cnt_y-1][j]){
          if(j+t[i] < MAXN*2) dp_y[cnt_y][j+t[i]] = true;
          if(j-t[i] >= 0) dp_y[cnt_y][j-t[i]] = true;
        }
      }
    }

    if(!flag) flag = true;
  }

  cout << ((dp_x[cnt_x][x+8000] && dp_y[cnt_y][y+8000]) ? "Yes" : "No") << endl;

  return 0;
}