tenka1_2018_C
C - Align
https://gyazo.com/ded3891efa2ce77c3e1abc6275cdbce5
考えたこと
2個の時どうやっても同じ
3個の時、最大値を真ん中に持ってくるか、最小値を真ん中に持ってくるか。どちらでも同じ
4個の時
最大値と最小値は端に置いてはいけない
後はジグザグならOK
一般的に
4つの数が単調増加の時、中二つを入れ替えてジグザグにした方が常に良い
端以外のジグザグの山に関して、入れ替えても結果は変わらない
端をどう考えるべきか…
端がジグザグの小さい側で、ジグザグのある谷より低い場合、入れ替えた方が常に良い
偶数個の場合は大小半分に割って境界の2つを端にすれば良い
奇数個の場合は大を多めにするのか小を多めにするのか…
小さい列で試して確認したい、異なるなら両方試せばいい
以上の考察からソートし線形オーダーで答えが出る
公式解説
おおよそ同じ感じ