AtCoder RC093 C: Traveling Plan

問題

C - Traveling Plan

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

解法

観光スポットに行かないケースを毎回計算していると、O(n^2)の計算量になってしまいます。

そこで以下のように考えます。

観光地が5カ所の場合、全ての観光地に行くケースの総距離は、

$$総距離 = |A_2 – A_1| + |A_3 – A_2| + |A_4 – A_3| + |A_5 – A_4|$$

となります。そして仮にA₃に行かないとすると

$$A_3に行かない場合 = |A_2 – A_1| + |A_4 – A_2| + |A_5 – A_4|$$

となります。これは以下のように総距離からの計算することが出来ます。

$$A_3に行かない場合 = 総距離 – |A_3 – A_2| – |A_4 – A_3| + |A_4 – A_2|$$

よって、事前に総距離を計算しておけば、各ケースは定数時間で算出することが可能です。

なお、以下の実装では配列の先頭と末尾に座標0を設定することで、実装をシンプルにしています。

実装

gets
x = Array.new
x[0] = 0
gets.chomp.split(' ').each{|n| x.push(n.to_i)}
x.push(0)

total_dist = 0
for i in 0..(x.size-2)
  total_dist += (x[i+1] - x[i]).abs
end

for i in 1..(x.size-2)
  p total_dist - (x[i+1] - x[i]).abs - (x[i] - x[i-1]).abs + (x[i+1] - x[i-1]).abs
end