ABC189 E - Rotate and Flip 雑記

あらすじ

atcoder.jp

問題を解いたのですが公式解説に書かれていた知識を持っておらず、回り道をしていたので思考過程のメモをしました。
なお該当のコンテストには出ておらず、「線形変換」というキーワードは目にした状態でスタートしていました。

問題概要

二次元平面上にN個の駒 (x_i, y_i)が置かれている。
以下のうち一つを行う、という操作が合計M回行われる。

  • 平面全体を時計回りに90度回転
  • 平面全体を反時計回りに90度回転
  • すべての駒を x = pに対して対称な位置に移動
  • すべての駒を y = pに対して対称な位置に移動

Q 個のクエリに答える。

  • A回目の操作が行われた直後にB番目の駒はどこにあるか。

1 \le N, M, Q \le 10^ 5
10^ {-9} \le x_i, y_i, p \le 10^ 9

解法概要

各クエリに対してシミュレーションをすると間に合わない。
4つの操作は全て平面に対する線形変換なので、変換行列の積を取ることで複数回の連続する操作をまとめて1度の変換で行うことができる。

公式解説

Editorial - AtCoder Beginner Contest 189 を見てください

4つの操作はそれぞれ、 座標を表すベクトル (x, y, 1)^ T に対して


\begin{pmatrix}
0&1&0\\
-1&0&0\\
0&0&1
\end{pmatrix}
\begin{pmatrix}
0&-1&0\\
1&0&0\\
0&0&1
\end{pmatrix}
 \begin{pmatrix}
-1&0&2p\\
0&1&0\\
0&0&1
\end{pmatrix}
\begin{pmatrix}
1&0&0\\
0&-1&2p\\
0&0&1
\end{pmatrix}

(追記)

上の変換行列の導出を教えてもらいました。

同時座標系という手法を用いることで平行移動を(ベクトルではなく)行列で表現することができ、以下に書かれているのと同じような平行移動->対称移動->平行移動の操作を一つの行列にまとめることができる、という話でした。

自分の考察

※まず変換行列は2×2だと思っている

それぞれの変換が行列で表せれば累積積で各クエリに対して O(1)で対処できる

回転行列はわかるが、鏡写しの場合が分からない(ググったが雑過ぎて引っかからず)

x=pではなくy軸対称の変換なら


 \begin{pmatrix}
-1&0\\
0&1\\
\end{pmatrix}

で表せて嬉しい。

なので、一度平行移動により対称移動の軸がy軸と重なるようにして、上記行列を作用させた後に平行移動を元に戻す。

例: (2, -1) を x=3に対して対称な位置へ


(2, -1) - (3, 0) = (-1, -1)    \\\\

\\\\

 \begin{pmatrix}
-1&0\\
0&1\\
\end{pmatrix}
(-1, -1)^ T = (1, -1)^ T    \\\\

\\\\

(1, -1) + (3, 0) = (4, -1)

左右対称移動について一般化


A = 
 \begin{pmatrix}
-1&0\\
0&1\\
\end{pmatrix}
,
x = (x, y)^ T
,
b = (p, 0)^ T

として、移動後の座標を x'とすると


x' = A(x - b) + b  \\\\


   = Ax -Ab + b

変換前の座標に依存しない部分を -Ab + b = b'と定義して、 x` = Ax + b'

複数回の変換

y = p_1 を軸とした対称変換の後に y = p_2を軸とした対称変換をするとどうなるか


A_1 = A_2 = 
 \begin{pmatrix}
-1&0\\
0&1\\
\end{pmatrix}
,
x = (x, y)^ T
,
b_1 = (p_1, 0)^ T
,
b_2 = (p_2, 0)^ T

とする。(後々の一般化のために、A_1とA_2は別物としている)


A_2(A_1 (x - b_1) + b_1 - b_2) + b_2 \\\\

= A_2(A_1x - A_1 b_1 + b_1 - b_2) + b_2  \\\\

= A_2 (A_1 x - b'_1 -b_2) + b_2  \\\\

= A_2 A_1 x - A_2(b'_1 + b_2) + b_2

で結局、初期値を


A_0 = 
 \begin{pmatrix}
1&0\\
0&1\\
\end{pmatrix}
,
b_0 = (0, 0)^ T

とすると、 i 回目までのすべての変換による結果を表す行列およびベクトルは


A’_i = A_i A'_{i-1}  \\\\

b'_i = -A_i(b'_{i-1} + b_i) + b_i

の漸化式で表せる。

実装上は累積積(のようなもの)を保持する配列を2つ用意して末尾に逐次pushしていけばいいので、 M回分の操作に対してO(M)で前計算することができる。

4つの操作に対する一般化

前節までは左右対称の変化のみを扱っていたが、他の操作に対しても


A = 
 \begin{pmatrix}
0&1\\
-1&0\\
\end{pmatrix}
,
b = (0, 0)^ T  (時計回り) \\\\

A = 
 \begin{pmatrix}
0&-1\\
1&0\\
\end{pmatrix}
,
b = (0, 0)^ T  (反時計回り) \\\\

A = 
 \begin{pmatrix}
-1&0\\
0&1\\
\end{pmatrix}
,
b = (p, 0)^ T  (左右対称) \\\\

A = 
 \begin{pmatrix}
1&0\\
0&-1\\
\end{pmatrix}
,
b = (0, p)^ T  (上下対称) \\\\

と定義することでそのまま使うことができる。

前述のとおり O(M)で前計算し、Q個のクエリに対してそれぞれO(1)で答えることでACすることができる。

解答

Submission #19659845 - AtCoder Beginner Contest 189

(累積積を持っているということは、時刻 l - rでの変換を切り取るとかもできそうですが、逆行列がなかったりする場合もあるのかな)

免責

数学の議論とはてなブログの記法に疎いため、数式のふりをしたただのお気持ち表明が多くなっています、すみません。