読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

SRM538 Div.1 Med(450) TurtleSpy

Div.1 Medium 初AC!

問題

TopCoder Statistics - Problem Statement

ロボットに以下の命令を送ることができる。

  • その場で左(右)に向きをx度変える(xは1以上359以下の整数)

  • 前(後ろ)に距離xだけ進む

使える命令文(「左に50度曲がる」など)が与えられるので、これらを組み合わせて到達できる点が初期地点から最も遠くなるようにしたときの距離の最大値を求めよ。

解法

以下のように進むと一番遠くまで行ける。

  1. 最初にまとめて前進

  2. 180度にできるだけ近くなるように回転

  3. まとめて後退

1は前進の距離を足し合わせるだけ。2は角度についてDPをして、180度に最も近いものを選べばよい。3は(後退する距離の和, 0)というベクトルを2の角度で回転させて前進した分のベクトルとの和を取れば最終地点がわかる。

入力の処理が面倒だったのでPythonで解いた。

class TurtleSpy:
    def maxDistance(self, commands):
        N = len(commands)
        c = [0] * N
        x = [0] * N
        forward = 0
        back = 0
        degs = []
        for i in range(N):
            s, t = commands[i].split()
            x[i] = int(t)
            if s[0] == "l":
                c[i] = 0
                degs.append(x[i])
            if s[0] == "r":
                c[i] = 1
                degs.append(360 - x[i])
            if s[0] == "f":
                c[i] = 2
                forward += x[i]
            if s[0] == "b":
                c[i] = 3
                back += x[i]

        dp = [[False] * 360 for i in range(len(degs) + 1)]
        dp[0][0] = True
        for i in range(len(degs)):
            for j in range(360):
                if dp[i][j]:
                    dp[i + 1][j] = True
                    dp[i + 1][(j + degs[i]) % 360] = True

        deg = 0
        for j in range(360):
            if dp[len(degs)][j]:
                if abs(j - 180) < abs(deg - 180):
                    deg = j

        deg = (deg + 180) % 360
        deg = deg * math.pi / 180.0

        v1 = complex(forward, 0)
        v2 = complex(back, 0)
        c = math.cos(deg)
        s = math.sin(deg)
        v2 = complex(v2.real * c - v2.imag * s, v2.real * s + v2.imag * c)
        v = v1 + v2

        return abs(v)

幾何やDPがさらっと複合されるあたり、さすがはmedという感じだろうか…。