TopCoder SRM264 Div2 250Pts

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

ある先生が二つの成績をつける手法を思いついた。学生は点数を0～100の間で受ける。全学生の成績はscores[]という整数型配列で表され、昇順にソートされている。学生は最終的に0から8のグレードで評価される。先生は知的に各生徒に必要な成績を割り当てている。scoreのi番目の要素はi番目の要素のグレードに対応する。同じ点数の場合、グレードは高い方から低い方にソートされる。
最初の成績をつける方法では、ある学生にXという成績をつけたいと思った場合、それ以上の成績を持つ学生は少なくともX以上の成績になる。この制約はさておき、学生はとりうる中で最も低いグレードを付けられる。例えば、3人の学生の成績が{60,80,80}であり、先生が彼らに{3,8,6}というグレードを割り当てたいと思った場合、学生は{3,8,8}というグレードを受け取ることになる。3番目の学生は同じ点数の人で6より高い8という評価を受けている人がいるため、少なくとも8の成績を受け取ることになるからである。
2番目の方法では、ある学生にXという成績をつけたいと思った場合、その学生の点数以下の学生は最大でもXという評価しかしないというものである。先ほどの例では、3人の学生は{3,6,6}というグレードを受け取ることになる。というのも、2番目の学生は3番目の学生の評価に引きずられるからである。
二つの手法を適用し、各学生に対しグレードの差の絶対値を求め、その総和を返すようなメソッドを作成せよ。

私の解答はこちら。

public class GradingSystem {
 public int fairness(int[] scores, int[] grades) {
  int min = 8;
  int max = 0;
  int sMax = 0;
  int sMin = 0;
  for( int i=0 ; i<scores.length ; i++ ){
   max = Math.max(max, grades[i]);
   sMax += max;
  }
  for( int i=scores.length-1 ; i >= 0 ; i-- ){
   min = Math.min(min, grades[i]);
   sMin += min;
  }
  return Math.abs(sMax - sMin);
 }
}

この問題のポイントになるのは、同じ成績であれば、グレードは降順にソート済みであるということである。この条件により実装の量は少なくて済むようになっている。これに気付くのが遅かったため、コーディングにはかなり時間がかかりました。