C - Align

はじめに

競技プログラミングTenka1 Programmer Beginner Contest
C - Align
言語はC#
何かあればTwitter→@pirorirori_n712まで

問題

問題文

整数がN個与えられます。
i個目の整数はAiです。
これらを好きな順に一列に並べるとき、隣り合う要素の差の合計の最大値を求めてください。

制約

2≤N≤10^5
1≤Ai≤10^9
入力はすべて整数である

入力

N
A1
:
AN

出力

与えられた整数たちを好きな順に一列に並べるとき、隣り合う要素の差の合計の最大値を出力せよ。

解き方

Tenka1 Programmer Contest 2018 解説放送の解き方で解いています。

隣り合う要素の差が大きくなる形を考える

まず仮に、
与えられた整数を「1,2,3,4」の4つとする。
このとき、
隣り合う要素の合計が最大になる順番を考えると
「2,4,1,3」となる。
(書き出してみると分かります。)
点を線で繋ぐと以下のような表になる。
f:id:aoaoaoaoaoaoaoi:20181110230118p:plain
もう一つ仮に、
与えられた整数を「6,8,1,2,3」の5つとする。(例題1)
このとき、
隣り合う要素の合計が最大になる順番を考えると
「3,8,1,6,2」となる。
点を線で繋ぐと以下のような表になる。
f:id:aoaoaoaoaoaoaoi:20181110222958p:plain

上の二つを表を見ると、
どちらも
上下に線が動いていることが分かる。
(表がギザギザになっている)
つまり、点の動きが
「小さい大きい小さい大きい…」
となっていて
「小さい小さい」や「大きい大きい」
のような二回連続での減少や増加を続けていないことが分かる。

ここから、
隣り合う数字の差を最大化するためには
減少と増加を交互に繰り返せばいいということが分かる。

文字に置き換えて考える

仮に与えられた数字が4つだとして、
隣り合う要素の差の合計が最大になる順番として
「a,b,c,d」が考えられるとき、
表は以下のような形となるので
f:id:aoaoaoaoaoaoaoi:20181110224518p:plain
隣り合う要素の差の合計をSとすると

S=(b-a)+(b-c)+(d-c)

となる。
この式を変形させると以下のようになる。

S=-a+2b-2c+d
 =-2c-a+d+2b

Sは隣り合う要素の差の合計なので
この値を上の式に要素を当てはめた際に
一番大きくなるようにすれば
隣り合う要素の差の合計を最大にすることができる。
式は

S=-2c-a+d+2b

なので
前から小さいものから順番に
「c,a,d,b」に
当てはめていけばよいことが分かる。
例えば与えられた数が「1,2,3,4」であれば
「c」から順番に当てはめていき

S=-2*1-2+3+2*4

となる。
これを計算すると
S=7
であり、これが答えである。

さらに、
数字の数が増えたとき
どこが変化するのかも確かめておく。
隣り合う要素の差の合計が最大になる順番として
「a,b,c,d,e,f」が考えられるとき、
隣り合う要素の差の合計をSとすると

S=(b-a)+(b-c)+(d-c)+(d-e)+(f-e)

となる。
この式を変形させると以下のようになる。

S=-a+2b-2c+2d-2e+f
 = -2c-2e-a+f+2b+2d


S=-2c-2e-a+f+2b+2d

数字が4つのときの式が以下なので

S=-2c-a+d+2b

この二つを比べると
2倍して引く数」と「2倍して足す数」が
一つずつ増えていることが分かる。

上では数字が4つの場合を仮定したが、
これでは数字の数が奇数だった場合に対応できない。
そこで、数字の数が奇数だった場合も考える。
仮に与えられた数字が5つだとして、
隣り合う要素の差の合計が最大になる順番として
「a,b,c,d,e」が考えられるとき、
表は以下のような2パターンが考えられる。

①小さい、大きい、小さい…
f:id:aoaoaoaoaoaoaoi:20181110231205p:plain

②大きい、小さい、大きい…
f:id:aoaoaoaoaoaoaoi:20181110235222p:plain

①について
隣り合う要素の差の合計をSとすると

S=(b-a)+(b-c)+(d-c)+(d-e)

となる。
この式を変形させると以下のようになる。

S=-a+2b-2c+2d-e<br>
 =-2c-a-e+2b+2d<br>

Sは隣り合う要素の差の合計なので
この値を上の式に要素を当てはめた際に
一番大きくなるようにすれば
隣り合う要素の差の合計を最大にすることができる。
式は

S=-2c-a-e+2b+2d

なので
前から小さいものを順番に当てはめていけばよいことが分かる。
例えば与えられた数が「6,8,1,2,3」であれば
「c」から順番に「1,2,3,6,8」を当てはめていき

S=-2*1-2-3+2*6+2*8

となる。
これを計算すると
S=21となる。

②について
隣り合う要素の差の合計をSとすると

S=(a-b)+(c-b)+(c-d)+(e-d)

となる。
この式を変形させると以下のようになる。

S=a-2b+2c-2d+e
 =-2b-2d+a+e+2c

Sは隣り合う要素の差の合計なので
この値を上の式に要素を当てはめた際に
一番大きくなるようにすれば
隣り合う要素の差の合計を最大にすることができる。
式は

S=-2b-2d+a+e+2c

なので
前から小さいものを順番に当てはめていけばよいことが分かる。
例えば与えられた数が「6,8,1,2,3」であれば
「c」から順番に「1,2,3,6,8」を当てはめていき

S=-2*1-2*2+3+6+2*8

となる。
これを計算すると
S=19となる。
①の21の方が大きいので答えは21となる。

またこちらでも
数字の数が増えた場合について考える。
仮に与えられた数字が7つだとして、
隣り合う要素の差の合計が最大になる順番を
「a,b,c,d,e,f,g」とする。

①について
隣り合う要素の差の合計をSとすると

S=(b-a)+(b-c)+(d-c)+(d-e)+(f-e)+(f-g)

となる。
この式を変形させると以下のようになる。

S=-a+2b-2c+2d-2e+2f-g
 =-2c-2e-a-g+2b+2d+2f


S=-2c-2e-a-g+2b+2d+2f

数字が5つのときの式が以下なので
S=-2c-a-e+2b+2d
この二つを比べると
2倍して引く数」と「2倍して足す数」が
一つずつ増えていることが分かる。

②について
隣り合う要素の差の合計をSとすると

S=(a-b)+(c-b)+(c-d)+(e-d)+(e-f)+(g-f)

となる。
この式を変形させると以下のようになる。

S=a-2b+2c-2d+2e-2f+g<br>
 =-2b-2d-2f+a+g+2c+2e


S=-2b-2d-2f+a+g+2c+2e

数字が5つのときの式が以下なので
S=-2b-2d+a+e+2c
この二つを比べると
2倍して引く数」と「2倍して足す数」が
一つずつ増えていることが分かる。

コードを書く

数字の数に対応して、
汎用的にする処理を考えていく。
1.数字の数が偶数のとき
隣り合う数字の差の合計が最大になる並び順を
「a,b,c,d」とすると
隣り合う数字の差の合計をSとして
隣り合う数字の差の合計の最大は

S=-2c-a+d+2b

また
隣り合う数字の差の合計が最大になる並び順を
「a,b,c,d,e,f」とすると
隣り合う数字の差の合計をSとして
隣り合う数字の差の合計の最大は

S= -2c-2e-a+f+2b+2d

上の合計を出している2つの式を見ると
数字の数を半分にして
前は引き算、後ろは足し算をしていることが分かる。

引き算:青色
足し算:赤色
S=-2c-a+d+2b
S= -2c-2e-a+f+2b+2d

さらに、細分化して係数に注目すると
数字の数を半分にした数をnとすると

n-1番目までは-2
n番目は-1
n+1番目は+1
n+2番目以降は+2

となる。
(一番初めを1番目とする場合、
下のコードでは0始まりで書いているのでずれています)

2.数字の数が奇数のとき
①小さい、大きい、小さい…
隣り合う数字の差の合計が最大になる並び順を
「a,b,c,d,e」とすると
隣り合う数字の差の合計をSとして
隣り合う数字の差の合計の最大は

S=-2c-a-e+2b+2d

また
隣り合う数字の差の合計が最大になる並び順を
「a,b,c,d,e,f」とすると
隣り合う数字の差の合計をSとして
隣り合う数字の差の合計の最大は

S=-2c-2e-a-g+2b+2d+2f

上の合計を出している2つの式を見ると
数字の数を半分にした数をnとすると
n+1番目までは引き算、それ以降は足し算をしていることが分かる。

引き算:青色
足し算:赤色
S=-2c-a-e+2b+2d
S=-2c-2e-a-g+2b+2d+2f

さらに、
細分化して係数に注目すると
数字の数を半分にした数をnとすると

n-1番目までは-2
n番目とn+1番目は-1
n+2番目以降は+2

となる。
(一番初めを1番目とする場合、
下のコードでは0始まりで書いているのでずれています)

②大きい、小さい、大きい…
隣り合う数字の差の合計が最大になる並び順を
「a,b,c,d,e」とすると
隣り合う数字の差の合計をSとして
隣り合う数字の差の合計の最大は

S=-2b-2d+a+e+2c

また
隣り合う数字の差の合計が最大になる並び順を
「a,b,c,d,e,f」とすると
隣り合う数字の差の合計をSとして
隣り合う数字の差の合計の最大は

S=-2b-2d-2f+a+g+2c+2e

上の合計を出している2つの式を見ると
数字の数を半分にした数をnとすると
n+1番目までは引き算、それ以降は足し算をしていることが分かる。

引き算:青色
足し算:赤色
S=-2b-2d+a+e+2c
S=-2b-2d-2f+a+g+2c+2e

さらに、
細分化して係数に注目すると
数字の数を半分にした数をnとすると

n番目までは-2
n+1番目とn+2番目は+1
n+3番目以降は+2

となる。
(一番初めを1番目とする場合、
下のコードでは0始まりで書いているのでずれています)

コード

using System;
using System.Linq;
using System.Collections.Generic;

class Cmondai
{
    static void Main()
    {
        //数字の数を保存
        var n = Int32.Parse(Console.ReadLine());
        //並び替える対象の数字を入れるためのリストを用意
        var list = new List<long>();
        //並び替える対象の数字をリストに追加
        for (int i = 0; i < n; ++i) list.Add(Int64.Parse(Console.ReadLine()));
        //小さい順に数字を並びかえる
        var line = list.OrderBy(x => x).ToArray();
        //隣り合う数字の差の最大の合計を入れる変数(答え)
        var ans = 0L;
        //数字の数を2で割ってあとで使えるようにしておく
        var m = n / 2;
        //数字の数が偶数のとき
        if (n % 2 == 0)
        {
            //数字の数ぶんループを回す
            for (int i = 0; i < n; ++i)
            {
                //係数ごとに分ける
                //m-1番目までは-2
                if (i < m - 1) ans += (-2) * line[i];
                //m番目は - 1
                else if (i == m - 1) ans -= line[i];
                //m番目は+1
                else if (i == m) ans += line[i];
                //m + 1番目以降は + 2
                else ans += 2 * line[i];
            }
        }
        else
        {
            var a = 0L;
            var b = 0L;
            //数字の数ぶんループを回す
            //大きい、小さい、大きい…
            for (int i = 0; i < n; ++i)
            {
                //m番目とm+1番目は+1
                if (i == m || i == m + 1) a += line[i];
                //m-1番目までは-2
                else if (i < m) a -= 2 * line[i];
                //m+2番目以降は+2
                else a += 2 * line[i];
            }
            //小さい、大きい、小さい…
            for (int i = 0; i < n; ++i)
            {
                //m番目とm+1番目は-1
                if (i == m - 1 || i == m) b -= line[i];
                //m-1番目までは-2
                else if (i < m - 1) b -= 2 * line[i];
                //m+2番目以降は+2
                else b += 2 * line[i];
            }
            //大きい始まりと小さい始まりを比べて
            //数の大きいほうを答えとする
            ans = Math.Max(a, b);
        }
        //答えを出力
        Console.WriteLine(ans);
    }
}