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」となる。
(書き出してみると分かります。)
点を線で繋ぐと以下のような表になる。
もう一つ仮に、
与えられた整数を「6,8,1,2,3」の5つとする。(例題1)
このとき、
隣り合う要素の合計が最大になる順番を考えると
「3,8,1,6,2」となる。
点を線で繋ぐと以下のような表になる。
上の二つを表を見ると、
どちらも
上下に線が動いていることが分かる。
(表がギザギザになっている)
つまり、点の動きが
「小さい大きい小さい大きい…」
となっていて
「小さい小さい」や「大きい大きい」
のような二回連続での減少や増加を続けていないことが分かる。
ここから、
隣り合う数字の差を最大化するためには
減少と増加を交互に繰り返せばいいということが分かる。
文字に置き換えて考える
仮に与えられた数字が4つだとして、
隣り合う要素の差の合計が最大になる順番として
「a,b,c,d」が考えられるとき、
表は以下のような形となるので
隣り合う要素の差の合計を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パターンが考えられる。
①小さい、大きい、小さい…
②大きい、小さい、大きい…
①について
隣り合う要素の差の合計を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); } }