ABC035-B - ドローン を解く
ABC035-B - ドローン
なんか色々小難しそうな説明しているけれど
多分単純な問題だろう
'U', 'D', 'L', 'R', '?' からなる文字列Sが与えられる
原点 (0,0) スタートで 'U' なら上、 'D' なら下、 'L' なら左、 'R' なら右に移動
'?' の場合は 'U', 'D', 'L', 'R' のいずれか
原点からの距離が一番大きくなるパタンと小さくなるパタンを考える問題だ
距離は "マンハッタン距離" で答えるよう指定されている
(a,b) と (x,y) のマンハッタン距離は |x - a| + |y - b| で表すことができる
直線距離を求めるのと比べると計算は簡単だ
'?' を考慮するとやや複雑な話に見えるが…
まずは '?' が含まれない文字列が与えられた場合を考えてみる
これなら簡単に計算できる
左右と上下を x軸方向、y軸方向のように考えて
上方向、右方向を +
下方向、左方向を -
として考えてあげればいい
例えば S = 'ULRDULL' の場合
x軸方向には LRLL で (-3) + 1 = -2 （Rが+ Lが-）
y軸方向には UDU で +2 + (-1) = +1（Uが+ Dが-）
マンハッタン距離は |-2| + |+1| = 3
となる
'?' がなければ計算は簡単なので
とりあえず '?' の計算は最後にまとめて行うようにすればいい
「順番変えて大丈夫か？」と思いそうだが
'ULRDULL' を 'UUDLLLR' に並び替えてもマンハッタン距離は変わらない
大丈夫だろう
では、'?' の計算はどうするか？ という話だが
よく考えてみると '?' が 'U', 'D', 'L', 'R' のどれに該当するのか？は
あまり考える必要がないことに気づく
なぜなら、マンハッタン距離が最小の場合を求める場合は
'?' はマンハッタン距離が小さくなるような方向をとるはずだし、
マンハッタン距離が最大の場合を求める場合は
'?' はマンハッタン距離が大きくなるような方向をとるはずだ
例えば、'?' 以外の移動処理が全て完了した後の座標が (3,5) で
'?' が 1個ある場合を考える
このとき、マンハッタン距離が最大になるよう移動した場合
移動後の座標は (4,5) か (3,6) のどちらかになる
つまり、マンハッタン距離は 8 → 9 と +1 になるように動くはず
最小の場合はこれの逆で、 -1 になるように動くはずだ
以上より、まずは '?' 抜きでマンハッタン距離の計算を行い
最後に '?' の個数分足すか引くかしてあげればよさそうだ
…と思ったが、一つ考慮漏れがある
例えば、マンハッタン距離が 3 で、'?' が 4個ある場合などは
距離の最小はどうなるか？
'?' が5個ある場合、6個ある場合は？
'?' の回数が マンハッタン距離を上回る場合は注意が必要だ
'?' の回数とマンハッタン距離の左が奇数の場合は、どうやっても 0 にできない
偶数の場合は移動を上手く調整して 0 にできる
（調整のイメージは隣接する2点間をひたすら往復するイメージ）
よって、'?' の個数が マンハッタン距離を上回り
距離の最小を求める場合のみ、場合分けをして処理を書いていく
提出したコード
# 入力 S=input() T=int(input()) # '?'の数を数えるカウンタ c=0 # x軸方向、y軸方向の距離（初期値は原点） x=y=0 for a in S: if a=='R': x+=1 elif a=='L': x-=1 elif a=='U': y+=1 elif a=='D': y-=1 # '?'の場合 else: c+=1 # マンハッタン距離を算出 d=abs(x)+abs(y) # 最大値を出力する場合 if T==1: print(d+c) # 最小値を出力する場合 else: # '?'の数がマンハッタン距離より大きい場合 if d<c: # 差が偶数なら最小値は0にできる if (c-d)%2==0: print(0) # 差が奇数なら最小値は頑張っても1まで else: print(1) else: print(d-c)
提出結果はACでした
