ARC229 C - Sum of Average 2

考え方

全体を $2$ 倍して考える。
すると、$A_i+A_{i+1}$ が奇数だったら $1$ 引いてから、その総和を取る形になる。
つまり、両端は $1$ 回、それ以外は $2$ 回合計して、偶奇が異なる数が隣接している回数を引く。
それが並べ替えを実際に作ったときの総和の $2$ 倍である。

$A$ は全て正の数なので、基本的には大きい方から $2$ つを両端に置くとよいと予想される。
これを証明しよう。

ある数 $X$ を端に置く代わりにそれより小さい $Y$ を端に置くとする。
この場合、偶奇が異なる最大隣接数が $1$ 変わる可能性がある。
が、$X-Y \geq 1$ であるため、良くても同点である。
従って、両端は貪欲に大きい方から $2$ つを選んでよい。

あとは偶奇が異なる最大隣接数だが、これはどちらかが尽きるまで交互に並べればよく、以下で簡単。

• 両端が偶数なら、$2\times(\text{奇数の個数})$ か、$2\times(\text{偶数の個数}-1)$ の小さい方
• 片方が偶数なら、$2\times(\text{奇数の個数})-1$ か、$2\times(\text{偶数の個数})-1$ の小さい方
• 両端が奇数なら、$2\times(\text{偶数の個数})$ か、$2\times(\text{奇数の個数}-1)$ の小さい方

以上をまとめると、解き方は以下のようになる。

• 大きい方から $2$ つは $1$ 回、それ以外は $2$ 回ずつ合計する
• 端に置いた数の偶奇を見て、偶奇が異なる最大隣接数を求めて引く
• 半分にすれば答え

最大の $2$ つを普通にソートするなら、計算量は $1$ ケース当たり $O(N\log N)$ である。
別の方法で最大 $2$ つを探せば、$1$ ケース当たり $O(N)$ にもできる。

入力例1での動作

入力例1のうち、$1$ 番目のテストケースを考える。

入力を受け取る。

n: 4
a: {1, 2, 4, 3}

まず $A$ を降順に並べる。

A: {4, 3, 2, 1}

大きい方から $2$ つである $4,3$ は $1$ 回ずつ、それ以外の $2,1$ は $2$ 回ずつ合計する。
全体を $2$ 倍した状態で考えているので、$4+3+2\times2+1\times2=13$ となる。

偶数は $4,2$ の $2$ 個、奇数は $3,1$ の $2$ 個である。
両端に置く $4,3$ は偶奇が異なるので、偶奇が異なる最大隣接数は $2\times\min(2,2)-1=3$ となる。

したがって、$13-3=10$ であり、最後に半分にして答えは $5$ となる。

実際、例えば次のように並べられる。

{4, 1, 2, 3}

この並べ方では、偶奇が異なる隣接箇所は $3$ 個になる。
また、$\left\lfloor\frac{4+1}{2}\right\rfloor+\left\lfloor\frac{1+2}{2}\right\rfloor+\left\lfloor\frac{2+3}{2}\right\rfloor=2+1+2=5$ となる。

注意点

途中の合計や答えは int 型からはみ出る。
long long 型を用いること。

別解

特になし。