備忘録代わりに精進記録を載せていくつもりです。解説に詳しい証明が載っているのですが、並べた後の数列が凸凹になっていると、効率がよりよくなります。みたいな感じです(逆もあり得ます)。このとき、以下のような図で表現できます。上にある頂点は隣の数より大きく、下にある頂点は隣の数より小さいです。このときの差の絶対値の計算はというと、となります。増えると、2倍して足す部分、もしくは引く部分が交互に追加されていきます。この中で、数字をどのように使って行くのが一番いいのかというと、より大きい数字は、2倍して加算する部分より小さい数字は、2倍して減算する部分となります。端の2箇所だけ、2倍されずに加算、もしくは減算される部分が存在するので、この部分だけ調整します。この数字をソートしたとき、中央の2個(もしくは3個)の数字を見るだけで大丈夫です。これは、偶奇で場合分けをしてあげるとスッキリいきます。それ以外は、先ほどの条件にしたがって先に計算してしまいます。中央の3つだけを取り出して考えると、上記のような2パターンに絞られます。名付けてあげると、先ほどの2パターンそれぞれについての最大値はとなります。あとは、この2つのうち大きい値を選んであげればよいです。最初と最後は、常にどちらかが上側で、もう一方が下側に存在します。うち値が大きい方を選択すればいいわけです。いうわけで、最初に求めた、2倍して加算したり減算した結果と、偶奇に分けて考えた中央付近の結果を足し合わせれば答えとなります。シミュレーションをします。(1)注目記事はてなブログをはじめよう!emtubasaさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。