TopCoder SRM449 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題文についておおまかに説明する。問題文には画像があるので、そちらを参考にしても良いかもしれない。

山登りをする友人がどれだけ山を歩くことになるかを知りたい。簡単のため2次元にして考える。横から見ると、山は直角三角形をしており、斜面が45度、頂上が90度になっているとする。友人は左から右方向に向かって、x軸方向に大きくなる方向に向かって歩いていく。山は必ず連なっており(2つ以上に分かれていない)、i番目の山のふもとの始点はstart[i]、終点はfinish[i]という位置が整数型の配列で与えられている(訳注：つまり、その2つの整数値の真ん中が山の頂上のある水平方向の位置になる)。友人はこれらの山の一番高い所に沿って歩く。山を左端から右端まで歩いたとき、その歩いた距離の合計を返せ。

私の解答はこちら。

import java.util.Arrays;

public class MountainRoad {

 public double findDistance(int[] start, int[] finish) {
  Arrays.sort(start);
  Arrays.sort(finish);
  int diff = start[0]-finish[finish.length-1];
  return Math.abs(diff)*Math.sqrt(2);
 }

}

どの山が一番高いかなんて考える必要はない。山が連なっているという条件から、水平方向に1歩くと45度の斜面を歩いているのだから、必ずルート2だけ歩くのである。従って、startの最小値とfinishの最大値を求めてその距離をルート2倍すればよい。