ABC189E - Rotate and Flip

考え方

$\mathrm{op}_{1}, (\mathrm{op}_{2} \circ \mathrm{op}_{1}),..., (\mathrm{op}_{M} \circ \cdots \circ \mathrm{op}_{1})$に対応する変換行列を予め計算しておけば良さそうであることはわかる．

ベクトル$\begin{pmatrix} x \\ y \end{pmatrix}$の回転だけでなく平行移動も考える場合は，代わりに$\begin{pmatrix} x \\ y \\ 1 \end{pmatrix}$を使うと３次元行列で表せる（アフィン写像 - Wikipedia）．
クエリ1は

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

クエリ2は

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

となる．

クエリ3 pは$x$方向に$-p$平行移動してから$x=0$に対して反転させ，$x$方向に$p$平行移動させればよい．

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

クエリ4 pはクエリ3 pの$x$と$y$を入れ替えれば良いから，

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

となる．

回答例

numpyだとTLEするため，1次元配列でPyPyを使う方針に（【参考】【Python】ABC189 解説）．

通るが遅い．もっと高速化したい．

N = int(input())
P = [list(map(int, input().split())) + [1] for _ in range(N)]
M = int(input())
def dot(x, y):
    res = [0] * 9
    for i in range(3):
        for j in range(3):
            for k in range(3):
                res[3 * i + j] += x[3 * i + k] * y[3 * k + j]
    return res

matrix = [[1, 0, 0, 0, 1, 0, 0, 0, 1]]
now = [1, 0, 0, 0, 1, 0, 0, 0, 1]
for _ in range(M):
    op = list(map(int, input().split()))
    if op[0] == 1:
        now = dot([0, 1, 0, -1, 0, 0, 0, 0, 1], now)
    elif op[0] == 2:
        now = dot([0, -1, 0, 1, 0, 0, 0, 0, 1], now)
    elif op[0] == 3:
        p = op[1]
        now = dot([-1, 0, 2 * p, 0, 1, 0, 0, 0, 1], now)
    else:
        p = op[1]
        now = dot([1, 0, 0, 0, -1, 2 * p, 0, 0, 1], now)
    matrix.append(now)

Q = int(input())
for _ in range(Q):
    A, B = map(int, input().split())
    ans = [0] * 3
    for i in range(3):
        for j in range(3):
            ans[i] += matrix[A][3 * i + j] * P[B - 1][j]
    print(*ans[:2])