[Atcoder]ABC086C – Traveling [Ruby] | プログラミングな日常

問題
自分の答え
余談

問題

シカの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くんの旅行プランが実行可能かどうか判定してください。

入力例

入力例
2
3 1 2
6 1 1
出力例
Yes

自分の答え

def trabeling(t2,x2,y2)
  t1,x1,y1 = 0,0,0
  t = t2 - t1
  d = (x2 - x1).abs + (y2 - y1).abs
  if d <= t && (t - d).even?
    t1 = t2
    x1 = x2
    y1 = y2
  else
    puts "No"
    exit
  end
end

number = gets.to_i
number.times do
  t2,x2,y2 = gets.chomp.split(" ").map(&:to_i)
  trabeling(t2,x2,y2)
end
puts "Yes"

今回のもとても難しかったです。ただ、わかってしまえば、何も難しいことをする必要はありませんでした。

Noとなる条件は二つあります。”目的地までの移動回数より、移動可能回数が少ない時”と”目的地に到達した時点で残り移動可能回数が奇数の時”です。この二つの場合を除けばいいのです。わかりづらいので、詳しく説明したいと思います。

1.目的地までの移動回数より、移動可能回数が少ない時

これは単純で、例えば、(0,0)から(100,0)に行くには100回移動しなくてはいけません。それに対して、移動可能回数、この問題であれば時刻tiの数が100より小さい時はたどり着けないので、答えはNoとなります。コードで言うと、d <= tの部分になります。

2.目的地に到達した時点で残り移動可能回数が奇数の時

この問題は、最短距離で目的地まで行き、残り移動可能回数が偶数であればYesとなります。途中の移動の仕方などは考慮しなくても大丈夫なのです。

目的地に着いた時点で、残り移動可能回数が偶数であれば一歩進んで一歩戻るを繰り返せばいいのです。しかし、奇数だった場合、一歩余ってしまいます。なので、残り移動可能回数が奇数の時は失敗となるので、除外しなければなりません。コードで言うと、(t – d).even?になります。

除外する条件は上記の二つになります。この事にさえ気づけさえすれば、簡単な問題です。僕は気づけませんでした!