paiza Aランクレベルアップ問題集【座標系での向きの変わる移動】解いてみたPart2【Python3】

はじめに

4問目がFinal問題より難しく感じました

• 解いてみたPart1

• 問題文

STEP: 1 マップからの座標取得

• 問題文

位置を取得するだけなので多次元配列に慣れていれば特に難しくないはず...

step1.py

def int_input():
    return [int(i) for i in input().split()]


def main():
    line = int_input()
    h_rows, w_columns = line[0], line[1]

    for h in range(h_rows):
        line = input()
        for w in range(w_columns):
            if line[w] == '#':
                return f'{h} {w}'


if __name__ == '__main__':
    print(main())

STEP: 2 座標系での移動・方角

• 問題文

step2.py

import numpy as np


def int_input():
    return [int(i) for i in input().split()]


def move(d): # 南北東西の向きをベクトルで考える
    if d == 'N':
        return np.array([-1, 0])
    elif d == 'S':
        return np.array([1, 0])
    elif d == 'E':
        return np.array([0, 1])
    else:
        return np.array([0, -1])


def main():
    line = int_input()
    y_0, x_0, n_num = line[0], line[1], line[2]

    d_move = []
    for n in range(n_num):
        d_move.append(input())

    vector = np.array([y_0, x_0])

    for d in d_move:
        vector += move(d)
        print(f'{vector[0]} {vector[1]}')


if __name__ == '__main__':
    main()

まだまだシンプルな問題だと思います｡ Numpyを使わなくてもこれくらいの問題ならば解けますが､ 以後の問題で回転行列を使うとスムースに解ける問題が出てくるので､ 回転行列が扱いやすいNumPyには慣れておきたいです｡

STEP: 3 座標系での移動・向き

• 問題文

step3.py

import numpy as np


def move(d):
    if d == 'N':
        return np.array([-1, 0])
    elif d == 'S':
        return np.array([1, 0])
    elif d == 'E':
        return np.array([0, 1])
    else:
        return np.array([0, -1])


def main():
    line = input().split()
    y_0, x_0, direction = int(line[0]), int(line[1]), line[2]
    d_move = input()

    vector = np.array([y_0, x_0])
    r_move = np.array([[0, 1], [-1, 0]]) # θ=-π/2 の回転行列
    l_move = np.array([[0, -1], [1, 0]]) # θ=π/2 の回転行列
    if d_move == 'R':
        vector += r_move @ move(direction) # 回転行列の計算を行ってる
    else:
        vector += l_move @ move(direction)
    print(f'{vector[0]} {vector[1]}')


if __name__ == '__main__':
    main()

回転した際の座標系の変換には行列の考えが多くの場合有用です｡ とくに90度回転する系の回転行列は頻出なので攻略しておきです(暗記しなくてもググったらいつでも使えるくらいには理解していたい)｡ 3次元での回転を表す際は複素数の拡張である四元数を用いると幸せになれるらしいです｡

• 回転行列の表式と導出（2次元・3次元）

STEP: 4 座標系での規則的な移動

• 問題文

step4.py

import numpy as np


def int_input():
    return [int(i) for i in input().split()]


def rotation(move):
    return np.dot([[0, -1], [1, 0]], move)


def main():
    line = int_input()
    x_0, y_0, n_max = line[0], line[1], line[2]
    
    vector = np.array([x_0, y_0])
    move = np.array([1, 0])
    cnt = 0 # 同じ方向で進んだ回数を記録する
    flag = 0 # 同じ距離の進行でターンした回数
    l = 1 # ターンするまでの距離
    # nからターンするか否かを判定する関数を作る場合二次方程式をnごとに解くことになる

    for n in range(n_max):
        vector += move
        cnt += 1
        if cnt >= l:
            cnt = 0
            if flag == 0: # lが増えない場合
                flag = 1
                move = rotation(move)
            else:
                l += 1 # lが増える場合
                flag = 0 # lが増えたのでカウントをリセットする
                move = rotation(move)

    print(f'{vector[0]} {vector[1]}')


if __name__ == '__main__':
    main()

考え方はいろいろあると思うが､ 自分の中でどのアルゴリズムを用いて解くかを明白にしないと解けない､ Bランクらしい難易度の問題です｡ せっかく前問で回転行列を導入したので､ ここでは回転行列を用いた方法で解いていこうと思います｡

図1

問題を読めば移動に図1のような規則性があることがわかります｡ つまり回転までの移動距離が下図のような規則性をもってることがわかります｡

図2

1\quad1\quad2\quad2\quad3\quad3\quad4\quad\dots\\
\rightarrow

もちろんこれは等差数列を二回繰り返してるだけの数列なのでnをもとに何回回転してるかを求めることもできますが､ その方法だと二次方程式を解くことになり少し面倒です(試行回数が非常に多い場合ならばこのような解析的手法が有用なことも多いですが)｡
回転を行う度に1をプラスする変数(この場合cnt)を用意することで場合分けが可能です｡ また回転は全て時計回りなのでθ=-π/2の回転座標で考えれば問題ないです｡ ただどの手法を用いてもある程度沢山の変数と分岐を使わないといけないのでこれまでの問題よりはやや難しいといえると思います｡

-Final問題- 座標系での向きの変わる移動

• 問題文

step5.py

import numpy as np


def move(vector, f, d):
    if d == 'R':
        v = np.array([[0, -1], [1, 0]])
    else:
        v = np.array([[0, 1], [-1, 0]])
    f = v @ f # 正面の方向(ベクトル)を回転行列で求める
    vector += f # 回転したあとの方向へ進む
    return vector, f


def main():
    x_0, y_0, n_num = [int(i) for i in input().split()]
    # vector, f, d でそれぞれ座標､ 正面のベクトル､ 左右を表す
    vector = np.array([x_0, y_0])
    f = np.array([0, -1])

    for _ in range(n_num):
        d = input()
        mv = move(vector, f, d)
        vector, f = mv[0], mv[1]
        print(f'{vector[0]} {vector[1]}')


if __name__ == '__main__':
    main()

ベクトルの考え方に慣れてさえいれば､ 座標と向きのベクトルをごっちゃにしてはいけない等ハードルはありますが､ 前問よりは簡単かと思います｡ step3での考えを繰り返すだけで解けます｡

終わりに

ただ解くだけではなく､ 考えをまとめるのは楽しいです｡