AOJ : 0529 - ダーツ (Darts)

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0529&lang=jp
日本語の問題文なので省略します

アルゴリズム

自分で考えて、結局いい解法が思いつかなかった(TLEしないような解法が思いつかなかった)ため、情報オリンピックの解説を参考にしました。
僕からのアルゴリズムの解説はなしです。

http://www.ioi-jp.org/joi/2007/2008-ho-prob_and_sol/2008-ho-review.pdf

プログラム

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

int p[1010];
int sum[1002010];

int main(void){
	int n,m;

	while(scanf("%d%d",&n,&m) && (n||m)){
		for(int i=0;i<n;i++){
			scanf("%d",&p[i]);
		}
		p[n++] = 0; //0点のスコアを作る

		int size=0;
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				sum[size++] = p[i] + p[j];
			}
		}
		sort(sum,sum+size);

		int ans = 0;

		for(int i=0;i<size;i++){
			int rem = m - sum[i];
			if(rem < 0) continue;
			int left = 0, right = size;

			while(left < right){
				int center = (left + right) / 2;
				if(rem > sum[center]){
					left = center + 1;
				}
				else if(rem < sum[center]){
					right = center;
				}
				else {
					break;
				}
			}

			ans = max(ans, sum[i] + sum[right-1]);
		}

		printf("%d\n",ans);
	}

	return 0;
}