class BiggestRectangleEasy { public: int findArea(int N) { int r = 1; for(int i=1; i<N; ++i){ int a = i * 2; int b = N - a; if(b % 2)--b; if(b < 0)break; r = max(r, i * b/2); } return r; } };500
難しかった。
class ReturnToHome { public: double solve(double X, double Y, double D, double T){ double dist = sqrt(X * X + Y * Y); double time = 0; double cost = dist; int cnt = 0; do{ time += T; dist -= D; ++cnt; cost = min(cost, time + fabs(dist)); }while(D <= dist); if(cnt)cost = min(cost, (cnt + 1.0) * T); else cost = min(cost, 2.0 * T); return cost; } double goHome(int X, int Y, int D, int T) { return solve(X, Y, D, T); } };1000
const int MAX_N = 1000 + 10; const int MAX_W = 1000 * 3 + 10; double t[MAX_W][MAX_N]; double p1, p2; double rec(int p, int n) { if(p <= 0)return 1.0; if(n == 0 && 0 < p)return 0.0; if(0 <= t[p][n])return t[p][n]; double a = rec(p - 2, n - 1) * p1 + rec(p, n - 1) * (1.0 - p1); double b = rec(p - 3, n - 1) * p2 + rec(p, n - 1) * (1.0 - p2); return t[p][n] = max(a, b); } class SimplifiedDarts { public: double tryToWin(int W, int N, int P1, int P2) { fill(&t[0][0], &t[MAX_W-1][MAX_N], -1); p1 = (double)P1 / 100.0; p2 = (double)P2 / 100.0; return rec(W, N) * 100.0; } };
0 件のコメント :
コメントを投稿