OUPC2022 C「Clock」解説

はじめに

「Clock」writerのshinchanです。
問題文が短く、行列累乗で解ける問題を作りたいと思ってたら思いつきました。

解法1 (行列累乗を用いた解法)

$t$ 秒後の針の先端の座標を $(x_t, y_t)$ とします。

\begin{pmatrix}
x_{t+1} \\
y_{t+1} \\
\end{pmatrix}
=
A
\begin{pmatrix}
x_t \\
y_t \\
\end{pmatrix}

となるような $A$ を考えます。$A$ をさらに、$\sqrt{2}$ 倍の拡大と $45$ 度の回転操作に分解すると、前者は実数で、後者は回転行列で表すことができ、$A$ はそれらの積です。つまり、以下のようになります。

A=\sqrt{2}
\begin{pmatrix}
\cos(45°) & -\sin(45°)\\
\sin(45°) & \cos(45°)\\
\end{pmatrix}
=\sqrt{2}
\begin{pmatrix}
\frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}}\\
\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\\
\end{pmatrix}
=
\begin{pmatrix}
1 & -1\\
1 & 1\\
\end{pmatrix}

したがって、$(x_T, y_T)$ は次式で求めることができます。

\begin{pmatrix}
x_{T} \\
y_{T} \\
\end{pmatrix}
=
\begin{pmatrix}
1 & -1\\
1 & 1\\
\end{pmatrix}^T
\begin{pmatrix}
x_0 \\
y_0 \\
\end{pmatrix}
=
\begin{pmatrix}
1 & -1\\
1 & 1\\
\end{pmatrix}^T
\begin{pmatrix}
X \\
Y \\
\end{pmatrix}

$A^T$ は行列累乗で mod を考慮しながら計算することができます。
以上のようにして、問題が解けました。

解法2 (複素数を用いた解法)

$t$ 秒後の針の先端の座標 $(x_t, y_t)$ を、複素数を用いて、 $z_t = x_t + y_t i$ と表します。
$z_{t+1} = C z_t$ となる複素数 $C$ を考えると、$C = \sqrt{2} e^{i \frac{\pi}{4}} = 1 + i$ となります。
したがって、$z_T = C^T z_0 = C^T (X + Y i)$ は、 $C^T$ を繰り返し二乗法を用いて求めることで、mod を考慮しながら計算することができます。
以上のようにして、問題が解けました。

解法3 (T の mod 4 や mod 8 に注目する解法)

本問題は行列累乗や複素数を知らなくても解くことができます。
$45$ 度の回転のみに注目します。すると、例えば $4$ 秒後は原点対称の位置に移動するだけであり、$8$ 秒後には元に戻ります。このように、$T\mod 4$ や $T\mod 8$ に注目することで、繰り返し二乗法を用いる箇所は、針の長さの変化だけとなります。この操作をすると、$0$ 秒以上 $8$ 秒未満の範囲の計算だけが残り、mod さえ考慮すれば愚直に計算することができます。

いずれの解法でも時間計算量は $O(\log T)$ となります。