2011年4月28日木曜日

TopCoder SRM177 Div2 250Pts

本日の問題はこちら(要TopCoder登録 & 問題文は英語)。

問題のおおまかな訳は以下の通り。

階段のデザインの組み合わせについて実装する。階段は一定の(蹴上げの)高さと一定の(踏面の)幅を持つものとする。いま、階段の高さの合計をtotalHeight、幅の合計をtotalWidthとする。高さの上限はmaxHeight、幅の下限はminWidthとする。デザインする階段の高さ、幅は共に正の整数とする。totalHeight、totalWidth、maxHeight、minWidthが与えられたときに、階段を設計するする方法は何通りあるかを返すメソッドdesignsを作成せよ。

私の回答は以下の通り。

public class Stairs {
 public int designs(int maxHeight, int minWidth, int totalHeight, int totalWidth) {
  int raiser, treads;
  int n = 0;
  for( int i=1 ; i<=totalWidth/minWidth ; i++){
   treads = i; # 踏面の数
   raiser = i+1; # 蹴上の数
   if( totalWidth%treads != 0 ) continue; # 踏面の幅は整数でなければならない
   if( totalHeight/raiser <=maxHeight){ # 蹴上の高さは上限以下で、整数でなければならない
    if( totalHeight%raiser == 0  ){
     n++;
    }
   }
  }
  return n;
 }
}

踏面の数は1から最大でtotalWidth/minWidthになる。また、階段の蹴上げの数は踏面の数より1だけ大きいということに気付けば実装ができる。

得点は190.80/250(バグなしにするまで20分弱)。最初、高さと幅が整数でなければならないということに気付かず、回答が遅くなってしまったのが悔やまれる。

0 件のコメント:

コメントを投稿

フォロワー

ページビューの合計