AtCoder Begginers Selection "Traveling"
なんとかクリアした。
問題としては、
時刻t に座標p = (x, y)にいてて、時刻t2に座標p2 = (x2, y2)にちょうどその場所に存在することができるかという問題。
時刻が1つ進むごとに、x軸、y軸のいずれかで必ず正負いずれかの方向に1進まないといけない(同じ場所にとどまることはできない)。
とりあえず、時間内にp2まで到達できるかを調べないといけないので、許容移動時間と最短到達距離を求めてみる
許容移動時間はt2 - t
最短到達距離は「(x2 - x)の絶対値」 +「(y2 - y)の絶対値」。マイナス方向にも1移動できるので、移動距離は絶対値で取らないといけない。
ここで移動時間のほうが、最短到達距離よりも大きい場合は、そもそも到達できないので、ダメということが分かる。時速1キロで歩いている人が5時間後に10キロ地点に到達しないのと同じことです。
それ以外の場合は、とりあえず目的地まではたどり着けるということ。ただし、問題はここからで、時刻が1つ進むたびに必ず1マス移動しないといけないので、到達できても時刻t2にその場所に居られるかはわからない。なので、それを調べる。
まず、残り時間の確認。目的地に到達してから、時刻t2までの残り時間は許容移動時間-最短到達距離で求められる。この残り時間で同じ場所にとどまることができるのか。ここから気づくまでが長かった…
時刻が1つ進むたびに、x軸、y軸いずれかで必ず正負の方向に1つ進まないといけない、ということは、偶数時間の場合は正の方向への移動距離と負の方向への移動距離を相殺させて同じ場所に帰ってくることができるけど、残り時間が奇数時間の場合は、相殺できず(正負の何れかの方向に1進んでしまう)同じ場所にとどまることができない。
なので、それをそのまま判定方法にもちいればOK。
提出したコードは次の通り
# シカのAtCoDeerくんは二次元平面上で旅行をしようとしています。 # AtCoDeerくんの旅行プランでは、時刻 0 に 点 (0,0) を出発し、 1 以上 N 以下の各 i に対し、時刻 ti に 点 (xi<200b>,yi) を訪れる予定です。 # AtCoDeerくんが時刻 t に 点 (x,y) にいる時、 時刻 t+1 には 点 (x+1,y), (x−1,y), (x,y+1), (x,y−1) のうちいずれかに存在することができます。 # その場にとどまることは出来ないことに注意してください。 AtCoDeerくんの旅行プランが実行可能かどうか判定してください。 def traveling(time1, x1, y1, time2, x2, y2): travelingTime = time2 - time1 xsum = abs(x2 - x1) ysum = abs(y2 - y1) totalDistance = xsum + ysum # 総移動距離 if travelingTime < totalDistance: # 最短距離で移動しても時間的に間に合わない ret = False elif (travelingTime - totalDistance) % 2 == 1: # 目的地に最短で移動して、奇数時間残っている # ⇒同じ場所にとどまれないためNG ret = False else: # 目的地について偶数時間残っている # ⇒右+左、上+下の繰り返しで同じ場所にとどまれる ret = True return ret ans = "Yes" timeMax = int(input()) time1 = 0 time2 = 0 x1, x2, y1, y2 = 0, 0, 0, 0 for i in range(timeMax): time2, x2, y2 = map(int, input().split()) if traveling(time1, x1, y1, time2, x2, y2) == False: #print("timw1: {} time2: {}",time1, time2) ans = "No" break time1 = time2 x1 = x2 y1 = y2 print(ans)