TopCoder SRM401 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題文について説明する。

ジョンはフィールドテックという会社で働いている。そして今日、ジョンは仕事後にとても疲れていたので、家に帰るとすぐに眠ってしまった。不幸なことに、寝ている時でさえもジョンは仕事のことが忘れられなかった。夢の中で、ジョンは人参栽培を行っている会社から以下の問題に対処するように頼まれた。2つの人参を結ぶ直線状に何本の人参が育てられるだろうか?ただし端点の人参は除くものとして考える。これはかなり変な問題であるが、さらに問題を変なものにしていることとして、会社の代表はすべての人参は無限の広さを持つ平面で育ち、1つの格子点(訳注：座標が整数の箇所のこと)に1つの人参だけ育てられるということを述べた。あなたはこの問題に対処する疲れ切ったジョンを助けなければならない。

2本の端点の人参の座標を(x1, y1), (x2, y2)としたときに、これらの位置を結ぶ線分上で育てられる人参の数を返すメソッドを作成せよ。

public class DreamingAboutCarrots {

 public int carrotsBetweenCarrots(int x1, int y1, int x2, int y2) {
  int num = Math.abs(y2 - y1);
  int denom = Math.abs(x2 - x1);
  int step = gcd(num, denom);
  return step-1;
 }
 private static int gcd(int a, int b){
     return b == 0 ? a : gcd(b, a % b);
 }
}

得点は191.09/250、1回のsubmitでシステムテストクリア。中央値は約142点。結局x、y方向の座標の差を計算し、その値の最大公約数-1が答えになる。短いコードでかける気持ちのいい問題。当日の正解率は34%台と難しめ。