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