ABC051 C - Back and Forth

AtCoder Python3

備忘録

問題

atcoder.jp

回答

import sys
import os

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    sx, sy, tx, ty = il()

    ret = ''
    for n in range(ty - sy): ret += 'U'
    for n in range(tx - sx): ret += 'R'
    for n in range(ty - sy): ret += 'D'
    for n in range(tx - sx): ret += 'L'

    ret += 'L'
    for n in range(ty - sy + 1): ret += 'U'
    for n in range(tx - sx + 1): ret += 'R'
    ret += 'D'
    ret += 'R'
    for n in range(ty - sy + 1): ret += 'D'
    for n in range(tx - sx + 1): ret += 'L'
    ret += 'U'

    print(ret)


if __name__ == '__main__':
    main()

考え方

条件としてsx < tx, sy < tyとなっている。
そのため、平面上の位置関係は常に、
点(sx, sy)の右上に点(tx, ty)が存在している。
そのため、(sx, sy)から(tx, ty)までに到達するための最短距離は

  • 点(sx, sy)のy軸を点(tx, ty)に揃えるため、上(U)にty - sy回移動
  • 点(sx, sy)のx軸を点(tx, ty)に揃えるため、上(R)にtx - sx回移動

することで到達することができる。
戻るときは同じ回数DとL移動するだけ。

2往復目は初めの経路を避けるために、一つ外にずれる必要があることに注意する。