2次元平面上でX軸とY軸を独立に考えることができる問題

少し難しめ

ABC 351 E

入門

問題

https://atcoder.jp/contests/abc274/tasks/abc274_d

解法

$p_i$ から $p_{i+1}$ への遷移を考えると

$$ i = 0 \pmod 2 \\ p_{i+1} = \begin{cases} (p_{i} x+A[i],p_{i}y) \\ (p_{i} x-A[i],p_{i}y) \end{cases} \\ \text{otherwise} \\ p_{i+1} = \begin{cases} (p_{i} x,p_{i}y+A[i]) \\ (p_{i} x,p_{i}y-A[i]) \end{cases} $$

となる。 $i$ の偶奇によってX軸に値を加算するかY軸に値を加算するかが定まることが分かる。X軸とY軸において取りうる値を更新するように $A$ を前から見ていけば良いことがわかる。

X軸とY軸それぞれにbool型のdpテーブルを用意して上記の式を実装すればよいだけであるが、制約上ゴール地点や途中の座標に負の値が含まれる場合がある。ここで最初からゴールの座標とスターとの座標にそれぞれ適当な値足してあげれば座標を全て正の値として処理することが出来る。 std::map 等を使わずとも簡単に配列だけで実装が出来る。このテクニックはよく使うので覚えておくと良い。