Q. 線形代数なんて何の役に立つの？ A. 競プロの問題を解くのに役立つ

この問題を解きました。ネタバレを含みます。

問題

二次元グリッドの原点 (0,0) にチェスのナイトの駒があります。ナイトの駒はマス(i,j)にあるとき(i+1,j+2)か(i+2,j+1)のどちらかのマスにのみ動かすことができます。ナイトの駒をマス(X,Y)まで移動させる方法は何通りありますか？10⁹+7で割った余りを求めてください。

制約

1≤X≤10⁶

1≤Y≤10⁶

入力中のすべての値は整数である。

DPっぽい！解けそう！と思ったら全然解けなくて解説を見ました。解説では言及されていませんでしたが、線形代数でも解けそうな気がしたのでやってみました。

線形代数の本を引っ張り出してやり直すところから始めたので、この問題だけで1週間くらい掛けてしまいました。

線形代数の説明に関する引用元はすべて「意味がわかる線形代数」です。わかりやすくてとてもおすすめです。

www.amazon.co.jp

この問題は二つのパートにわけて考えることができます。

与えられたX,Yという座標を、ナイトの駒が動ける単位であらわしたときの座標に変換する例）元々の座標が(1,2)であれば、(1,0) 元々の座標が(3,3)であれば、(1,1)

この記事ではこのパートだけ書きます

スタート地点(0,0)から目標の座標までに到達する通りを数え上げる機会があれば別の記事で書きます。

まずは、線形代数の基底という概念を思い出します。

R²中の任意の点Pに対して、 $\vec{OP}=k\vec{a}+l\vec{b}$ となる(k,l)の組がただ１通りに決まるとき、{ $\vec{a}, \vec{b}$ }はR²の基底であると言います。

本当は図があるとわかりやすいんですが、準備するのが大変そうだったので諦めました。

$\vec{e_1} =\begin{pmatrix} 1 \\ 0 \end{pmatrix}$

$\vec{e_2} =\begin{pmatrix} 0 \\ 1 \end{pmatrix}$

これらを基底にした場合、

Pの座標が(1, 2)であればk = 1, l = 2、 (2, 1)ならk = 2, l = 1ですね。

以下の計算からわかると思います。

$\vec{OP}=k\begin{pmatrix} 1 \\ 0 \end{pmatrix}+l\begin{pmatrix} 0 \\ 1 \end{pmatrix}$

$\vec{OP}=\begin{pmatrix} k \\ 0 \end{pmatrix}+\begin{pmatrix} 0 \\ l \end{pmatrix}$

これら $\vec{e_1}, \vec{e_2}$ は標準基底といいます。

続いて、以下のベクトルを基底にした場合を考えます。

$\vec{a} =\begin{pmatrix} 2 \\ 1 \end{pmatrix}$

$\vec{b} =\begin{pmatrix} 1 \\ 2 \end{pmatrix}$

ちなみにこれらはナイトの動きをベクトルで表したものだと考えてください。

$\vec{OP}=k\begin{pmatrix} 2 \\ 1 \end{pmatrix}+l\begin{pmatrix} 1 \\ 2 \end{pmatrix}$

$\vec{OP}=\begin{pmatrix} 2k \\ k \end{pmatrix}+\begin{pmatrix} l \\ 2l \end{pmatrix}$

では、k = 1, l = 0 を代入してみましょう。

$\vec{OP}=\begin{pmatrix} 2 \\ 1 \end{pmatrix}+\begin{pmatrix} 0 \\ 0 \end{pmatrix}$

となり、(2, 1)の座標が得られます。

k = 0, l = 1 を代入すれば、(1, 2)が得られ、

k = 1, l = 1 を代入すれば、(3, 3)が得られます。

つまり、kまたはlにプラス1するということはナイトを1手動かすと考えることができるので、動かした任意の手数に応じた座標を得ることができます。

（図があれば起きていることを一発で理解できると思うんですが、用意できなくて申し訳）

問題文では、x, yが与えられるので、

与えたれた任意のx, yを、ナイトの動きをベクトルとして考えた新しい基底での座標に変換できると問題を解くことができます。

例えば、

x, y = (2, 1)の場合は、新しい基底では(1, 0)
x, y = (1, 2)の場合は、新しい基底では(0, 1)
x, y = (3, 3)の場合は、新しい基底では(1, 1)

のように変換したいわけです。

結論を言うと、基底の取替え行列があれば計算で変換することができます。

基底の取替え行列とは

R²の基底{ $\vec{a}, \vec{b}$ }から基底{ $\vec{c}, \vec{d}$ }への基底の取替え行列P

( $\vec{c}$ $\vec{d}$ ) = ( $\vec{a}$ $\vec{b}$ ) P

がある。座標平面上の点が、それぞれの基底のもと、

x $\vec{a}$ + y $\vec{b}$ = k $\vec{c}$ + l $\vec{d}$

と表されるとき、

$(x, y)_{ab}$

から

$(k, l)_{cd}$

を求めるには、

$P^{-1}\begin{pmatrix} x \\ y \end{pmatrix}=\begin{pmatrix} k \\ l \end{pmatrix}$

とすればよい。