SRM318Div2

250

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