AtCoder ABC 035 B – ドローン Python解説

スポンサーリンク

ドローン

無限に広い二次元グリッドの原点 (0, 0) に高橋君と 1 台のドローンがいます。このドローンは文字列が与えられた時、文字列の先頭から末尾までのそれぞれの文字を 1 つの命令と解釈して順に実行します。命令は以下の 4 種類です。

L 現在のドローンの位置を (x, y) として (x-1, y)  に移動する
R 現在のドローンの位置を (x, y) として (x+1, y) に移動する
U 現在のドローンの位置を (x, y) として (x, y+1) に移動する
D 現在のドローンの位置を (x, y) として (x, y-1)  に移動する

今、ドローンに何らかの命令が与えられ、どこかへと移動しました。高橋君はドローンに送られた命令を表す文字列である S を手に入れたものの、いくつかの箇所は破損し?になり分からなくなってしまいました。ただし、?が元々はLRUDのいずれかの文字だったことが分かっています。

ドローンと高橋君の距離はドローンの位置を (x,y) としてマンハッタン距離x∣+∣yで表されます。求める値の種類を表す整数 T が与えられるので、移動を終えたあとのドローンと高橋君の距離としてありうる値のうち、 T=1 ならば最大値を、 T=2 ならば最小値を求めてください。

AtCoder Beginner Contest 035 「ドローン」

まずは、?以外の移動を終えたドローンのマンハッタン距離を求めます。
T = 1のときは最大値を求めるので、ドローンのマンハッタン距離に?の数を加えた値が答えとなります。

T = 2のときはマンハッタン距離から?の数を引くのですが、?の数によっては原点を通り過ぎてしまうので、?の数がマンハッタン距離より小さければ、マンハッタン距離から?を引いた値、大きければ原点か1の場所にいます。

s = input()
t = int(input())

x, y = 0, 0
unknown = 0
for i in s:
    if i == "L":
        x -= 1
    elif i == "R":
        x += 1
    elif i == "U":
        y += 1
    elif i == "D":
        y -= 1
    elif i == "?":
        unknown += 1

if t == 1:
    ans = abs(x) + abs(y) + unknown
    print(ans)
else:
    # *1
    ans = abs(x) + abs(y)
    for _ in range(unknown):
        if ans >= 0:
            ans -= 1
        else:
            ans += 1
    print(abs(ans))

(*1)T = 2のときは、?(変数unknown)の数だけfor文を回しています。
マンハッタン距離が0以上なら-1減らし、マイナスになったら1足しています。

s = input()
t = int(input())

x, y = 0, 0
unknown = 0
for i in s:
    if i == "L":
        x -= 1
    elif i == "R":
        x += 1
    elif i == "U":
        y += 1
    elif i == "D":
        y -= 1
    elif i == "?":
        unknown += 1

if t == 1:
    ans = abs(x) + abs(y) + unknown
    print(ans)
else:
    ans = abs(x) + abs(y)
    if ans >= unknown:
        print(abs(ans - unknown))
    else:
        # *2
        if (unknown - ans) % 2 == 0:
            print(0)
        else:
            print(1)

上記のコード(*2)、 ?の数によっては原点を通り過ぎてしまうのですが、?とマンハッタン距離の差分が偶数なら原点にいられるので0を、奇数なら原点にいられないので1を出力するようにしています。