このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題文についておおまかに説明する。
luckySetという整数の集合が与えられる。luckySetに属する2つの要素でAがBより大きく、AとBが共に正の整数である区間[A, B]は、もしAとBの間の整数がなければ不幸であると考えられる。luckySetという整数型配列と、nというluckySetの最大値を超えないような整数が与えられたとき、nを含む不幸な区間の数を返すメソッドを作成せよ。
例えば、luckySet={1, 7, 14, 10}、n=2である場合、1と7の間に2があり、2～6の整数を用いて、2を含むような区間を考えてみると、[2, 6]、[2, 5]、[2, 4]、[2, 3]の4つが該当する。
私の解答はこちら。
import java.util.Arrays;
public class UnluckyNumbers {
public int getCount(int[] luckySet, int n) {
for( int i=0 ; i<luckySet.length ; i++ ){
if( luckySet[i] == n ) return 0; // Setの値があったら区間は作れないので0
}
Arrays.sort(luckySet); // ソートして、
int[] between = new int[2]; // どこの間の区間にnがあるか検討する
for( int i=1 ; i<luckySet.length ; i++ ){
if( luckySet[i] > n ){
between[0] = luckySet[i-1] + 1;
between[1] = luckySet[i] - 1;
break;
}
}
if( n < luckySet[0] ){ // nがluckySetの最小値よりも小さい場合
between[0] = 1;
between[1] = luckySet[0] - 1;
}
int nInterval = 0; // 以下で区間の数を数える
for( int i=between[0] ; i<=between[1] ; i++ ){
if( i < n ){
nInterval += between[1] - n + 1;
}else if( i == n){
nInterval += between[1] - n;
}
}
return nInterval;
}
}
得点は153.40/250、2回目のsubmitでシステムテストクリア。1回目の提出では、nがluckySetの最小値を下回る場合の処理を間違えていた。
