これは何？
AtCoderという競技プログラミングサイトの練習問題についての私の解答です。
残念ながら自力で解けず、参考サイトを大いに参考にして書きました。
（参考サイトのコードをRubyコードに置き換えて申し訳程度に修正しただけとも言う）
問題はこちら。
https://atcoder.jp/contests/abs/tasks/arc089_a
解答
n = gets.to_i
t_list = [0]
x_list = [0]
y_list = [0]
n.times do
t, x, y = gets.chomp.split.map(&:to_i)
t_list << t
x_list << x
y_list << y
end
i = 0
reachable = true
while i < n do
dt = t_list[i + 1] - t_list[i]
dist = (x_list[i + 1] - x_list[i]).abs + (y_list[i + 1] - y_list[i]).abs
if (dt < dist) or (dt % 2) != (dist % 2) then
reachable = false
break
end
i += 1
end
if reachable then
puts 'Yes'
else
puts 'No'
end
基本的な考え方
- 次に到達するべき座標への距離と、移動距離との兼ね合いで到達可否が決まる
- 座標への距離に対して移動距離が足りなければもちろんNG
- 座標への距離と移動距離が同じならもちろんOK
- 座標への距離に対して移動距離が大きければ、それぞれの偶奇が一致していればOK、そうでなければNG（偶奇が一致していれば、同じ場所で行ったりきたりして移動距離を調節できるため）
実装について
- dtが移動距離
- 時間が1増えた際に移動する距離は1なので、tは移動距離に等しい
- distが座標への距離
- t_list、x_list、y_listについてダミーデータとして0を先頭に入れている
- i + 1というアクセスをするため、配列の要素数はnより1大きくないといけない