[AtCoder] ABC 184 C – Super Ryuma

問題

方針

\( (r_1, c_1)\) から \(( r_2, c_2) \) への移動は、\( x = |r_2 – r_1| \)、\( y = |c_2 – c_1| \) として、\( (0, 0)\) から \( (x, y) \) への移動を考えることと同じです。

\( 1 \) 回の移動の移動で \( (0, 0) \)行くことができるマスは、整数 \( a \) を用いて、

\[ (a, a), (a, -a)\]

\[ ( i,  j) \ (|i| + |j | \leq 3)\]

と表現できます。\( 2 \) 回の移動の移動で \( (0, 0) \) から行くことができるマスは、\( 1 \) 回の移動を考慮し、整数 \( b \) を用いて、

\[ (a + b, a – b) , (i + b, j + b), (i + b, j – b) \]

\[ (k, l) \ (|k| + |l| \leq 6)\]

と表現できます。ここで、変数 \( a, b \) についての方程式を考えます。

\begin{eqnarray}
a + b &=& x\\
a – b &=& y
\end{eqnarray}

この方程式の解は、

\[ a = \dfrac{x + y}{2} \wedge b = \dfrac{x – y}{2}\]

となります。\( (x + y) \bmod 2 = 0 \) であるとき、\( (x – y) \bmod 2 = 0 \) です。なので、\( (x + y) \bmod 2 = 0 \) であるとき \( 2 \) 回の移動の移動で \( (0, 0) \) から \( (x, y)\) へ移動することができます。このことから、\( (x + y) \bmod 2 = 1 \) のときは、\( (0, 0) \) から \( (1, 0) \) へと移動することで、少なくとも \( 3 \) 回の移動で、 \( (0, 0) \) から \( (x, y)\) へ移動することができます。

コード