Tenka1 Programmer Contest 2018 C - Align
解法
1,..,N の順列を p1,..,pN として, 最大化したい関数は
|A_p1 - A_p2| + .. + |A_pN-1 - A_pN| になる.
目的関数の絶対値を外したい気持ちになるので,そのためには数列の順序付けが必要になる.
それを念頭に起きつつ最適解の必要条件を列挙してみる.
すると A_p1,.., A_pN が単調増加/減少になっていてはダメで, 凸凹のような形になっている必要があることがわかる.
例えば a < b < c であれば a c b と並んでいた方がいい.簡潔な証明は解説に載っている.
これを式で書くと
A_p1 >= A_p2 <= A_p3 >= .. or A_p1 <= A_p2 >= ..
となっている.
前者の時, N=evenとすると目的関数は
(A_p1 - A_p2)+(A_p3-A_p2) + .. + (A_p{N-1} - A_pN )
= 2(A_p1 + .. + A_p{N-1}) - A_p1 - 2(A_p2 + .. + A_pN) + A_pN
となる.
よって{A} を sortしてgreedyに当てはめていけばいい.
この場合だと奇数項が昇順sortしたときの後ろ半分(ただしA_p1がその中で最小のもの),
偶数項が前半分(ただしA_pNがその中で最大のもの) になる.
