選び方のスコア - yukicoder No. 972

#二分探索 #累積和 #中央値

解法

選んだ数列が要素数偶数なら, 真ん中の大きい方の数を抜いたほうが答えが良くなる

(問題文に答えが整数になると書いてあるので, 分数が出てくる, 要素数偶数のときは答えにならないのではないか, と考える)
∵
要素数が偶数のとき, 中央値は真ん中の小さい方 $a_k$ と大きい方 $a_{k + 1}$ で決まるが, それらと中央値の差の和は 0
$a_k - \frac{a_k + a_{k + 1}}{2} + a_{k + 1} - \frac{a_k + a_{k + 1}}{2} = 0$

よって, スコアは, 真ん中の 2 数を除いた数 $\ \ \ \ (1)$ と, 中央値の差の和である

ここで, 真ん中の大きい方の数を抜く
要素数は奇数になる
真ん中の数 (さっきまで真ん中の小さい方だった数) と中央値 (その数) の差は 0

スコアは, 抜いた数と真ん中の数を除いた数 ((1) と同じ) と, 中央値の差の和である

中央値が小さくなったので全体も小さくなった

以上より, 要素数は奇数なので, 中央値は $a_i$ のいずれかになった

中央値 $a_m$ を固定したとき, スコアを最大にするにはどうすればいいか
まず, 一番大きな値 $a_{n - 1}$ はとりたい
すると, 中央値を変えないために, 中央値より小さな値も 1 つ取らなければならない
$a_{m - 1}$ とするべき

以降, $(a_{n - 2}, a_{m - 2}), (a_{n - 3}, a_{m - 3}), ...$ をとるか考える

要素を追加したとき, スコアの差分は $a_{n - i} + a_{m - i} - 2 * a_{m}$
ここで, i を大きくしたとき, $a_{n - i} + a_{m - i}$ は小さくなる
$2 * a_{m}$ は一定で, スコアの差分に単調性があるので, 二分探索が使える (ポイント)

スコアの差分が正のものをすべて足す
二分探索で i を決めたとする

すなわち, 中央値を $a_m$ としたとき, スコアは
$\sum_{k = 1}^{i} a_{n - k} + a_{m - k} - 2 * a_{m}$
$= \sum_{k = 1}^{i} a_{n - k} + \sum_{k = 1}^{i} a_{m - k} - 2 * i * a_{m}$

これは累積和で求められる

コード
#419587 No.972 選び方のスコア - yukicoder