Edit

【pythonでABC082を解説】D - FT Robot

問題概要

問題ページ

D - FT Robot
D - FT Robot

問題ページへ移動する

問題文

二次元平面の原点にロボットが置かれています。
最初、ロボットは \(x\) 軸の正の向きを向いています。

このロボットに命令列 \(s\) が与えられます。
\(s\) は次の \(2\) 文字のみからなり、先頭から末尾まで順に実行されます。

  • F : 今向いている向きに長さ \(1\) だけ移動する。
  • T : 時計回りまたは反時計回りの好きな方向に \(90\) 度だけ向きを変える。

ロボットの目標は、命令列をすべて実行し終わった後に座標 \((x, y)\) にいることです。
この目標が達成可能か判定してください。

制約

  • \(s\) は F, T のみからなる。
  • \(1 \leq |s| \leq 8\ 000\)
  • \(x\), \(y\) は整数である。
  • \(|x|, |y| \leq |s|\)

問題の考察

ACコード

import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    s = str(input().rstrip('\n')) + "T"
    x, y = list(map(int, input().rstrip('\n').split()))
    xl = collections.deque()
    yl = collections.deque()
    cnt = 0
    for i in range(len(s)):
        if s[i] == "T":
            if len(xl) == len(yl):
                xl.append(cnt)
            else:
                yl.append(cnt)
            cnt = 0
        else:
            cnt += 1

    xd = [collections.defaultdict(int)]
    xd[0][xl.popleft()]
    for i in range(len(xl)):
        xv = xl.popleft()
        d = collections.defaultdict(int)
        for k, v in xd[i].items():
            d[k + xv]
            d[k - xv]
        xd.append(d)

    yd = [collections.defaultdict(int)]
    yd[0][0]
    for i in range(len(yl)):
        yv = yl.popleft()
        d = collections.defaultdict(int)
        for k, v in yd[i].items():
            d[k + yv]
            d[k - yv]
        yd.append(d)
    print("Yes" if x in xd[-1] and y in yd[-1] else "No")


if __name__ == '__main__':
    solve()

-Edit
-