AtCorderで自分が間違えた問題集

解答:

# nはただ、入力するだけ。 => 後の処理では使わない。
n = gets.to_i

#aに配列が格納される
a = gets.split.map(&:to_i)

count = 0

# .all?(&:even?) 配列の要素全てが偶数か判定
while a.all?(&:even?)

 # { |x| x / 2 }  => 引数xを受け取ってxを2で割った数を返す
 #  a = [1, 2, 3, 4, 5]
 #  b = a.map { |x| x * 2 }
 # mapメソッドは{}の処理をして新しい配列をbに返す

  a = a.map { |x| x / 2 }
  count += 1
end

puts count

考え方:

各地点に訪れる順場が決まっており、次の地点に移動するには前の地点に到着する必要がある。現在地から上下左右のいずれか1つ進む。
判断方法は、

• その地点の到着時刻を超えていないかどうかを確認する。
• 到着する座標が、その地点の座標から 1 以上離れているかどうかを確認する。

例: (x, y)にいる時の時刻(t+1)の時

• (x+1, y), (x-1, y), (x, y+1), (x, y-1)のいずれかとなる。

(x-i, y-i)を訪れる予定がある時

• 時刻t-i以前に(x-1, y-1), (x_2, y_2), (x_{i-1}, y_{i-1})のいずれかに存在していなければならない。

• 存在することができる点は、前後の時刻に訪れた点からの上下左右のいずれかに限られる

• 時刻t+1に点(x+1, y), (x-1, y), (x, y+1), (x, y-1)$のいずれかに存在することができるかどうかを判定すれば良い

解説:

n = gets.to_i

# AtCoDeerくんが訪れる予定の位置と時刻を、配列として保持する
plans = []
plans << [0, 0, 0]  # 初期位置
n.times do
  t, x, y = gets.split.map(&:to_i)
  plans << [t, x, y]
end

#入力例:
# 3
# 1 2 3
# 1 2 4
# 1 7 8
# [[0, 0, 0], [1, 2, 3], [1, 2, 4], [1, 7, 8]]



# AtCoDeerくんが旅行プランに従って移動することができるかどうかを判定する
(1...n+1).each do |i|

  #plansのi-1番目の要素をt1, x1, y1の3つの変数に代入
  t1, x1, y1 = plans[i-1]
  
  # #plansのi番目の要素をt2, x2, y2の3つの変数に代入し
  t2, x2, y2 = plans[i]

  # (x2 - x1).absはx座標の差の絶対値を表し、(y2 - y1).absはy座標の差の絶対値を求める。
  dist = (x2 - x1).abs + (y2 - y1).abs  # 二点間の距離

  # 移動できない場合
  if (t2 - t1) < dist || (t2 - t1 - dist) % 2 == 1
    puts "No"
    exit
  end
end

puts "Yes"

何故、移動出来ない条件が↓のような条件式なの🤔

if (t2 - t1) < dist || (t2 - t1 - dist) % 2 == 1

時刻tに(x, y)にいる時、次の時刻t+1には(x+1, y) (x-1, y) (x, y+1) (x, y-1)のいずれかにいる。
つまり、次の時刻にはx方向, y方向のどちらか1だけ進める。

ここで、時刻t1に(x1, y1)にいて時刻t2に(x2, y2)に行くには

(x2 - x1).abs + (y2 - y1).absの距離を移動する必要がある。

また、distとt2-t1の差が奇数の場合偶数回で目的地には着けないので実現不可能である。

例: 移動距離が3で到達時刻が4の時
(x1,y1) -> (x1+1,y1) -> (x1+2,y1) -> (x1+1,y1) -> (x1,y1)のように移動を2回行っても目的地に到達できない。
移動距離と到達時刻の差が偶数の場合、AtCoDeerくんは偶数回の移動で目的地に到達できるため、実現可能。