Official
F - Mean Median Construction Editorial
by
F - Mean Median Construction Editorial
by 
Magentor
\(a_1 < a_2 < \dots <a_n\) とします。まずは、任意の \(a\) の連続とは限らない空でない部分列について、その部分列の中央値がその部分列の平均値以下である、という条件を高速に判定することを考えます。
すべての長さ \(3\) の \(a\) の部分列 \(b\) について、\(b\) の中央値が \(b\) の平均値以下であるとします。実はこのとき、\(a\) の全ての部分列についてその部分列の中央値が平均値以下であると分かります。
証明
すべての長さ $3$ 以下の $a$ の部分列について、条件が成り立っているものとします。 $a$ の部分列を $b=(b_1,b_2,\dots,b_{|b|})$ としたとき、$|b|\leq 2$ のときに成り立つことは明らかです。また、$|b|$ が偶数の場合、$b$ から $b_{|b|}$ を取り除いたものについて条件が成り立っていればいいので、$|b|$ が奇数の場合に帰着されます。 このとき、$b_{\lfloor \frac{|b|+1}{2} \rfloor} \leq \frac{b_1+b_2+\dots +b_{|b|}}{|b|}\Leftrightarrow 0 \leq b_1+b_2+\dots + b_{\lfloor \frac{|b|+1}{2} \rfloor-1}-(|b|-1)b_{\lfloor \frac{|b|+1}{2} \rfloor}+b_{\lfloor \frac{|b|+1}{2} \rfloor+1}+\dots + b_{|b|}$ が成り立てばいいです。ところで、この式は $0 \leq b_1-2b_{\lfloor \frac{|b|+1}{2} \rfloor}+b_{|b|}$ と $0 \leq b_2+b_3+\dots + b_{\lfloor \frac{|b|+1}{2} \rfloor-1}-(|b|-1)b_{\lfloor \frac{|b|+1}{2} \rfloor}+b_{\lfloor \frac{|b|+1}{2} \rfloor+1}+\dots + b_{|b|-1}$ が成り立てば成り立つと分かります。前者については $|b|=3$ の場合に条件が成り立つとしたので、この式は成り立ちます。よって、$|b|$ が $2$ 小さいときに条件が満たされれば良いと分かります。これを繰り返すことで、最終的に $|b|=3$ となり、条件が成り立つとわかります。また、これは明らかに \(2 \leq i \leq N-1\) を満たす整数 \(i\) について \(a_i \leq \frac{a_1+a_i+a_{i+1}}{3} \Leftrightarrow a_i \leq \frac{a_1+a_{i+1}}{2}\) という条件に言い換えられることが分かります。
このとき、\(a_1=0,a_N=10^9\) として、\(a_{i} = \lfloor \frac{a_1+a_{i+1}}{2} \rfloor\) となるようにするのが最適であると分かります。このようなことを繰り返したとき、\(31<N\) の場合結果的に \(a_1=a_2\) となってしまい、条件を満たしません。逆に \(N \leq 31\) の場合すべての条件を満たすことが確認できるので、この問題を解くことができました。
posted:
last update: