FT Robot [AtCoder Regular Contest 087 D]

https://beta.atcoder.jp/contests/arc087/tasks/arc087_b

解法

https://beta.atcoder.jp/contests/arc087/submissions/1875445

縦の動きと横の動きは独立に出来る。
Tで囲まれたFの個数を抜き出す。
すると、奇数番目にある数は横の動きに使え、偶数番目にある数は縦の動きに使える。
そのため、Fの個数を抜き出したら、奇数番目と偶数番目に分ける。
横の動きの1番目は特別にx軸の正の方向でしか動けない。
それ以外はどんな方向でも動ける。
縦と横の動きを別々にチェックする。

check(x,v) := 座標0からスタートして左右どちらかに配列vの数分だけ移動していって座標xまで移動できるか
もう少し言い換えると
check(x,v) := 配列vの数の正負を入れ替えて総和をxにできるか
これをチェックするにはdpをすればいい。
2次元DPをするとメモリ量が爆発しそうだったので、setで到達性判定をしたら間に合った。

string S; int N;
int xy[2];
//---------------------------------------------------------------------------------------------------
int check(int x, vector<int> _v) {
    vector<int> v;
    fore(i, _v) if (i) v.push_back(i);
 
    int n = v.size();
    int cent = 8080;
    
    set<int> dp;
    dp.insert(0);
    fore(i, _v) {
        set<int> pd;
        fore(j, dp) {
            pd.insert(j + i);
            pd.insert(j - i);
        }
        swap(dp, pd);
    }
 
    fore(i, dp) if (i == x) return 1;
    return 0;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S >> xy[0] >> xy[1];
    N = S.length();
 
    int pre = -1, state = 0;
    vector<int> v[2];
    rep(i, 0, N) {
        if (S[i] == 'T') {
            v[state].push_back(i - pre - 1);
            state = 1 - state;
            pre = i;
        }
    }
    v[state].push_back(N - pre - 1);
 
    xy[0] -= v[0].front();
    v[0].erase(v[0].begin(), v[0].begin() + 1);
 
    rep(d, 0, 2) {
        if (!check(xy[d], v[d])) {
            printf("No\n");
            return;
        }
    }
 
    printf("Yes\n");
}