AtCoder ARC087 FT-Robotを解きました
最近のABCに似た問題があったためにすぐ解けて嬉しかったのでメモ
FFFTFTFFみたいなのが与えられて、Fは直進、Tは90度回転を表す。回転は左右どちらでもいい。初めは(1,0)方向に進んでいる。また、座標（X,Y）も同時に与えられるのでその地点に到達できるかを答える問題。
入力をFFFTFTFFとすると連続するFを数字に変えて3T1T2としてみる。「3進む->回転->1進む->回転->2進む」を表す。こういう列をX1,T,X2,T,X3として表記する(上の例ではX1=3, X2=1, X3=2)と、左右のどちらかにX2i移動、上下どちらかにX2i+1移動と解釈できる。
あとはX2iに+か-掛けながら足して与えられるXに一致させられるか。同様にX2i+1の和をYに一致させられるか調べる問題に落ちる。
普通にdp（dp[2i][x] = X1~2i-2までをみてxにいることができるか）すればいいのだが、計算量はN**2。N=8000なのでpythonでは少し厳しい。（試してないだけでできるかも。）
参考になった最近の類題とはこれのこと。
これも同様のDPだが計算量で悩まされた。
bit演算にすればいい。
dp[2i] = X1~2i-2までをみてxにいることができる場合、xビット目が1、そうでない時0であるような数
とすれば、添字が１つ減る。嬉しい。
dp[0] = 1<<8000としておいて、Xiが来たらdp[2i] = dp[2i-2]>>Xi |dp[2i-2] <<Xi と更新でAC。
と思いきやWA...
あ、X2i は左右移動とかいたが、i=0の時は右移動に限られるのか。
初期化方法を少し変えてAC。difficultyは水らしいが、pythonだとbitも絡むのでもう少しだけ難しいかも。でもレートインフレ起きているので現在だとやっぱり水か。
