ログインしてください。
F - Push and Carry 解説
by
kyopro_friends
場合分けをあまり考える必要がない解法を説明します。
平行移動と反転により、目的地を原点、荷物がある位置を第一象限としてよいです。このとき、行動回数最小を達成する方法は次の2つのどちらかになります
- 荷物の \(x\) 座標が \(0\) でないなら下に押すことで \(0\) にする。その後、荷物の \(y\) 座標が \(0\) でないなら左に押すことで \(0\) にする。
- 荷物の \(y\) 座標が \(0\) でないなら左に押すことで \(0\) にする。その後、荷物の \(x\) 座標が \(0\) でないなら下に押すことで \(0\) にする。
(証明:「荷物を左に押し、そのあと下に押し、さらに左を押す」という箇所があれば、行動回数を増やすことなく「左左下」の順に入れ替えられる。下左下という箇所が存在する場合も同様)
荷物を下に押す方法を考えます。高橋君が座標 \((S_x,S_y)\)、荷物が \((T_x,T_y)\) にいる状態から始めて、荷物を \((T_x, 0)\) に移動させるためには、高橋君はまず \((T_x,T_y+1)\) に移動し、その後荷物を下へ \(T_y\) 回押すことになります。このときの \((S_x,S_y)\) から \((T_x,T_y+1)\) への移動は、この2点が軸に平行かつその間に荷物が存在しているときに限り、荷物を迂回するために余計な行動回数がかかり、そうでない場合は最短距離で移動できます。
軸を入れ替えることで左に押すことは下に押すこととみなせるので、同じロジックを使いまわすことができ、以下のように実装できます。
実装例(Python)
sx,sy,tx,ty,ux,uy=map(int,input().split())
# 平行移動と反転により、目的地を原点、荷物を第一象限にする
sx-=ux
sy-=uy
tx-=ux
ty-=uy
if tx<0:
sx*=-1
tx*=-1
if ty<0:
sy*=-1
ty*=-1
def push_down(sx,sy,tx,ty):
# 高橋君が(sx,sy),荷物が(tx,ty)にあるとき、荷物を(tx,0)に移動するまでの最小行動回数と、移動後の高橋君の座標、荷物の座標を返す
# ty==0なら何もしない
if ty==0: return 0, sx,sy, tx,ty
# (tx,ty+1)に行く
step=abs(sx-tx)+abs(sy-(ty+1))
# 荷物を迂回する必要があるなら+2
if sx==tx and sy<ty: step+=2
# 下に押す
return step+ty, tx,1, tx,0
ans=[]
for _ in range(2):
# 荷物を下→左の順に押す
# 荷物を下に押す
step1,a,b,c,d=push_down(sx,sy,tx,ty)
# 軸を入れ替えることで左に押すことを下に押すことに帰着
step2,*_=push_down(b,a,d,c)
ans.append(step1+step2)
# 軸を入れ替えることで左→下のケースを下→左に帰着
sx,sy=sy,sx
tx,ty=ty,tx
print(min(ans))
投稿日時:
最終更新: