2011年4月30日土曜日

TopCoder SRM179 Div2 250pts

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

問題のおおまかに説明する。

配列scoresの各要素に対して順位を計算する。順位を決める際には直近のk個のデータと比較する。このとき、全体の順位の合計を計算して返すメソッドcalcRanksを作成せよ。

例えば、scores[]={3,3,2}でk=1としたら、先頭の要素は1位、2番目の要素は先頭と同点なので1位、3番目の要素は2番目と比較して小さいので2位となり、順位を合計すると1+1+2=4になる。

public class OnLineRank {
 public int calcRanks(int k, int[] scores) {
  int sumRank=0;
  int start;
  int tmpRank=1;
  for( int i=0 ; i<scores.length ; i++){
   start = i-k>=0?i-k:0;
   tmpRank = 1;
   for( int j=start ; j<i ; j++){
    if( scores[j]>scores[i] ){
     tmpRank++;
    }
   }
   sumRank += tmpRank;
  }
  return sumRank;
 }
}

得点は209.43/250。解答のポイントは先頭の要素がkに足りないときの例外的な処理の部分である。あとは同点の場合の順位の処理で間違えないことと思われる。特に悩むことはなく素直に実装できた。ただし点数はあまり高くないが(2部リーグの回答者の平均より少し速い程度)。

0 件のコメント:

コメントを投稿

フォロワー

ページビューの合計