B - Go Straight and Turn Right Editorial by cirno3153

\(90\) 度回転を簡便に実装する方法について説明します。

まず、Sによる移動量を \((dx, dy)\) として定義します。 初めは \((dx, dy) = (1, 0)\) です。

そして、Rが呼ばれる度に、 \((dx, dy) \leftarrow (dy, -dx)\) とすることで、正しく動作します。

N = int(input())
T = input()

x, y = 0, 0
dx, dy = 1, 0
for t in T:
  if t == 'S': x, y = x + dx, y + dy
  else: dx, dy = dy, -dx
print(x, y)

何故これが正しく動くのでしょうか？

これは、アフィン変換という概念を考えることで理解することができます。

まず、\((x, y)\) 方向への移動量を表すベクトルを \(\begin{pmatrix}x \\ y \\ 1 \\ \end{pmatrix}\) とします。( \(x, y\) だけでなく余分な情報として \(1\) が追加で付いていますが、これは気にしないでください。詳しく知りたい場合は同次座標系などで調べると良いです。)

ベクトルに対する平行移動や回転は行列を作用させることで表すことができ、次のように表すことができます。

平行移動

ベクトルを \(X\) 軸方向に \(T_x\) 、 \(Y\) 軸方向に \(T_y\) 移動させる変換行列は、以下のように表せます。

\( \begin{pmatrix} x' \\ y' \\ 1 \\ \end{pmatrix} = \begin{pmatrix} 1 & 0 & T_x \\ 0 & 1 & T_y \\ 0 & 0 & 1 - T_x - T_y \\ \end{pmatrix} \begin{pmatrix} x \\ y \\ 1 \\ \end{pmatrix} \)

拡大縮小

ベクトルを \(X\) 軸方向に \(S_x\) 、 \(Y\) 軸方向に \(S_y\) 拡大させる変換行列は、以下のように表せます。

\( \begin{pmatrix} x' \\ y' \\ 1 \\ \end{pmatrix} = \begin{pmatrix} S_x & 0 & 0 \\ 0 & S_y & 0 \\ 0 & 0 & 1 \\ \end{pmatrix} \begin{pmatrix} x \\ y \\ 1 \\ \end{pmatrix} \)

鏡映

ベクトルを直線 \(y=ax+b\) を基準に鏡像を取る変換行列は、以下のように表せます。

\( \begin{pmatrix} x' \\ y' \\ 1 \\ \end{pmatrix} = \begin{pmatrix} \frac{1-a^2}{a^2+1} & \frac{2a}{a^2+1} & \frac{-2ab}{a^2+1} \\ \frac{2a}{a^2+1} & \frac{a^2-1}{a^2+1/} & \frac{2b}{a^2+1} \\ 0 & 0 & \frac{a^2+2ab-2b+1}{a^2+1} \\ \end{pmatrix} \begin{pmatrix} x \\ y \\ 1 \\ \end{pmatrix} \)

回転

ベクトルを \(\theta\) 回転させる変換行列は、以下のように表せます。

\( \begin{pmatrix} x' \\ y' \\ 1 \\ \end{pmatrix} = \begin{pmatrix} \cos\theta & -\sin\theta & 0 \\ \sin\theta & \cos\theta & 0 \\ 0 & 0 & 1 \\ \end{pmatrix} \begin{pmatrix} x \\ y \\ 1 \\ \end{pmatrix} \)

ここで \(\theta=\frac{3\pi}{2}\) 、つまり右に \(90\) 度回転させると

\( \begin{pmatrix} x' \\ y' \\ 1 \\ \end{pmatrix} = \begin{pmatrix} 0 & 1 & 0 \\ -1 &0 & 0 \\ 0 & 0 & 1 \\ \end{pmatrix} \begin{pmatrix} x \\ y \\ 1 \\ \end{pmatrix} \)

となり、 \((x', y', 1)^{\top} = (y, -x, 1)^{\top}\) となることから元の問題で用いた手法が導かれます。

アフィン変換行列を覚えることで、解ける問題の幅は広がります。 この機会に、学んでみるのはいかがでしょうか？

練習問題

posted:
last update: