TopCoder SRM183 Div2 350Pts

あー、前回の300点問題よりもまた難しくなってるよ～と思いながら開いた今回の問題。
今回の問題はこちら(要TopCoder登録 & 問題文は英語)。

今回の問題は数を数えるゲームの必勝法について。普通は、自分と相手が1からgoalまで、順にmaxAddまで数えられるという形式であるが、さらに自分がnextの数から数えるということになっている。もし自分がgoalの数を言うことができ、ゲームに勝てるとしたら、自分は最初にnextから数えるとして、いくつの数字を言えばよいか返すメソッドを作成せよというのが問題である。

例えばgoal=20、maxAdd=3、next=10とするのであれば、自分は20を言えば勝ち、16を言えば勝ち、12を言えば勝ちになるので、10、11、12と3つコールすれば勝つことができ、3を返すことになる。もし、どうあがいても勝てない場合は-1を返す。

ゲームに勝つためにここでコールを止めればよいという数字は、goal、goal-(maxAdd+1)、goal-2*(maxAdd+1)、...となっていることに注意。

私の最終的な実装は下のようになった。残念ながら、最初の提出ではシステムテストをクリアできなかった。

public class CountGame {

 public int howMany(int maxAdd, int goal, int next) {
  // これが言えたら勝ちという数字でnext以上の最小値を求める
  while(true){
   if( goal-(maxAdd+1)<next ){
    break;
   }
   goal -= maxAdd+1;
  }
  // 言えたら勝ちという数字は自分がコールできる範囲の値か?
  if( next+maxAdd-1>=goal ) return goal-next+1;
  return -1;
 }

}

システムテストで引っかかったのは、maxAdd=8、goal=1000、next=1のケースだった。間違いの原因はwhile文の中にあるif文で等号をつけていたことである。

得点はシステムテストに一発で通らなかったので、参考までに。再提出でシステムテストをクリアした時点で158.19/350。上のコードに書き直した時点で、105/350である。最初は冗長なコードだったけど、最終的にはスマートになったかな?