Codeforces Round #351 Div2 E. Levels and Regions

問題概要
あなたはテレビゲームをプレーしている。
このゲームでは、1からnまでの階があり、それらはk個の地区に分かれている。
各階iには、対応するトークンがt[i]個ある。

今あなたは地区Xにいるとする。
そのとき、コンピュータによって以下の操作が行われる。

• 袋にX内のクリア済みの階に対応するトークンを入れる。
• 袋にX内のまだクリアしていない最低階に対応するトークンを入れる。
• 袋から一様な確率でランダムにトークンを引く。

あなたは袋から引かれたトークンに対応する階をプレーしないといけない。

一つの階をクリアするには1時間かかる。
各階をどのように地区に振り分けるかは自由である。
すべての階をクリアするために必要なプレー時間の期待値の最小値を求めよ。

解法
(地区を何個まで区切ったか, 階)を状態数としてDPすればいいのはすぐ分かる。
これだけだと遅いので、うまく式変形してConvex Hull Trickを使って高速化する。

実装
ライブラリ化している人が多かったので、自分もライブラリ作ってみた。
処理の詳細な説明は蟻本に載っている。

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

const double oo = 1e100;
int n, k;
int ts[200000];
double sum[200000+1];
double rev[200000+1];
double pre[200000+1];
double dp[50+1][200000+1];

template <typename T>
// line f(x) = ax + b
struct line {
  T a, b;
  line() {}
  line(T a, T b) : a(a), b(b) {}
  T eval(T x) { return a * x + b; }
};

template <typename T>
// get min_l {f_l(x)} with convex hull trick
struct CHT {
  int s;
  int t;
  vector<line<T> > deq;

  CHT(int n) {
    deq = vector<line<T> >(n);
    clear();
  }

  void clear() {
    s = t = 0;
  }
  
  bool check(const line<T> &l1, const line<T> &l2, const line<T> &l3) {
    return (l2.a-l1.a) * (l3.b-l2.b) >= (l2.b-l1.b) * (l3.a-l2.a);
  }
  
  void push(T a, T b) {
    line<T> l(a, b);
    while (s + 1 < t && check(deq[t-2], deq[t-1], l))
      --t;
    deq[t++] = l;
  }
  
  
  T get(T x) {
    while (s + 1 < t && deq[s].eval(x) >= deq[s+1].eval(x))
      ++s;
    return deq[s].eval(x);
  }
  
};

void solve() {
  REP (i, n) sum[i+1] = sum[i] + ts[i];
  REP (i, n) rev[i+1] = rev[i] + 1.0 / ts[i];
  REP (i, n) pre[i+1] = pre[i] + sum[i+1] / ts[i];
  REP (i, k+1) REP (j, n+1) dp[i][j] = oo;
  dp[0][0] = 0.0;
  CHT<double> cht(n+1);
  REP (i, k) {
    cht.clear();
    REP (j, n) {
      cht.push(-sum[j], dp[i][j] - pre[j] + rev[j] * sum[j]);
      double tmp = pre[j+1] + cht.get(rev[j+1]);
      dp[i+1][j+1] = min(dp[i+1][j+1], tmp);      
    }
  }
}

int main() {
  scanf(" %d %d", &n, &k);
  REP (i, n) scanf(" %d", ts+i);
  solve();
  printf("%.9lf\n", dp[k][n]);
  return 0;
}