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 を手に入れたものの、いくつかの箇所は破損し
?になり分からなくなってしまいました。ただし、?が元々はL、R、U、Dのいずれかの文字だったことが分かっています。ドローンと高橋君の距離はドローンの位置を (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を出力するようにしています。