2012年9月17日月曜日

TopCoder SRM425 Div2 250Pts

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

nという正の整数がproper factorであるというのは、nがaの倍数で、かつaが1でもnでもないということを指す。ある数nのproper factorのすべての要素が含まれている、factors[]という2以上の整数が含まれるリストが与えられる。このとき、nを求めて返すメソッドを作成せよ。

私の解答はこちら。

public class InverseFactoring {

 public int getTheNumber(int[] factors) {
  long proper = 1;
  long max = -1;
  long min = Long.MAX_VALUE;
  for( int i=0 ; i<factors.length ; i++ ){
   proper = lcm(proper, factors[i]); // 全部の数の最小公倍数を計算
   max = Math.max(max, factors[i]);
   min = Math.min(min, factors[i]);
  }
  // factorの全要素の最小公倍数が最大値そのものになったら、
  // 最大値はproper factorではないので、最小値だけ掛けてproper factorを求める。
  return proper == max ? (int)proper * (int)min : (int)proper;
 }

 static long gcd(long a, long b){ // 最大公約数
  return b == 0 ? a : gcd(b, a % b);
 }

 static long lcm(long a, long b){  // 最小公倍数
  return a * b / gcd(a, b);
 }
}

得点は200.54/250、2回目のsubmitでシステムテストクリア。仮定としてfactorsは妥当なものしか入らないので、上のような実装は不要で、factorsの最小値*最大値で導出ができるとのこと。

0 件のコメント:

コメントを投稿

フォロワー

ページビューの合計