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; }