AtCoder RC093 C: Traveling Plan

AtCoder 競技プログラミング

問題

https://arc093.contest.atcoder.jp/tasks/arc093_a

解法

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

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

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

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

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

$$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