2012年9月4日火曜日

TopCoder SRM421 Div2 250Pts

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

あなたはジムにおり、トレーニングをしたいと思っている。トレーニングは1分間単位に分けられる。1分間ごとに、運動あるいは休憩のどちらかを取ることができる。もし、トレーニングを1分間することにすれば、心拍数がtrainChangeだけ上昇する。つまり、もし、ある時点での心拍数がXであれば、運動した1分後にはX+trainChangeになrということである。心拍数はmaxPulseという上限を超えて欲しくはないので、X+trainChangeがmaxPulse以下になるときに限って運動を行うことができる。もし、1分間休憩することにすれば、restChangeだけ心拍数を下げることになる。つまり、ある時点の心拍数がXであれば、休憩を1分した後には心拍数がX-restChangeになるということである。しかしながら、心拍数はminPulseを下回ることはなく。X-restChangeがminPulse未満になるようであれば、心拍数はminPulseになる。初期状態におけるあなたの心拍数をminPulseとする。そして、needToTrainという時間だけ運動を行いたいものとする(連続で行う必要はない)。それだけのトレーニングを行うのに最小限必要となる時間を返すメソッドを作成せよ。なお、needToTrain分間の運動ができないようであれば、-1を代わりに返すようにすること。

私の実装はこちら。

public class GymTraining {

 public int trainingTime(int needToTrain, int minPulse, int maxPulse, int trainChange, int restChange) {
  int currentPulse = minPulse;
  int currentTime = 0;
  int currentTrainTime = 0;

  // 失敗する場合の条件チェック
  if( minPulse + trainChange > maxPulse ) return -1;
  while( true ){
   // 休憩と運動の選択
   // maxPulseを上回らないようであれば、運動を選択することで、時間を最小化できる
   if( currentPulse + trainChange <= maxPulse ){
    currentPulse += trainChange;
    currentTime++;
    currentTrainTime++;
    if( currentTrainTime >= needToTrain ) break;
   }else{
    int next = currentPulse - restChange;
    currentPulse = next >= minPulse ? next : minPulse;
    currentTime++;
   }
  }
  return currentTime;
 }

}

得点は230.67/250、1回のsubmitでシステムテストクリア。中央値は約188点。

0 件のコメント:

コメントを投稿

フォロワー

ページビューの合計