JOI Open 2013 - Watching

問題文 : ウォッチング

解法 (ただし人と違う解き方をしているらしい) :
50 点分の解法は, dp[i][j][k] : 位置i までを小カメラj 個, 大カメラk 個で覆うときの距離の最小値, として, O(N^4) で計算できる. (二分探索とは概念)

これを高速化するために, dp[i][j] :距離w が固定されているとき, 小カメラi 個と大カメラj 個で覆えるイベントの最大値とすると, O(N^2 * logN) までこれを高速化することができる. w は二分探索で定めればよい為, O(N^2 * 30 * logN) となるが, 制限時間が2 sec あるのでこれで十分である.

普通はdp[i][j] : i 番目までをj 個の大カメラで覆うときに必要な小カメラの最小値, とするらしいですが, なんでもよさそうです.

コード :

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int A[2013];
int dp[2048][2048];
int N, _P, _Q;
int lim;

bool ok()
{
	
	for (int i = 0; i <= _P; i++){
		for (int j = 0; j <= _Q; j++){
			dp[i + 1][j] = max(dp[i + 1][j], (int)(upper_bound(A, A + N, A[dp[i][j] + 1] + lim - 1) - A - 1));
			dp[i][j + 1] = max(dp[i][j + 1], (int)(upper_bound(A, A + N, A[dp[i][j] + 1] + lim * 2 - 1) - A - 1));
			//printf("(%d, %d) = %d / (%d, %d) = %d\n", i + 1, j, dp[i + 1][j], i, j + 1, dp[i][j + 1]);
			if ((i + 1 <= _P && dp[i + 1][j] == N - 1) || (j + 1 <= _Q && dp[i][j + 1] == N - 1)) return (true);
		}
	}
	
	return (false);
}



int main()
{
	scanf("%d %d %d", &N, &_P, &_Q);
	
	if (_P + _Q >= N) return (!printf("1\n"));
	
	for (int i = 0; i < N; i++)
		scanf("%d", A + i);
	
	sort(A, A + N);
	int lo = 1, hi = 1000000000;
	while (lo != hi){
		int mid = (lo + hi) / 2;
		lim = mid;
		
		memset(dp, -1, sizeof(dp));
		
		if (ok()) hi = mid;
		else lo = mid + 1;
	}
	
	printf("%d\n", lo);
	
	return (0);
}