N - Matrix Game Editorial by sotanishy
行列の行と列の並び替え及び転置によって勝敗が変化しないことは明らかなので，そのような操作によって一致する状態は全て同一視します．一般性を失わず， \(a\) が \(A\) の最小の要素であるとします．
結論だけ先に述べると，以下のようにして \(O(1)\) 時間で勝敗の判定ができます．
- \(a=d\) または (\(b=c<d\) かつ \(\left\lfloor \frac{a}{d-a} \right\rfloor = \left\lfloor \frac{b}{d-a} \right\rfloor\)) なら後手必勝
- それ以外は先手必勝
以下でこれを示します．証明の基本的なアイデアは，対角要素の遷移を追うことです．これは，終了状態が \(a=d=0\) であること，また 1 回の操作で対角要素の一方のみが必ず変化することが根拠です．
(証明)
先手必勝の状態の全体を \(\mathcal{N}\), 後手必勝の状態の全体を \(\mathcal{P}\) と表す．
補題 1
\(a\neq d\) かつ \(d \leq \max(b,c)\) であるような状態の全体を \(\mathcal{X}\), \(a=d\) であるような状態の全体を \(\mathcal{Y}\) とする．このとき，\(\mathcal{X}\subset \mathcal{N},\,\mathcal{Y}\subset \mathcal{P}\)
証明
要素の総和に関する帰納法で示す．終了状態の全体を $\mathcal{E}$ とすると， $\mathcal{E}$ は $a=d=0$ となる状態の全体である．明らかに $\mathcal{E}\subset \mathcal{Y}$ である．
次に， $\mathcal{X}$ に含まれる状態から $\mathcal{Y}$ に含まれる状態に遷移することが可能であることを示す．現在の状態を $\begin{pmatrix}a & b \\ c & d\end{pmatrix} \in \mathcal{X}$ とする．一般性を失わず， $c \geq b$ を仮定する．2 行目から $d - a > 0$ を引いて $\begin{pmatrix}a & b \\ c-d+a & a\end{pmatrix}$ と遷移することが可能である ( $c-d\geq 0$ であるからである)．帰納法の仮定よりこれは $\mathcal{Y}$ に含まれる．
次に， $\mathcal{Y}$ から遷移できる状態はすべて $\mathcal{X}$ に含まれることを示す．現在の状態を $\begin{pmatrix}a & b \\ c & a\end{pmatrix} \in \mathcal{Y}$ とする．1行目に対して操作をして $\begin{pmatrix}a-k & b-k \\ c & a\end{pmatrix}$ になったとすると， $A$ の最小の要素は $a-k$ であり， $a-k\neq a, a \leq c$ であるから，これは $\mathcal{X}$ に含まれる．他の操作を行ったとしても遷移先が $\mathcal{X}$ に含まれることは同様に示せる．
あとは， \(a\leq b<d,\,a\leq c<d\) の場合を判定できれば良い．
補題 2
\(a\leq b<d,\,a\leq c<d\) かつ \(b \neq c\) ならば \(A \in \mathcal{N}\)
証明
一般性を失わず $b < c$ とする．要素の総和に関する帰納法で示す．$A=\begin{pmatrix}a & b \\ c & d\end{pmatrix}$ から $B=\begin{pmatrix}a & b \\ b & d-c+b\end{pmatrix}$ に遷移することができる． $B\in \mathcal{P}$ ならば $A\in \mathcal{N}$ である． $B\in \mathcal{N}$ とする．すると， $B$ から遷移できる状態であって $\mathcal{P}$ に含まれるもの $C$ が存在する． $C$ の対角要素の組で等しいものが存在しないと仮定すると，補題 1 および帰納法の仮定より $C\in \mathcal{N}$ となり矛盾である．よって $C$ の対角要素の組で等しいものが存在する． $B$ に操作をして $(1,2)$ 成分と $(2,1)$ 成分を等しくすることはできないので， $C$ の $(1,1)$ 成分と $(2,2)$ 成分が等しくなるはずである．$d-c+b>c-c+b=b\geq a$ だから，$C$ としてあり得るのは $C=\begin{pmatrix}a & b \\ c-d+a & a\end{pmatrix}$ のみである． $A\rightarrow C$ と直接遷移することが可能なので，結局 $A\in \mathcal{N}$ である．
残っているのは \(a\leq b=c<d\) のケースのみである．このような状態において，調べる必要のある遷移は高々 1 通りしかない．なぜならば，対角要素を等しくする遷移 \(\begin{pmatrix}a & b \\ b & d\end{pmatrix} \rightarrow \begin{pmatrix}a & b \\ b-d+a & a\end{pmatrix}\) 以外の遷移先はすべて \(\mathcal{N}\) の要素であるからである．もう一度 (可能ならば) 遷移すると \(\begin{pmatrix}a & b \\ b-d+a & a\end{pmatrix}\rightarrow \begin{pmatrix}2a-d & b-d+a \\ b-d+a & a\end{pmatrix}\) となり，これは \(A\) のすべての要素から \(d-a\) を引いたものとなる．よって， \(a\) を \(d-a\) で割った商を \(q\), あまりを \(r\) として， \(A=\begin{pmatrix}a & b \\ b & d\end{pmatrix}\) と \(A'=\begin{pmatrix}r & b-(d-a)q \\ b-(d-a)q & r+d-a\end{pmatrix}\) の勝敗は一致する． \(b-(d-a)q<d-a \Leftrightarrow \lfloor \frac{b}{d-a} \rfloor \leq \lfloor \frac{a}{d-a} \rfloor\) ならこれ以上対角要素を等しくする遷移は行えず， \(A'\in \mathcal{P}\) である．そうでないならあと 1 回遷移が行えるので \(A'\in \mathcal{N}\) である．
posted:
last update: