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