キーエンスプログラミングコンテスト2022(AtCoder Beginner Contest 274) D - Robot Arms 2 (400)
毎回角度が90度になるので偶奇によってX,Y座標のどちらに影響するかを分けて考えることができる
$ dp[i][j] で$ i番目の要素でX,Y座標の対応する方の値を$ jにできるかどうか、とする
配列で負のインデックスになるのを防ぐために$ 10^4を実際には足しておく
遷移については正の方向、負の方向の両方から遷移元が元々作成可能であれば遷移する
最初だけ正の方向に限定されているのに注意
最後とその前の配列で$ x,yの座標に到達可能であればOK
どっちがどっちになるかは$ nの偶奇によって異なる
それぞれの要素で取り得る範囲を調べる必要があるので$ \mathcal{O}(\max A)