このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題文についておおまかに説明する。
あなたの語学学校は新しいセメスターを始めていて、各生徒は時間割を決めなければならない。groups[]というi番目の要素がi番目のスケジュールの受講者数を表す整数型の配列が与えられる。学校には各スケジュールに割り当てられる受講生の数はminSize以上maxSize以下でなければならないというルールがある。しかしながら、このルールは登録段階では適切に満たされていない。あなたのやることはルールが満足されるように学生のスケジュールを割り当てなおすことである。再割り当てというのは、ある学生の受講スケジュールを別の時間に振り変えることである。さて、再割り当てしなければならない学生の人数の最小値を返すメソッドを作成せよ。ただし、もしそのようなルールを満たすことができなければ-1を返すこと。スケジュールを新しく加えたり、存在しているスケジュールは削除しないことにも注意。
私の解答はこちら。
public class CreateGroups {
public int minChanges(int[] groups, int minSize, int maxSize) {
int[] range = new int[2];
range[0] = minSize * groups.length;
range[1] = maxSize * groups.length;
int total = 0; // 総受講者数
for( int i=0 ; i<groups.length ; i++ ){
total += groups[i];
}
// -1になるのは受講者数の合計がminSize*授業数未満、あるいは
// maxSize*授業数より大きいをみたすときである。
if( total < range[0] || total > range[1] ) return -1;
int[] diff = new int[2];
for( int i=0 ; i<groups.length ; i++ ){
if( groups[i] < minSize ){
diff[0] += minSize - groups[i];
}else if( groups[i] > maxSize ){
diff[1] += groups[i] - maxSize;
}
}
// 最少の再割り当て人数は少ない方に埋めなければならない人数と
// 多い方で減らさなければならない人数の大きい方になる。
return Math.max(diff[0], diff[1]);
}
}
得点は176.84/250、1回のsubmitでシステムテストクリア。最後のコメントにあるアイディアを思いつくのに時間がかかりました。
