ヒント集 → https://atcoder.jp/contests/arc197/editorial/12811

本問のように何らかの値の最大化が要求される問題は最適化の問題と呼ばれることがあります．（全ての場合の総和を求めるといった問題と違って）最適化の問題では，考えるべき場合を特殊な場合に限定するという戦略が有効に働くことがあります．この解説でもそのような戦略をとります．

部分列 \(x\) の平均値を \(\mathrm{avg}(x)\)，スコアを \(\mathrm{score}(x)\) と書くことにします．

[1] スコアを減らさない操作

最適解であって，規則の分かりやすいものが存在することを示すのが目標です．このことを，次の \(2\) つのスコアを減らさない操作から導きましょう．

操作 1

次が成り立ちます．

部分列 \(x\) について，\(A_i\) が次を満たすとする．

• \(A_i\leq \mathrm{avg}(x)\)
• \(A_i\) は \(x\) に含まれない．

このとき \(x\) に \(A_i\) を追加して得られる部分列を \(x'\) とすると \(\mathrm{score}(x)\leq \mathrm{score}(x')\) が成り立つ．

\(\mathrm{avg}(x')\leq \mathrm{avg}(x)\) となることから簡単に証明できます．\(x\) から \(x'\) を得る操作を操作 1 と呼ぶことにします．

操作 2

次が成り立ちます．

部分列 \(x\) について，\(A_i, A_j\) が次を満たすとする．

• \(\mathrm{avg}(x) < A_i < A_j\)
• \(A_i\) は \(x\) に含まれない
• \(A_j\) は \(x\) に含まれる

このとき \(x\) から \(A_j\) を削除し，\(A_i\) を追加して得られる部分列を \(x'\) とすると \(\mathrm{score}(x)\leq \mathrm{score}(x')\) が成り立つ．

やはり \(\mathrm{avg}(x')\leq \mathrm{avg}(x)\) となることから簡単に証明できます．\(x\) から \(x'\) を得る操作を操作 2 と呼ぶことにします．

[2] 答の計算

部分列 \(x\) が最適解であるとし，それに対して [1] で述べた \(2\) 種類の操作を可能な限り繰り返します．操作 1 は要素数を増加させ，操作 2 は要素数を変えないまま総和を減少させるため，有限回の操作の後にこれ以上操作が行えない状態に到達します．

操作はスコアを減らさないので，次が分かります：最適解であって，操作 1，操作 2 がどちらも行えないものが存在する．

このことから，簡単のため \(A\) を昇順にソートしておくと， \(x=(A_1,\ldots,A_n)\) の形の最適解が存在することが分かります．\(n=1,2,\ldots,N\) に対するスコアの計算は二分探索や尺取り法などで簡単に行えます．これを適切に実装すれば \(O(N\log N)\) 時間で答を計算することができます．

• 解答例：https://atcoder.jp/contests/arc197/submissions/65482041