3258-River Hopscotch

問題（外部リンク）

3258 -- River Hopscotch

実装の概要

最小値を最大化する問題です。どのm個の石を取り除くかを全探索で考えようとすると間に合いません。
そこで、最大値を仮定し二分探索を利用して絞り込みます。
仮定した解をaとすると、今回の問題は「毎回距離a以上を保ちながら次の石に移動し続けることができるか。途中、合計m回まで石をスキップできる」と読み替えることができます。チェックの条件もこれに基づいて実装します。このチェックは1回あたりでできます。
二分探索なので最初の探索の範囲も重要ですが、rightの初期値は十分大きい値であればint型の上限の必要はありません。もっとも数回しか探索回数が変わらないのでそれほど問題ではありません。
なお、N=0の場合もあり得るのでそれについてはループに入る前に判断を行うようにしています。
また、分かりやすくするために配列の末尾にゴールの石の座標も入れてあります。

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String tmpArray[] = br.readLine().split(" ");

		int l = Integer.parseInt(tmpArray[0]);
		int n = Integer.parseInt(tmpArray[1]);
		int m = Integer.parseInt(tmpArray[2]);

		int stones[] = new int[n + 1];

		for(int i = 0; i < n; i++){
			stones[i] = Integer.parseInt(br.readLine());
		}

		stones[n] = l;

		System.out.println(solve(stones, l, m));
	}

	static int solve(int stones[], int l, int m){
		int n = stones.length;

		int left = 0;
		int right = l + 1;

		//解を仮定して二分探索
		while(right - left > 1){
			int mid = (left + right)/2;

			if(check(stones, l, m, mid)){
				left = mid;
			}
			else {
				right = mid;
			}
		}

		return left;
	}

	//interval以上の距離を開けつつ移動することはできるか
	static boolean check(int stones[], int l, int m, int interval){
		Arrays.sort(stones);
		int n = stones.length;

		//途中に石が1つもない場合
		if(n == 0){
			if(interval >= l){
				return true;
			}
			else {
				return false;
			}
		}
		int position = 0;
		int index = 0;
		while(position < l){
			//どこに飛べば良いかを探す
			for(int i = index; i < n; i++){
				//十分に遠い場合
				if(stones[i] - position >= interval){
					position = stones[i];
					index = i + 1;
					break;
				}
				else {
					m--;
					//スキップ回数がmを超えたら失敗
					if(m < 0){
						return false;
					}
				}
			}
		}

		return true;
	}

}