[ABC327] E - Maximize Rating

[Q] E - Maximize Rating

考察
1. N, M = 5000は二次元DPだと思う。
2. DP[i] = i個とったときのベストスコアとして管理。
答えはDP[1] ~ DP[N]までのベストスコアが解答になる。
3. index i~Nまで探索する。
indexごとに、1~N個とった場合のスコアを計算する。
4. 遷移は、nDP[i] = DP[i - 1] * 0.9 + p[i]で、最大値を更新する必要がある。
5. 確定で取らなきゃいけないときを考慮する必要がある。
分子の箇所だけ抽出して考える。

10
1 1 1 1 5000 1 1 1 1 1

このケースは、5個目の5000までをとるのが最善というのがわかる。

DP[0] = 0
DP[1] = 5000
DP[2] = 5000.9
DP[3] = 5001.71
DP[4] = 5002.44
DP[5] = 5003.1
DP[6] = 4503.79 // 5003.1ではない。常に最大値を更新するわけではない。
DP[7] = 4054.41 // 5003.1ではない。
DP[8] = 3649.97
DP[9] = 3285.97
DP[10] = 2958.37

index i~Nについて、iより大きい値でのDP[j~N]更新については、最大値の更新ではなく、確定で採用する必要がある。

実装

int main() {
  cincout();
  
  ll N;
  cin >> N;
  // 前計算。
  vector<ld> pow9(N + 1), acc(N + 1); // pow9[2] = 0.9^2, acc[2]=1+0.9+0.81
  pow9[0] = 1;
  rep(i, N) pow9[i + 1] = pow9[i] * 0.9;
  acc[0] = 1;
  rep(i, N) acc[i + 1] = acc[i] + pow9[i + 1];

  vector<ld> DP(N + 1);
  rep(i, N){
    // task用のDP。swap()する予定
    vector<ld> nDP(N + 1);
    ll p;
    cin >> p;
    for(ll j = 1; j <= N; ++j){
      if (j <= i){ // とるのが必須ではない。とるか取らないか選べる場合
        nDP[j] = max(DP[j], DP[j - 1] * 0.9 + p);
      }
      else{ // とるのが必須のとき i=5 j=6のとき、6番目の要素で6個とらなければいけないため、とるのが必須
        nDP[j] = DP[j - 1] * 0.9 + p;
      }
    }
    // 更新
    swap(DP, nDP);
  }
  ld ans = -oo;
  for(ll i = 1; i <= N; ++i){
    // 分母と定数を除く
    ld cur = DP[i] / acc[i - 1] - 1200.0 / sqrtl(i);
    chmax(ans, cur);
  }
  cout << ans << endl;
}

https://atcoder.jp/contests/abc327/submissions/47257335