AtCoder Beginner Contest 189 E - Rotate and Flip (diff: 1526)

線形代数をサボったため行列がなんか括弧の中に数字がいっぱい入っている人向けに書こうかと。

すなわち僕向けです・・・

行列をほぼ初めから調べたので間違っている部分もあるかもしれません。その時はそっと教えて頂けると助かります。。。

思考回路

全点について操作が行われるので愚直に操作した場合は$\mathcal{O}(NM+Q)$になる。操作 1,2 に着目してみると、これは前計算で$i$回目の操作後の角度を持っておけば良さそう！

後は操作$3,4$もこんな感じに前計算で持っていければハッピーだけど、どうやるのこれ・・・・

⇛ 解説みたらアフィン変換で解けるらしい。へぇ。

解説が読めないくらいの知識なので行列もまとめて理解し直してみる。

解説

画像の拡大縮小、回転、平行移動などをまとめて３×３の行列を使って変換する事をアフィン変換と呼びます。

引用: アフィン変換　画像処理ソリューション

なにかの画像の左下を(0,0), 右上を(x,y)と考えると、(x,y)をいい感じに変換出来れば画像処理が出来そうです。

方針

問題文中の 4

操作 1,2 について考えてみる。

• 操作 1: 原点を中心に時計回りに 90 度回転させた位置に移動する

極座標を覚えていますか？これは原点からの距離と角度を用いて座標を表す方法です。僕は覚えていませんでした。

直行座標$(x,y)$に対して操作 1 を行った後の座標について$(x',y')$とする。

直交座標$(x,y)$の極座標表示を$(r,\theta)$とする。(1)操作後は直交座標表示で$(x',y')$とする。

(1)から、時計回りに 90 度回転させた位置は

$x' = r\cos{\theta + \frac{\pi}{2}}$

コサインの加法定理から

$x' = r(\cos {\frac{\pi}{2}} \cos {\theta} - \sin{\frac{\pi}{2}}\sin{\theta})$

$x' = -r\sin{\theta}$

ここで、$y = r\sin{\theta}$なので$x' = -y$

次に$y'$についても求めてみる。

$y' = r\sin{\theta + \frac{\pi}{2}}$

サインの加法定理から、

$y' = r(\sin{\theta}\cos{\frac{\pi}{2}}+\cos{\theta}\sin{\frac{\pi}{2}})$

$y' = r\cos{theta}$

ここで、$x = r\cos{\theta}$なので

$y' = x$

これで求まりました。ただ、これを予め前計算しておくとなると、どのように書けばいいか分かりません。そこで行列のアイデアが出てきます。

$x'$の計算をするために$y$が必要。$y'$の計算に$x$が必要なのでまとめて計算が出来る行列の仕組みを持ってくるイメージをしています。

行列の掛け算は以下のように表されます。

それぞれ、行列$A,B$をそれぞれこのように定義します。

$$A = \begin{pmatrix} a & b & c\\ d & e & f \\ g & h & i \\ \end{pmatrix}$$

$$B = \begin{pmatrix} j & k & l\\ m & n & o \\ p & q & r \\ \end{pmatrix}$$

行列の掛け算$AB$はこのようになります。

$$AB = \begin{pmatrix} aj + bm + cp & ak + bn + cq & al + bo + cr \\ dj + em + fp & dk + en + fq & dl + eo + fr \\ gj + hm + ip & gk + hn + iq & gl + ho + ir \\ \end{pmatrix}$$

この性質を利用して座標変換を行列で表したいとします。
座標(x,y)を三次元に拡張して座標(x,y,1)で持つ事にします。(三次元に拡張すると水平移動が出来るようになるため、余分な一次元を追加します。詳しくは: 参考記事のアフィン変換/平行移動だって変換行列で - Qiitaをご覧ください)
そして操作後の座標を(x',y',1)としてみる。

とりあえず変換に利用する行列を

$$Y = \begin{pmatrix} a & b & c \\ d & e & f \\ g & h & i \end{pmatrix}$$

として

$$Y \begin{pmatrix} x \\ y \\ 1 \end{pmatrix} = \begin{pmatrix} x' \\ y' \\ 1 \end{pmatrix}$$

として、操作1,2について、対応する$Y$を良い感じに見つけていきます。

$$\begin{pmatrix} x' \\ y' \\ 1 \end{pmatrix} = \begin{pmatrix} ax + by + c \\ dx + ey + f \\ gx + hy + i \end{pmatrix}$$

$g,h = 0$

$i = 1$

$c,f = 0$

とします。

操作1,2をまとめて表現したいので回転する角度を$z$として,$x = r\cos{\theta}$, $y = r\sin{\theta}$とする。

$x' = r(\cos{z} \cos {\theta} - \sin{z}\sin{\theta})$

$y' = r(\sin{\theta}\cos{z}+\cos{\theta}\sin{z})$

から

$x' = x\cos{z} - y\sin{z}$

$y' = y\cos{z} + x\sin{z}$

である。

よって、

$$\begin{pmatrix} x' \\ y' \\ 1 \end{pmatrix} = \begin{pmatrix} \cos{z} & - \sin{z} & 0 \\ \sin{z} & + \cos{z} & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} x \\ y \\ 1 \end{pmatrix}$$

完成！

これで操作1と操作2を行列の掛け算で表すことが出来るようになりました。

操作3,4もこんな感じで行列の掛け算で表すことが出来るようになれば完全に勝利です。

操作3 について考えてみる。

先程のように操作に利用する行列を

$$Y = \begin{pmatrix} a & b & c \\ d & e & f \\ g & h & i \end{pmatrix}$$

として

$$Y \begin{pmatrix} x \\ y \\ 1 \end{pmatrix} = \begin{pmatrix} x' \\ y' \\ 1 \end{pmatrix}$$

として、操作3について、対応する$Y$を良い感じに見つけていきます。

初めに$x = p$について対称移動することを考えると、y座標の移動は起こらず、x座標だけが移動されます。

また移動先のx座標は$x^{\prime} = x-2(x-p)$ , すなわち $x^{\prime} = -x +2p$ になります。

よって。

$$\begin{pmatrix} x' \\ y' \\ 1 \end{pmatrix} = \begin{pmatrix} ax + by + c \\ dx + ey + f \\ gx + hy + i \end{pmatrix}$$

から $a = -2$,$b = 0$, $c = 2p$, $d = 0$, $e = 1$, $f = 0$, $g = 0$, $h = 0$, $i = 1$となります。よって、

$$\begin{pmatrix} x' \\ y' \\ 1 \end{pmatrix} = \begin{pmatrix} -2 & 0 & 2p \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{pmatrix} \begin{pmatrix} x \\ y \\ 1 \end{pmatrix}$$

完成！

操作4 について考えてみる。

先程のように操作に利用する行列を

$$Y = \begin{pmatrix} a & b & c \\ d & e & f \\ g & h & i \end{pmatrix}$$

として

$$Y \begin{pmatrix} x \\ y \\ 1 \end{pmatrix} = \begin{pmatrix} x' \\ y' \\ 1 \end{pmatrix}$$

として、操作3について、対応する$Y$を良い感じに見つけていきます。

初めに$y=p$について対称移動することを考えると、x座標の移動は起こらず、y座標だけが移動されます。

また移動先のy座標は $y' = y-2(y-p)$ , すなわち$y' = -y + 2p$になります。

よって。

$$\begin{pmatrix} x' \\ y' \\ 1 \end{pmatrix} = \begin{pmatrix} ax + by + c \\ dx + ey + f \\ gx + hy + i \end{pmatrix}$$

から $a = 1$,$b = 0$, $c = 0$, $d = 0$, $e = -2$, $f = 2p$, $g = 0$, $h = 0$, $i = 1$となります。よって、

$$\begin{pmatrix} x' \\ y' \\ 1 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & -2 & 2p \\ 0 & 0 & 1 \\ \end{pmatrix} \begin{pmatrix} x \\ y \\ 1 \end{pmatrix}$$

完成！

最後に

操作1,2,3,4について操作を行列で表すことが出来たので前計算で行列の累積積を求めておけば解けます！

解答コード

e.cpp

#include <bits/stdc++.h>

#define INF 1e9
#define INFLL 1ull<<60u
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()
#define endl "\n"

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
typedef long long ll;

using vi = vector<ll>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vpii = vector<pair<ll,ll>>;

vvi matrix_product(vvi a,vvi b) {
    vvi matrix(3,vi(3,0));
    REP(i,3)REP(j,3)REP(k,3) {
        matrix[i][j] += a[i][k] * b[k][j];
    }
    return matrix;
}

void solve() {
  
     const auto op1 = []()-> vvi {
        vvi matrix(3,vi(3,0));
        matrix[0][1] = 1;
        matrix[1][0] = -1;
        matrix[2][2] = 1;
        return matrix;
    }();
  
    const auto op2 = []()-> vvi {
        vvi matrix(3,vi(3,0));
        matrix[0][1] = -1;
        matrix[1][0] = 1;
        matrix[2][2] = 1;
        return matrix;
    }();

    const auto gen_op4 = [](int p)-> vvi {
        vvi matrix(3,vi(3,0));
        matrix[0][0] = 1;
        matrix[1][1] = -1;
        matrix[1][2] = 2 * p;
        matrix[2][2] = 1;
        return matrix;
    };

    const auto gen_op3 = [](int p)-> vvi {
        vvi matrix(3,vi(3,0));
        matrix[0][0] = -1;
        matrix[0][2] = 2 * p;
        matrix[1][1] = 1;
        matrix[2][2] = 1;
        return matrix;
    };



    int N; cin >> N;
    vpii pieces(N);
    REP(i,N) {
        int X,Y; cin >> X >> Y;
        pieces[i] = make_pair(X,Y);
    }

    vvi matrix(3,vi(3,0));
    
    // 正則行列にする。
    REP(i,3) matrix[i][i] = 1;

    int M; cin >> M;
    
    // x回目の累積積
    vvvi states(M+1,vvi(3,vi(3,0)));
    states[0] = matrix;

    FOR(i,1,M+1) {
        int op; cin >> op;
        if (op == 1) states[i] = matrix_product(op1,states[i-1]);
        else if (op == 2) states[i] = matrix_product(op2,states[i-1]);
        else if (op == 3) {
            int p; cin >> p;
            states[i] = matrix_product(gen_op3(p),states[i-1]);
        }
        else if (op == 4) {
            int p; cin >> p;
            states[i] = matrix_product(gen_op4(p),states[i-1]);
        }
        else assert(false);
    }

    int Q; cin >> Q;
    REP(_,Q) {
        int A,B; cin >> A >> B; --B;
        
        vvi piece_matrix(3,vi(3,0));
        piece_matrix[0][0] = pieces[B].first;
        piece_matrix[1][0] = pieces[B].second;
        piece_matrix[2][0] = 1;

        auto ans = matrix_product(states[A],piece_matrix);
        cout << ans[0][0] << " " << ans[1][0] << endl;
    }
}

int main() {
    solve();
    return 0;
}

提出 #19842729 - AtCoder Beginner Contest 189

参考

• アフィン変換　画像処理ソリューション
• 逆三角関数 - Wikipedia
• 行列の積
• アフィン変換/平行移動だって変換行列で - Qiita