TopCoder SRM304 Div2 250Pts

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

いくつかのサイズからなる絨毯が入荷されている。事実、縦と横の長さが同じ偶数でない整数以外の、任意の縦横の長さを持つ絨毯を見かけることができる。例えば4*4の絨毯は見かけられるが、2*4は長さが異なり、かつ偶数なので見つけられないことになる。ある領域が与えられたときに、いくつ絨毯の選択方法があるかということが知りたい。areaという面積を表す整数値が与えられたときに、その面積をきっかり覆う絨毯の選び方が何通りあるかを返すメソッドを作成せよ。なお、同じサイズのものは2回数えてはならない。つまり6*9と9*6は1回として数えよ。

私の解答はこちら。

public class RugSizes {

 public int rugCount(int area) {
  int cnt = 0;
  int mul = 0;
  // sqrtを取ればよいのは対称性を考慮したため
  // 実はfloorでなく、intへのキャストでOK
  for( int i=1 ; i<=Math.floor(Math.sqrt(area)) ; i++ ){
   if( area % i == 0 ){ // 絨毯のサイズは整数*整数に限られる
    mul = area/i; // iが1辺、mulが他辺を表す
    if( i == mul ){ 
     cnt++; // もし両方の辺の長さが等しければ
    }else if( i % 2 != 0 || mul % 2 != 0 ){
     cnt++; // 辺の長さが違い、かつともに偶数でない
    }
   }

  }
  return cnt;
 }

}

得点は235.98/250、中央値は約199点。同じものを数えないようにするために、areaの平方根を切り捨てた値まで検討すれば良いというのがポイント。