平均値や中央値を最大化する問題は、「答えを \(K\) 以上にできるか？」という判定問題に帰着し、二分探索によって答えを求めるのが定石です。

平均値を \(K\) 以上にできるか？

「\(x_1, \dots, x_n\) の平均値が \(K\) 以上 \(\Leftrightarrow\) \((x_1 - K) + \dots + (x_n - K)\) が \(0\) 以上」であるので、\(B_i = A_i - K\) とおき、選んだカードに対応する \(B_i\) の総和の最大値が \(0\) 以上かどうか判定すればよいです。

中央値を \(K\) 以上にできるか？

「\(x_1, \dots, x_n\) の中央値が \(K\) 以上 \(\Leftrightarrow\) \(x_i\) のうち \(K\) 以上のものの個数が \(K\) 未満のものの個数より多い」であるので、\(B_i\) を \(A_i \geq K\) なら \(1\)、そうでないなら \(-1\) とおき、選んだカードに対応する \(B_i\) の総和の最大値が正かどうか判定すればよいです。

\(B_i\) の総和の最大化

前述の判定問題において、選んだカードに対応する \(B_i\) の総和の最大値を求める必要がありました。これは次のような動的計画法によって求められます。

• \(f_k := k\) 番目のカードまで選ぶかどうか決め、かつ \(k\) 番目のカードを選ぶときの \(B_i\) の総和の最大値
• \(g_k := k\) 番目のカードまで選ぶかどうか決め、かつ \(k\) 番目のカードを選ばないときの \(B_i\) の総和の最大値

\(f_0 \leftarrow 0, g_0 \leftarrow 0\) とし、\(k\) の昇順に \(f_k \leftarrow \max(f_{k - 1}, g_{k - 1}) + B_k, g_k \leftarrow f_{k - 1}\) と計算していけばよいです。よって、判定問題を \(O(N)\) で解くことができます。

誤差への対応

平均値は整数値をとるとは限らないので、厳密な値を求めることは困難です。この問題においては正しい値との相対誤差または絶対誤差が \(10^{-3}\) 以下であれば正答とみなされるので、次の方法が考えられるでしょう。

• 各 \(A_i\) を \(10^3\) 倍し、平均値を \(K\) 以上にできるような最大の整数 \(K\) を求める。\(10^{-3} K\) を出力する。実装例 (C++)
• 二分探索の下端を \(l\)、上端を \(h\) としたとき、\(\frac{h - l}{h} > 10^{-3}\) である間探索を続ける。探索が終了したら、\(l\) を出力する。実装例 (C++)
  • 補足 1. この問題において平均値は必ず \(1\) 以上になるので、\(l \geq 1\) としてよいです。そのため、相対誤差は必ず絶対誤差より小さくなります。
  • 補足 2. 二分探索では \(m = \frac{l + h}{2}\) として \(K = m\) に対する判定問題を解くのが一般的です。しかし、この問題のように答えが必ず \(1\) 以上であり、かつ相対誤差を閾値以下にすることが目的である場合は、\(m = \sqrt{lh}\) とした方が最悪探索回数が少なくなります。これは、\(\max(\frac{x - l}{x}, \frac{h - x}{h})\) を最小化することを考えると分かります。