ARC087 D - FT Robot
解法
やることはこちらの記事の問題と同じです。
まず初めに、縦と横の移動はそれぞれ独立なので、縦の移動と横の移動に分解をして、それぞれが目的の座標にいけるかどうかを判定します。
次に、移動してたどり着くことができる場所について考えます。
今座標xにロボットがいるとして、次にdだけ進むことを考えたとき、ターンは好きな向きに行うことができるので、xから移動できる場所は、(x+d)と(x-d)の2通りです。
そして、次pだけ移動する、としたとき、今度は先ほどの(x+d)、(x-d)からそれぞれ2パターン考えればいいことになります。
これだけ見るとかかりそうな気がするのですが、そこで出てくるのがbitsetです。
そのときに存在しうる座標すべてをまとめて考えることで、計算量を落とします。
具体的には、最初は原点に1を置き、他は0にしておきます。
その後、今現在の状態からdだけ右にシフトしたものと、左にシフトしたものの論理和を取ることで、d移動した後にいける場所にのみ、1がたっていることになります。
考えられる座標はざっくり-8000～8000なので、16000ほどの大きさのbitsetをもっておけば事足ります。そして、移動回数はたかだか4000回(縦と横が分かれているので実際はその半分)なので、計算量はこれで十分間に合います。
最後に、指定された座標に1が立っているかどうかで、いけるかどうかを判定します。
最初の移動のみ、2通りではなく正の方向にしか移動できないことに注意してください(数ケースWAになります)。
