ARC087 D : FT Robot(500)
作成日：2017.12.17
最終更新日：2017.12.17
問題概要
$xy$2次元平面の原点に$x$軸の正の向きを向いたロボットが置かれている。
文字$F,T$からなる命令列$s$が与えられ、ロボットはこれを先頭から順に実行していく。
文字$F$は$1$だけ前進、文字$T$はいずれかの方向に$90$度回転という命令を表す。
命令列をすべて実行した後に、ロボットが座標$(x,y)$にいることは可能かどうか判定せよ。
制約
$1 \leq |s| \leq 8000$
$|x| , |y| \leq |s|$
考え方
回転をした回数が偶数の時は$x$軸方向、奇数の時は$y$軸方向を向いているから、各座標を独立に考えることができる。
1回以上回転した後は正負いずれの方向に進むかは選ぶことができるが、一度選んだら再び回転するまでは同じ方向に進み続けなければならない。
よって文字$T$の後に続く文字$F$の数を$z$とすると、現在到達可能な位置から正負いずれかの方向に$z$動いた位置にのみ到達可能である。
つまり、DPをすることにより最終的な到達可能な位置を求めることができる。
但し一度も回転していない時に進む方向は選べないので、その時に移動した分だけ座標をずらすなど別処理が必要である。
この時、計算量は$O(N^2)$なので十分高速である。
ソースコード
マクロ等はこちら
const int MC = 8010;
string S;
int x,y;
bool p[MC],q[MC],t[MC];
int main(){
cin >> S;
cin >> x >> y;
int n = S.size();
int z = 0;
while(z < n && S[z] == 'F') ++z;
x -= z;
if(abs(x)>MC) return cout << "No" << endl , 0;
S += "T";
p[0] = q[0] = 1;
int r = 0;
bool b = 0;
for(; z <= n ; ++z){
if(S[z] == 'T'){
if(r){
fill(t,t+MC,0);
repp(i,0,z){
if(!(b?q:p)[i]) continue;
t[i+r] = t[abs(i-r)] = 1;
}
swap(t,b?q:p);
}
r = 0;
b = !b;
} else {
++r;
}
}
cout << (p[abs(x)] && q[abs(y)] ? "Yes" : "No") << endl;
return 0;
}解法まとめ
一度も回転していない時に進んだ分は、座標をずらすことで対応する。(10-13行)
一回以上回転した後はDPで各座標ごとに到達可能な位置を調べる。
その位置は原点に対して対称であることから、上記コードでは非負の部分のみを求めている。(14-34行)