ABC 327 E — Maximize Rating

考察

選ぶcontest数kを固定するとdenominator Σ0.9^iとpenalty 1200/√kは固定され、最大化すべきなのはweighted performance numeratorだけになる。参加順を保ってj個選んだweighted sumへ新しいperformance P_iを末尾追加すると、既存sum全体が0.9倍されてP_iが加わる。従ってprefixからj個選ぶ最大numeratorを選択個数DPで全k同時に求められる。contest iをtakeする遷移はdp_new[j]=max(dp_old[j],0.9dp_old[j-1]+P_i)で、skipと末尾追加の2caseを尽くす。den[k]=Σ_{r=0}^{k-1}0.9^rもden[k]=0.9den[k-1]+1で同じ方向に前計算できる。

採用する候補: dp[j]を処理済みcontestからj個選ぶweighted numerator最大値としてskip/take更新し、各kのratingを比較する。

2^N subsetを選択個数ごとの最良numeratorへ集約し、k依存のdenominatorとpenaltyを最後に適用できる。

棄却する候補: performanceが高いcontestを値順にk個選ぶ。

weightは参加順で新しい選択ほど大きく、値だけでsortすると元の時系列を無視する。

棄却する候補: 全contest subsetのratingを直接計算する。

N≤5000で2^N候補は列挙不能である。

dp[0]=0、他を−∞とし、P_iを順に見るたびjを大きい方から1まで走査してdp[j]=max(dp[j],0.9·dp[j-1]+P_i)と更新する。den[0]=0からden[k]=0.9den[k-1]+1を作り、全k=1..Nでdp[k]/den[k]−1200/sqrt(k)の最大値をdoubleで出力する。

典型の発動条件

選択個数別subsequence DP

発動条件: 順序を保つsubsetを選び、末尾追加で評価式が簡単に更新できるとき。

prefix処理と選択数を状態にしてskip/takeする。

目的関数parameterの固定

発動条件: 選択数kごとに一部の項が固定され、残りだけ別DPで最大化できるとき。

numerator最大値M(k)を全k求めてrating式へ戻す。

問題固有の要素

新しい選択を末尾に加えると過去performanceの全weightが一様に0.9倍されるため、個々の選択時刻を状態に残さずweighted sum1値で十分になる。

別の問題へ持ち帰る視点: 時系列重みが末尾追加で共通倍率を受ける評価は、aggregateへaffine変換を施すsubsequence DPにできる。

正当性

k個選択の分子は前のk−1個分子へ0.9を掛け現在Pを足す。同じkの分母と罰則は固定なので分子最大だけを残せる。降順k更新は一つの成績の再使用を防ぐ。全kのrating最大を最後に取る。

実装上の注意

  • 1次元in-place DPはjを降順に更新し、同じcontestを複数回takeしない。
  • 未到達dpを−∞で区別し、最終ratingのsqrtとdivisionはdoubleまたはlong doubleで行う。

復習の核

  • 古い高performanceと新しい中performanceの2 contestで、末尾追加時に前者だけ0.9倍されることと降順更新を確認する。

計算量と制約

時間

N 成績、選択数kの全更新で O(N²)。

空間

rolling選択数 DP と分母表 O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1\leq N\leq 5000; 1\leq P_i\leq 5000; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Maximize Rating の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 列・subsequence DP

主題
  • 列・subsequence DP: 列の順序を保つ状態と、選ぶ・選ばない遷移を設計できる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 列・subsequence DP

      執筆: abc-explanation-author1.1.1 / revision 2

      学習の位置

      体系上の位置: 列・subsequence DP

      • 列の順序を保つ状態と、選ぶ・選ばない遷移を設計できる。

      先に読む単元:

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題