問題

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|$$
となります。そして仮に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
コメント