AtCoder Beginner Contest 327E問題

ABC327E

解法

レーティングの計算式を見ると，\(k\)を固定したときに 第一項の分母と第二項は定数． よって，第一項の分子だけ最大化すればよい． この DP は容易．

注意

普通にDPを実装すると，-inf * \(0.9^{t}\) の形を計算することになる． これだと，\(t\)が大きい時に変な値になってしまう． いずれ正の数になってしまう？

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  ll n;

  cin >> n;

  vll a(n); rep(i,n) { cin >> a[i]; }

  vector<double> dp(n+1, -1e18);

  dp[0] = 0;

  rep(i,n){

    drep(k,i+1){ // n : wa (-1e18*0.9^{t} を計算することになって，いずれ変な値になるため)

      chmax(dp[k+1], 0.9*dp[k] + a[i]);

    }

  }

  double ans = -1e18;

  double s = 0;

  rep1(k,n){

    s = 0.9*s + 1;

    chmax(ans, dp[k]/s - (double)1200/sqrt(k));

  }

   

  printf("%.10lf\n", ans);

  return 0;

}