ABC082 D - FT Robot Next-DP 解法

Next-DP よくわかってないのでもしかしたら違うかも．
問題リンク D - FT Robot

解法

まず，前処理として $S$ を $\lbrace x軸とy軸どちらと平行に動くか,移動する回数 \rbrace$ というペアの列にランレングス圧縮します．次に，配列 $\mathrm{dp}$ の値 $\mathrm{dp}_{x,y}$ を，座標 $(x,y)$ に到達できるかの bool 値と定めます．すると， $i$ 回目の移動で到達しうる座標は前に同じ向きで移動したときに到達しうる座標にのみ依存します．よって，RLE 配列を順に見ていき，Next-DP 配列に移動後に到達しうる座標を記録し $\mathrm{dp}$ の対応する次元の値を上書き，という操作を繰り返すことで最終的に到達しうる座標を求めることができます．RLE 配列のサイズは $O(|S|)$ 時間，移動による配列の更新も $O(|S|)$ 時間で行えるので全体として $O(|S|^2)$ 時間で答えを求めることができます．
提出コード (76ms) Submission #61342243 - AtCoder Beginner Contest 082