[AtCoder] ABC 145 D – Knight

問題

方針

マス \( i, j \) から \( (i + 1, j + 2) \) に移動するような動き方の回数を \( a \), マス \( i, j \) から \( (i + 2, j + 1) \) に移動するような動き方の回数を \( b \) とします。このとき、\( a, b \) について、次の連立方程式を考えます。

\[
\begin{eqnarray}
2a + b &=& X\\
a + 2b &=& Y
\end{eqnarray}
\]

これは、\( a + b \) 回の移動でマス \( (X, Y) \) に到達するための条件となります。したがって、

\[a = \dfrac{2X – Y}{3},\  b = \dfrac{2Y – X}{3}\]

は整数でなければいけません。\( a + b\) 回の移動で、動き方の順序は関係ないので、

\[ {}_{a + b} \mathrm{ C }_{a}\]

が答えになります。これは、格子状の点と点の移動方法の組み合わせで出てくるような考え方です。

コード