tenka1_2018_C
考えたこと
2個の時どうやっても同じ
3個の時、最大値を真ん中に持ってくるか、最小値を真ん中に持ってくるか。どちらでも同じ
4個の時
最大値と最小値は端に置いてはいけない
後はジグザグならOK
一般的に
4つの数が単調増加の時、中二つを入れ替えてジグザグにした方が常に良い
端以外のジグザグの山に関して、入れ替えても結果は変わらない
端をどう考えるべきか…
端がジグザグの小さい側で、ジグザグのある谷より低い場合、入れ替えた方が常に良い
偶数個の場合は大小半分に割って境界の2つを端にすれば良い
奇数個の場合は大を多めにするのか小を多めにするのか…
小さい列で試して確認したい、異なるなら両方試せばいい
以上の考察からソートし線形オーダーで答えが出る
公式解説
おおよそ同じ感じ
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]