TopCoder SRM229 Div2 250Pts

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

ゲームではハイスコアを記録していることがよくある。ハイスコアは降順にスコアをならべたものである。例えば100,90,90,30など。これを順位に直すと、1,2,2,4のようになる。同点はとりうる順位候補の中で一番小さい順位にする。ハイスコアを記録する数placesと既存のハイスコアscores[](ソート済)と新しい記録newscoreが入力されたときに、newscoreが何位になるかを返すメソッドを作成せよ。ただし、placesに入れない場合は-1を返すようにせよ。また、同点の場合は、後ろに並べられると考える。このことについては次の例を見て欲しい。

scores[]={5,4,3,2,1}、newscore=1、places=5とすると、1は5位タイになるが、その値はplaces=5になっているため、scoresの中に追加できないので-1を返すことになる。またscores[]={}、newscore=4、places=2とするとscoresは空なので1位となり1が返される。

私の解答は以下の通り。

public class Highscore {
 public int getRank(int[] scores, int newscore, int places) {
  int rank = 0;
  boolean isIn = false;
  if( scores.length == 0 ) return 1;
  for( int i=0 ; i<scores.length ; i++ ){
   if( newscore > scores[i] && isIn == false ){
     return i+1; // いきなり上回った
   }else if( newscore == scores[i] && isIn == false ){
    rank = i+1;
    // 同点が出てきた && まだランキングに入れられる
    if( scores.length < places) return rank; 
    isIn = true;
   }else if( newscore > scores[i] && isIn == true ){
    return rank; // 同点が出てきたのち、途中で上回った(scores.length == placesだよ!)
   }
  }
  // 同点も、いきなり上回ることもなかったら、最後に入れられるかチェック
  if( scores.length < places ) return scores.length+1;
  return -1;
 }
}

得点は75.00/250、再提出5回でようやくシステムテストを通過。中央値は約120点という難しめの問題。