あばれうなぎ (AOJ 2278)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2278

問題

略

解法

一番左端のプレート2つを考えるとエネルギーを右側に全力でかけるか、両方のプレートで同じだけの熱を与えるようにエネルギーを掛けるかの効率の良い方を選択すれば良い。これをすることによって2つのプレートをマージできる。マージを続けていくとプレートが3枚だけになるのでてきとうに計算すれば良い。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

int n;
double E;
double plate[300000];

inline double Get(int index) {
  return plate[index + n];
}

inline double Merge(double x, double y, int w) {
  return min(y, (w * x + y) / (w + 1));
}

double MergeAll(int dir) {
  double left = Get(-dir * n);
  int w = 1;
  int index = -dir * n + dir;
  while (index != 0) {
    left = Merge(left, Get(index), w);
    //cout << index << " " << left << " " << w << endl;
    assert(left >= -EPS);
    w++;
    index += dir;
  }
  return left;
}

int main() {
  while (scanf("%d %lf", &n, &E) > 0) {
    REP(i, 2 * n + 1) {
      scanf("%lf", &plate[i]);
    }
    double left = MergeAll(1);
    double right = MergeAll(-1);
    double ans = max(E / Get(0), E * (n + 1) / (n * (left + right) + Get(0)));
    printf("%.8f\n", ans);
  }
}