AtCoder RC089 C: Traveling

問題

C - Traveling
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

時刻が1進む毎に上下左右のいずれかに1進めるので、次の場所に進むことを考えると

・次の場所との距離(X座標とY座標の差の絶対値の和)が時刻の差に等しい

がまず最もシンプルな条件になります。

また、時刻の差が距離より大きい場合は、一旦次の場所に着いてから「隣の座標に移って戻る」を繰り返せば良いので

・次の場所との距離(X座標とY座標の差の絶対値の和)と時刻の差が正の偶数である

というのがもう一つの条件になります。

上記の条件に合うかどうかを順次チェックしていけば解けます。

実装

t = Array.new
x = Array.new
y = Array.new

t[0] = x[0] = y[0] = 0

STDIN.gets
STDIN.each_line do |line|
    n = line.chomp.split(' ')
    t.push(n[0].to_i)
    x.push(n[1].to_i)
    y.push(n[2].to_i)
end

for i in 0..t.size-2

    dist = (x[i+1] - x[i]).abs + (y[i+1] - y[i]).abs
    if dist > (t[i+1] - t[i]) || (t[i+1] - t[i] - dist) % 2 == 1 then
        puts "No"
        exit
    end
end
puts "Yes"

コメント

タイトルとURLをコピーしました