AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。
出典：
Tenka1 Programmer Beginner Contest C – Align
この問題、きちんと考察するのは意外と面倒なところもあるので、ついエイヤッと貪欲で実装して通してしまった人も多いのではないだろうか……なんて。しかし、通りはするもののそれが正当である証明はやっぱり難しいので、素直に考察しておく。
# Tenka1 Programmer Beginner Contest C - Align
# https://atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_c
# 数列 隣接 差分 最大 考察 貪欲法
# 直感としては、大小大小……もしくは小大小大……という具合に
# 並んでいるのがよさそうではある。
# 仮に途中に a <= b <= c となる並びがあった場合、
# その差分の合計は (c - b) + (b - a) = c - a となるが、
# b を移動した b a c あるいは a c b という並びのほうが、
# 差分の合計が (c - a) + (b - a) と大きくなる。
# さて、仮に大小大小……で数列を作成するとして、
# abcdef という並びの場合、その差分の合計は
# (a-b) + (c-b) + (c-d) + (e-d) + (e-f) =
# a + 2c + 2e - (2b + 2d + f) という感じになる。
# つまり、両端でない数は必ず 2回足されるか引かれるかする。
# よって考慮すべき内容としては、
# 1）足す数に分類するか引く数に分類するか
# 2）端をどうするか
# だけでいい。
def main():
N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()
# 偶数個の場合
if N % 2 == 0:
plus = A[N//2:]
minus = A[:N//2]
result = 2 * sum(plus) - 2 * sum(minus)
# 足す数は一番小さいものを、
# 引く数は一番大きいものを端に持っていく
result = result - plus[0] + minus[-1]
# 奇数個の場合
else:
plus = A[N//2+1:]
minus = A[:N//2]
mid = A[N//2]
tmp_r = 2 * sum(plus) - 2 * sum(minus)
# 中央の数を足す方にする場合（大小大小～の並びになる）
# 両端が足す数になる。足す数のうち小さいものから順に 2個
# 端に移動するが、そのうち1つは中央の数
res1 = (tmp_r + mid * 2) - mid - plus[0]
# 中央の数を引く方にする場合（小大小大～の並びになる）
# 両端が引く数に（以下略
res2 = (tmp_r - mid * 2) + mid + minus[-1]
# 比べて大きい方を取る
result = max(res1, res2)
print(result)
main()
# 実は貪欲法でも通る。
# 残りから一番大きいもの or 一番小さいものを、
# 点数が高くなるように次々に数列の左右に追加していく感じ。
from collections import deque
def main2():
N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()
# 一番大きいのを取り出し、数列の元とする。
# 以下両端のみ管理。
left = right = A.pop()
result = 0
rem = deque(A)
while rem:
scores = []
# (右|左)から取って(右|左)につける
rr = abs(right - rem[-1])
rl = abs(left - rem[-1])
lr = abs(right - rem[0])
ll = abs(left - rem[0])
# 左右どちらから取る？
if max(rr, rl) >= max(lr, ll):
pick = rem.pop()
else:
pick = rem.popleft()
# 一番差分が大きくなるようにつける
if abs(pick - right) >= abs(pick - left):
result += abs(pick - right)
right = pick
else:
result += abs(pick - left)
left = pick
print(result)
# main2()