AOJ_0529 Darts

問題
解法
<ダーツを投げない>は0点の的に当たったとしてあつかえばいい。

n回目に投げたダーツの得点をPnとすると、
P1 + p2 + P3 + p4 < M
が成り立つようにしなければならない。

このまま計算すると、計算量は O(N^4) となりN <= 1000 だから時間がかかりすぎる。

ここで、式を変形して、
P3 + P4 < M - (P1 + P2)

これを計算する
2つのダーツの合計得点をあらかじめ計算し、
ソートしておくけば、(P1 + P2)の値を決めると、この式を満たし
かつ最大の(P3 + P4)の値は二分法を使うことにより決めることができる。
計算量はO(N^2 log N)となり制限時間内に求めることができる。

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 1001;
int N, M;
int P[MAX_N];
int PpP[MAX_N*MAX_N];
int solve(int l, int h, int n){
	int res = -1;
	while(true){
		int m = (l + h) / 2;
		if(PpP[m] < n){
			res = PpP[m];
			l = m + 1;
		}else{
			h = m;
		}
		if(h == l) break;
	}
	return res;
}
int main(){
	while(scanf("%d %d", &N, &M) && N){
		P[0] = 0;
		N++;
		for(int i = 1; i < N; i++)
			scanf("%d", &P[i]);
		sort(P, P + N);
		for(int i = 0; i < N; i++)
			for(int j = 0; j < N; j++)
				PpP[i*N+j] = P[i] + P[j];
		sort(PpP, PpP + N * N);
		int ans = 0;
		for(int i = 0; i < N * N; i++){
			int X = PpP[i];
			if(M-X < 0) continue;
			//printf("%d(%d) ", M-X, X);
			int Y = solve(0, N * N, M - X);
			ans = max(ans, X + Y);
		}
		//puts("");
		printf("%d\n",ans);
	}
	return 0;
}