技術室奥プログラミングコンテスト#4 Day2：G - 平均レーティング

問題
解法
解答

問題

https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_g

解法

「平均値の最大化」における一般的なテクとして二分探索がある．具体的には，求める最大の平均値を二分探索し，平均値 m が実現可能かどうかの判定は (各要素の値 - m) を最大化したものが 0 以上であるかで行うという方法．こうすることによって，要素の個数を決めなければ単なる最大化の問題にできなかったのを，要素の個数をいちいち決める必要がなくなり計算量を 1 つ落とすことができる．

今回の場合は，今実現可能か調べる平均値 m について a_i := a_i - m として以下の DP をする．

dp(i, j) := 部員 i までで，体力を j 使うときの，各レート - m の和の最大値

遷移は「平均を取る部員の中に採用する」「1 回教育する」「退部させる」の 3 つ．「1 回教育する」の処理において，部員 i + 1 を見ているときに部員 i を教育する遷移の処理を書く必要がある（そうでないと，部員 i を考慮していないのにレートをあげる処理をしてしまうことになる）．O(NK * log(答えの最大値))．