ARC087 / ABC082 D FT Robot - 足跡-sokuseki-

2次元平面の原点にロボットが置かれていて、はじめは $x$ 軸の正の方向を向いている。
'F', 'T' のみからなる文字列 $s$ が命令として与えられ、先頭から順に実行される。

すべての命令を実行した後にロボットが座標 $(x, y)$ にいることができるか判定せよ。

制約
$1 \le | s | \le 8000$
$| x | , | y | \le | s |$

命令Tは90度だけ向きを変えることができるから、命令Tを区切りとして分割した時、 $i$ 番目(1-indexed)の区間は $i$ が奇数なら $x$ 座標の向きの移動、 $i$ が偶数なら $y$ 座標の向きの移動になる。
よって、 $x$ 座標の移動と $y$ 座標の移動は別々に考えてよい。

$dp_x [i][j] :=$ $i$ 番目の $x$ 軸方向の移動をした後に $x$ 座標が $j$ かどうか
$dp_y [i][j] :=$ $i$ 番目の $y$ 軸方向の移動をした後に $y$ 座標が $j$ かどうか

という2つのDPを行い、最終的に座標 $(x, y)$ にいるかを判定すればよい。
DPの計算量は $O(| s | ^2)$ なので十分間に合う。

Submission #2009622 - AtCoder Regular Contest 087
（配列aに分割して入れていく必要はないということに通ってから気づいた）