問題
シカのAtCoDeerくんは二次元平面上で旅行をしようとしています。 AtCoDeerくんの旅行プランでは、時刻 0 に 点 (0,0) を出発し、 1 以上 N 以下の各 i に対し、時刻 ti に 点 (xi,yi) を訪れる予定です。
AtCoDeerくんが時刻 t に 点 (x,y) にいる時、 時刻 t+1 には 点 (x+1,y), (x−1,y), (x,y+1), (x,y−1) のうちいずれかに存在することができます。 その場にとどまることは出来ないことに注意してください。 AtCoDeerくんの旅行プランが実行可能かどうか判定してください。
解法
https://atcoder.jp/contests/abc086/submissions/4775730
時刻 t で (x, y) にいて時刻 nextT で (nextX, nextY) に行くことを考える。
t 回の移動で次の点まで届かない場合はこのプランは実行不可能であることは明らかである。
その場にとどまることは出来ないことに注意してください とあるとおり、仮に距離的にたどり着くことが可能だったとしても、シカくんが時刻 t ピッタリに次の点に行けるとは限らない。
ある時刻に次の点までたどりといたら、「右にひとつ動いて、また戻って」を繰り返せばいい。なので、とりあえず次の点にたどり着き、「右にひとつ動いて、また戻って」を繰り返して時間が来るのを待てばいいわけだ。
しかしここで問題になるのは、「右にひとつ動いて、また戻って」は2ターン使ってしまう。なので、次の点に到着したときの残り時間は偶数でないと目的の点に戻ってこられなくなってしまうのだ。
ということで、次の点に到達するまでの最短の時間を計算し、残り時間が偶数であれば実行可能。そうでなければ実行不可能である。
