\(A\) に \( (2M-N)\) 個の \(0\) を加え、長さ \(2M\) の数列とした後に適切に並び替えて、以下の値を最小化すれば良いです。

\[\sum_{i=1}^{M}(A_{i}+A_{2M+1-i})^{2}\]

これは \(A\) をソートすることで最小化できるので、 \(O(N\log{N})\) で解くことができます。

以下、 \(A\) をソートすることが最適解のひとつであることの証明です。

任意の \(A\) に対して、答えを変化させずに以下の条件を満たすように並び替える方法があります。

• \(A_{i}\leq A_{2M+1-i}\;(1\leq i\leq M)\)
• \(A_{i}\leq A_{i+1}\;(1\leq i\lt M)\)

よって、最適解のひとつは上 \(2\) つの条件を満たします。

ここで、\(2\) つの条件下で \(A_{2M+1-i}\lt A_{2M-i}\) となるような \(i\;(1\leq i\lt M)\) が存在したとします。

\(((A_{i}+A_{2M+1-i})^{2}+(A_{i+1}+A_{2M-i})^{2})-((A_{i}+A_{2M-i})^{2}+(A_{i+1}+A_{2M+1-i})^{2})\)

\(=2(A_{i}A_{2M+1-i}+A_{i+1}A_{2M-i}-A_{i}A_{2M-i}-A_{i+1}A_{2M+1-i})\)

\(=2(A_{i}-A_{i+1})(A_{2M+1-i}-A_{2M-i})\)

ここで、 \(A_{i}-A_{i+1}\leq 0\) かつ\(A_{2M+1-i}-A_{2M-i}\lt 0\) より、 \(2(A_{i}-A_{i+1})(A_{2M+1-i}-A_{2M-i})\leq 0\) が成り立ちます。

以上より、 \(A_{2M+1-i}\lt A_{2M-i}\) を満たす \(i\;(1\leq i\lt M)\) が存在するなら、\(A_{2M+1-i}\) と \(A_{2M-i}\) を入れ替えることで、答えが維持されるもしくは改善されるため、\(A_{2M+1-i}\lt A_{2M-i}\) を満たす \(i\;(1\leq i\lt M)\) が存在しない最適解が存在します。

よって、以下の条件を全て満たす最適解が存在します。

• \(A_{i}\leq A_{2M+1-i}\;(1\leq i\leq M)\)
• \(A_{i}\leq A_{i+1}\;(1\leq i\lt M)\)
• \(A_{2M-i}\leq A_{2M+1-i}\;(1\leq i\lt M)\)

これらの条件を満たすように \(A\) を並び替えれば良くて、これは昇順ソートすること同値です。