Problem:


Score : 300 points

Problem Statement

Snuke has an integer sequence A of length N.

He will freely choose an integer b.
Here, he will get sad if A_i and b+i are far from each other.
More specifically, the sadness of Snuke is calculated as follows:

abs(A_1 - (b+1)) + abs(A_2 - (b+2)) + ... + abs(A_N - (b+N))

Here, abs(x) is a function that returns the absolute value of x.

Find the minimum possible sadness of Snuke.

Constraints

1 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the minimum possible sadness of Snuke.

Sample Input 1

5
2 2 3 5 5

Sample Output 1

2

If we choose b=0, the sadness of Snuke would be abs(2-(0+1))+abs(2-(0+2))+abs(3-(0+3))+abs(5-(0+4))+abs(5-(0+5))=2.
Any choice of b does not make the sadness of Snuke less than 2, so the answer is 2.

Sample Input 2

9
1 2 3 4 5 6 7 8 9

Sample Output 2

0

Sample Input 3

6
6 5 4 3 2 1

Sample Output 3

18

Sample Input 4

7
1 1 1 1 2 3 4

Sample Output 4

6



Sample input:
5
2 2 3 5 5


Sample output:
2

Submission status: Accepted

Solution code:
# median を import する
from statistics import median

# N と Ai を標準入力
N = int(input())
listNumsAs = list(map(int,input().split()))

# 空のリスト listNumsBs を用意
listNumsBs = []

# listNumAs の各要素から、その (index + 1) の数を引いた (Ai - (i + 1)) をリスト listNumsBs に順番に代入
for index in range(len(listNumsAs)):
    listNumsBs.append(listNumsAs[index] - index - 1)

# listNumsBs を昇順にソートする
listNumsBs.sort()

# listNumsBs の中央値を med に代入する
med = int(median(listNumsBs))

listSadnessA1 = [abs(s - med - N) for s in listNumsBs]
minimumSum = sum(listSadnessA1)

# listNumsBs の中央値 ± N の範囲の変数 b で処理を繰り返す
for b in range(med - 10, med + 10):
    
    # 悲しさ指数のリスト listSadness に (Bi - b) の絶対値の計算結果を順番に代入する
    listSadness = [abs(s - b) for s in listNumsBs]
       
    if sum(listSadness) < minimumSum:
        minimumSum = sum(listSadness)
        listTruthSadness = listSadness
        truthB = b

print(minimumSum)

Submission status: Accepted

Solution code:
a = int(input())
b = input().split()
c = []
for i in range(a):
  c.append(int(b[i]))
g = []
for i in range(a):
  g.append(c[i] - i-1)
g.sort()
d = g[int(a/2)]
f = 0
for i in range(a):
  e = abs(c[i]-(d+i+1))
  f += e
print(f)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
diff = []
for i, index in enumerate(a,1):
    diff.append(i-index)

diff.sort()
if n % 2 == 1:
    b = diff[n // 2]
    tmp = map(lambda x: x - b, diff)
    print(sum( map(abs,tmp )))
else:
    b1 = diff[n // 2 - 1]
    b2 = diff[n // 2]
    tmp1 = map(lambda x: x - b1, diff)
    tmp2 = map(lambda x: x - b2, diff)
    ans1 = sum( map(abs,tmp1 ))
    ans2 = sum( map(abs,tmp2 ))
    print(min(ans1,ans2))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(n) - int(i) for i, n in enumerate(input().split())]
A.sort()
print(sum([abs(n - A[N // 2]) for n in A]))

Submission status: Accepted

Solution code:
from statistics import median
N = int(input())
A = [int(i) for i in input().split()]

B = [A[i] - (i+1) for i in range(N)]
b = int(median(B))

C = [abs(B[i] - b) for i in range(N)]

print(sum(C))

Submission status: Accepted

Solution code:
N = int(input())
A_list = list(map(int, input().split()))

dif = []
for idx, v in enumerate(A_list, 1):
    dif.append(v - idx)

dif.sort()
if len(dif) % 2 == 1:
    b = dif[len(dif) // 2]
    print(sum(map(abs, (map(lambda x: x - b, dif)))))
else:
    b1 = dif[len(dif) // 2 - 1]
    b2 = dif[len(dif) // 2]
    print(min(sum(map(abs, (map(lambda x: x - b1, dif)))),
              sum(map(abs, (map(lambda x: x - b2, dif))))))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
a = [int(_) - (i + 1) for i, _ in enumerate(input().split())]

# INF = 10**10
# grief = INF
# for b in set(a):
#     tmp = sum([abs(ai - b) for ai in a])
#     if tmp < grief:
#         bb = b
#         grief = tmp

# print(grief)  # running time limit error

a.sort()
med = a[len(a) // 2]
grief = sum([abs(ai - med) for ai in a])
print(grief)

Submission status: Accepted

Solution code:
from statistics import median

n = int(input())
xs = [int(i) for i in input().split()]

ys = [x-i-1 for i,x in enumerate(xs)]
m = int(median(ys))

print(sum(abs(y-m) for y in ys))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]

for i in range(N):
    A[i] = A[i] - (i+1)

A.sort()

medium = A[int(N/2)]

s = 0
for i in range(N):
    s = s + abs(A[i]-medium)

print(s)

Submission status: Accepted

Solution code:
N = int(input())
L = list(map(int,input().split()))

cnt = 0

c = []
for i in range(N):
    c.append(L[i] - (i + 1))

c.sort()
if N % 2 == 0:
    b = (c[N // 2] + c[N // 2 - 1]) / 2
else:
    b = c[N // 2]
for i in range(N):
    cnt += abs(L[i] - (b + i + 1))
print(int(cnt))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

A_sunuke = sorted(a - (i+1) for (i,a) in enumerate(A))

center = A_sunuke[len(A) // 2]

rtn = sum([abs(a - center) for a in A_sunuke])
print(rtn)

Submission status: Accepted

Solution code:
import statistics
n = int(input())
a_list = list(map(int, input().split()))

pro_list = [a_list[i-1] - i for i in range(1, n+1)]
ave = int(statistics.mean(pro_list))
med = int(statistics.median(pro_list))
b_list = [ave - 1 for i in range(10)] + [ave + i for i in range(10)]
b_list += [med - 1 for i in range(10)] + [med + i for i in range(10)]

ans = [sum([abs(pro-b)for pro in pro_list]) for b in b_list]
print(min(ans))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
i = 1
ans = 0
for j in range(len(A)):
    A[j] = A[j] - i
    i += 1

A.sort()
#print(A)
if len(A) % 2 == 1:
    b = A[((len(A) + 1) // 2) - 1]
#    print(b)
    for j in range(len(A)):
        ans = ans + abs(A[j] - b)
    print(ans)

else:
    b = (A[(len(A) // 2) - 1] + A[(len(A) // 2)]) // 2
#    print(b)
    for j in range(len(A)):
        ans = ans + abs(A[j] - b)
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(_) for _ in input().split()]

xs = sorted(a - i - 1 for i, a in enumerate(A))

center = xs[len(xs)//2]

r = sum(abs(x - center) for x in xs)

print(r)

Submission status: Accepted

Solution code:
import numpy as np
def sadness(l, b):
    sad = 0
    for a in l:
        sad += abs(a - b)
    return int(sad)

if __name__ == '__main__':
    n = int(input())
    l = list(map(int, input().split()))
    if n == 1:
        print('0')
        exit()

    for i in range(len(l)):
        l[i] -= (i+1)
    nl = np.array(l)
    nl.sort()
    m = np.median(nl)

    s = sadness(l, m)
    print("{}".format(s))

Submission status: Accepted

Solution code:
N = int(input())
A_list = list(map(int, input().split()))

for i in range(N):
    A_list[i] = A_list[i] - i - 1

A_list = sorted(A_list)
if(N % 2 == 0):
    key = N // 2
else:
    key = (N - 1) // 2
b = A_list[key]
sadness = 0

for A in A_list:
    sadness += abs(A - b)

print(sadness)

Submission status: Accepted

Solution code:
def main():
    """
    1 <=  N <= 2 * 10^5
    1 <= ai <= 10^9
    """
    N = int(input())
    *A, = map(int, input().split())

    #ans = WA3(N, A)
    ans = editorial(N, A)
    print(ans)


def editorial(N, A):
    ans = 0
    C = sorted(a - i for i, a in enumerate(A, 1))
    if N % 2 == 1:
        b = C[N // 2]
    else:
        # 中央値だけど、整数？
        s = C[N // 2 - 1] + C[N // 2 - 1]
        b = s // 2

    ans = sum(abs(c - b) for c in C)
    return ans


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    """
    1 <=  N <= 2 * 10^5
    1 <= ai <= 10^9
    """
    N = int(input())
    *A, = map(int, input().split())

    #ans = WA3(N, A)
    ans = editorial(N, A)
    print(ans)


def editorial(N, A):
    ans = 0
    C = sorted(a - i for i, a in enumerate(A, 1))
    if N % 2 == 1:
        b = C[N // 2]
    else:
        # 中央値だけど、整数？
        s = C[N // 2 - 1] + C[N // 2 - 1]
        b = (s + 1) // 2

    ans = sum(abs(c - b) for c in C)
    return ans


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:


a = int(raw_input())
lll = map(int, raw_input().split())

b=sorted([l-i for i,l in enumerate(lll,1)])
med= b[int(len(b)/2)]
ret= sum([abs(x-med) for x in b])
print ret

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=sorted([A[i]-i for i in range(N)])
if N%2==0:
	C=int((B[int(N/2)]+B[int(N/2-1)])/2)
else:
	C=B[int((N-1)/2)]
print(sum([abs(b-C) for b in B]))

Submission status: Accepted

Solution code:
from operator import itemgetter
N=int(input())
A=list(map(int,input().split()))

differences=[]
for index, item in enumerate(A):
    differences.append(item-(index+1))
differences.sort()

if len(differences)%2==1:
    b=differences[int(len(differences)/2)-1+1]
else:
    b=differences[int(len(differences)/2)-1]

answer=0
for index,item in enumerate(differences):
    answer+=abs(item-b)
print(answer)

Submission status: Accepted

Solution code:
from numpy import cumsum
from bisect import bisect
N = int(input())
A = [int(i) for i in input().split()]
X = [v - i - 1 for i, v in enumerate(A)]
X.sort()
S = cumsum(X)
ans = float('inf')
for bc in set(X):
    i = bisect(X, bc)
    a = -1 * S[i - 1] + bc * i + (S[N - 1] - S[i - 1]) + -1 * bc * (N - i)
    ans = min(ans, a)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
def calc_sadness(points, b):
    return sum([abs(y - (b + x)) for x, y in points])

points = [(i+1, y) for i, y in enumerate(A)]

# y = x + b
# b = y - x
b_list = [y - x for x, y in points]
b_list.sort(reverse=True)

max_b = b_list[0]
min_b = b_list[-1]

best_ind = len(b_list)//2

minimum = calc_sadness(points, b_list[best_ind])

print(minimum)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = []
for i in range(n):
	b.append(a[i]-(i+1))
b.sort()
if n%2 == 1:
	median = b[n//2]
else:
	median = (b[n//2]+b[n//2-1])/2
ans = 0
for i in range(n):
	ans += abs(a[i]-(median+i+1))
print(int(ans))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
B = [A[i]-i for i in range(N)]
B.sort()
b = B[int(N//2)]
C = [abs(B[i]-b) for i in range(N)]
print(sum(C))

Submission status: Accepted

Solution code:
import collections
from statistics import median

n = int(input())
array = list(map(int, input().split()))

for i in range(0, n):
    array[i] = array[i] - (i + 1)
c = collections.Counter(array)
elem = int(c.most_common()[0][0])

# print(c.most_common()[0][0])
# print(array)
# print(elem)
# if c.most_common()[0][1] != 1:
#     # print("test")
#     for j in range(0, n):
#         array[j] = abs(array[j] - elem)
# else:
#     for j in range(0, n):
#         array[j] = abs(array[j])
b = int(median(array))
for j in range(0, n):
    array[j] = int(abs(array[j] - b))

print(sum(array))

Submission status: Accepted

Solution code:
import statistics

N = int(input())
A = [int(a) for a in input().split()]
B = [A[b]-(b+1) for b in range(N)]
B.sort()
b = statistics.median(B)
ans = sum([abs(i-int(b)) for i in B])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

B = [A[i] - (i + 1) for i in range(N)]

B.sort()

b = B[len(B) // 2]

ans = 0

for j in range(N):
    ans += abs(A[j] - (b + j + 1))

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))

for i in range(n):
    a[i]=a[i]-i-1

a=sorted(a)

median=a[len(a)//2]

ans=0

for i in range(n):
    ans += abs(a[i]-median)

print(ans)

Submission status: Accepted

Solution code:
#abc102c

n=int(raw_input())
a=map(int,raw_input().split())
b=[]
for i in xrange(n):
 b.append(a[i]-i)
c=sorted(b)
print sum(map(lambda x: abs(x-c[n/2]),c))

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split(" ")))

B = [y - x - 1 for x, y in enumerate(a)]
B_s = sorted(B)

# if odd 
if N % 2 == 1 :  
    median = [B_s[int(N / 2)]]
else :
    median = [B_s[int(N / 2)], B_s[int(N / 2) + 1]]

min_sum = None 

for m in median :
    sum_over = 0
    
    for i, j in enumerate(a) :
        sum_over += abs(j - (m + i + 1))

    if min_sum == None or sum_over < min_sum :
        min_sum = sum_over
        
print(min_sum)

Submission status: Accepted

Solution code:
def merge(l, r, compare):
    result = []
    i, j = 0, 0
    while i < len(l) and j < len(r):
        if compare(l[i], r[j]):
            result.append(l[i])
            i += 1
        else:
            result.append(r[j])
            j += 1
    while (i < len(l)):
        result.append(l[i])
        i += 1
    while (j < len(r)):
        result.append(r[j])
        j += 1
    return result
def mergesort(L, compare = lambda x, y : x < y):
    if len(L) < 2:
        return L[:]
    else:
        middle = len(L)//2
        l = mergesort(L[:middle], compare)
        r = mergesort(L[middle:], compare)
        return merge(l, r, compare)

N = int(input())
An = list(map(int, input().split()))
for i in range(N):
    An[i] -= i + 1
Bn = mergesort(An)
midN = Bn[N//2]

ans = 0
for i in range(N):
    ans += abs(Bn[i] - midN)

print(ans)

Submission status: Accepted

Solution code:
from statistics import median
n = int(input())
a = [int(i) for i in input().split()]
b = []

for i in range(n):
    b.append(a[i] - (i+1))

m = int(median(b))

sum = 0
for i in range(n):
    sum += abs(a[i] - (m+i+1))

print(sum)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int, input().split()))
for i in range(n):
    a[i]-=i+1
a.sort()
m=a[len(a)//2]
score=list(map(lambda x:abs(x-m), a))
print(sum(score))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

def sunuke(b):
    ret = 0
    sub = 1
    for a in A:
        ret += abs(a - (b+ sub))
        sub += 1
    return ret


B = []

sub = 1
for a in A:
    b = a - sub
    B.append(b)
    sub += 1

B.sort()
b1 = N // 2
if N < 3:
    print(sunuke(B[b1]))
    exit()

b2 = b1 + 1
b1_s = sunuke(B[b1])
b2_s = sunuke(B[b2])
if b1_s < b2_s:
    print(b1_s)
else:
    print(b2_s)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))

B = [A[i]-i-1 for i in range(N)]
B.sort()
if N%2:
        b = B[(N-1)//2]
else:
        b = (B[N//2]+B[N//2 - 1])//2

print(sum([abs(A[i]-b-i-1) for i in range(N)]))

Submission status: Accepted

Solution code:
N=int(input())
A=sorted(a-i for i,a in enumerate(map(int,input().split())))
print(sum(A[N//2:])-sum(A[:-~N//2]))

Submission status: Accepted

Solution code:
import math
n = int(input())
al = list(map(int, input().split()))

for i, a in enumerate(al, 1):
    al[i-1] = a - i

al = sorted(al)
if len(al) % 2 != 0:
    b = al[(math.floor(len(al)/2))]
    ans = sum([abs(a-b) for a in al])
    print(ans)
else:
    b1, b2 = al[math.floor(len(al)/2)], al[math.floor(len(al)/2)-1]
    tmp1 = sum([abs(a-b1) for a in al])
    tmp2 = sum([abs(a-b2) for a in al])
    ans = min(tmp1, tmp2)
    print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
import statistics
B=[0]*N
answer=0
for i in range(N):
	B[i]=A[i]-(i+1)
med=int(statistics.median(B))

for i in range(N):
	answer+=(abs(B[i]-med))
print(answer)

Submission status: Accepted

Solution code:
n = int(input())
A = [int(i) for i in input().split()]

B = []

for i, a in zip(range(1, n+1), A):
   B.append(a - i)

B.sort()
if n % 2 == 0:
    b = (B[n//2] + B[n//2-1]) // 2
else:
    b = B[n//2]

sum = 0

for i, a in zip(range(1, n+1), A):
    sum += abs(a-(b+i))
    
print(sum)

Submission status: Accepted

Solution code:
from sys import stdin, stdout
input = lambda: stdin.readline().rstrip()
write = stdout.write

def main():
    N = int(input())
    A = tuple(map(int, input().split()))

    num = [a - i for i, a in enumerate(A, start=1)]
    num.sort()
    b = num[N//2]
    ans = sum([abs(a - (b + i)) for i, a in enumerate(A, start=1)])
    print(ans)

main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

a = sorted([r - (i + 1) for i, r in enumerate(a)])
b = a[(n - 1) // 2]

print(sum([abs(r - b) for r in a]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from sys import stdin
N = int(input())
A = [int(i) for i in input().split()]
A_i = sorted([a - (i + 1) for i, a in enumerate(A)])

if N % 2 != 0:
    idx_of_median = int(N // 2)  # 奇数時のインデックス [0, 1, 2, 3, 4] -> 5//2 = 2
    print(sum([abs(a - A_i[idx_of_median])for a in A_i]))
else:
    idx_of_median = int(N / 2) # 奇数時のインデックス [0, 1, 2, 3, 4, 5] -> 6/2 = 3 or 6/2 - 1 = 2
    print(sum([abs(a - A_i[idx_of_median]) for a in A_i]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from sys import stdin
N = int(stdin.readline().rstrip())
A = [int(i) for i in stdin.readline().rstrip().split()]
A_i = sorted([a - (i + 1) for i, a in enumerate(A)])

if N % 2 != 0:
    idx_of_median = int(N // 2)  # 奇数時のインデックス [0, 1, 2, 3, 4] -> 5//2 = 2
    print(sum([abs(a - A_i[idx_of_median])for a in A_i]))
else:
    idx_of_median = int(N / 2) # 奇数時のインデックス [0, 1, 2, 3, 4, 5] -> 6/2 = 3 or 6/2 - 1 = 2
    print(sum([abs(a - A_i[idx_of_median]) for a in A_i]))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

B = sorted([(a - (n + 1)) for n, a in enumerate(A)])

M = -1
if N % 2 != 0:
    i = N // 2 
    M = B[i]
else:
    i1 = N // 2 - 1
    i2 = i1 + 1
    M = (B[i1] + B[i2]) // 2

AE = [abs(a - (M + (n + 1))) for n, a in enumerate(A)]
R = sum(AE)

print(R)

Submission status: Accepted

Solution code:
from math import floor, ceil

N = int(input())
A = list(map(int, input().split()))

B = [A[i] - (i+1) for i in range(N)]
B.sort()
b = (B[floor((N-1)/2)] + B[ceil((N-1)/2)]) // 2
ans = sum([abs(a-b) for a in B])
print(ans)

Submission status: Accepted

Solution code:
import statistics

def calc_sad_param(b):
    global numbers
    sad_param = 0
    for i in range(len(numbers)):
        sad_param += abs(numbers[i] - i - b)
    return int(sad_param)

n = int(input())
numbers = list(map(int, input().split()))
b_list = [numbers[i] - i for i in range(n)]
print(calc_sad_param(statistics.median(b_list)))

Submission status: Accepted

Solution code:
import math
import statistics

def ret(l, b):
  r = 0
  for i in range(len(l)):
    r += int(math.fabs(l[i] - b - i - 1))
  return r

input()
l = list(map(int, input().split()))
a = []
for i in range(len(l)):
  a.append(l[i] - i - 1)
x = statistics.median_low(sorted(a))
y = statistics.median_high(sorted(a))
print(min(ret(l, x), ret(l,y)))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

N = int(input())
AN = list(map(int, input().split()))

# Ai - i の各値を用意してソートする
BN = [AN[i] - (i + 1) for i in range(N)]
BN.sort()
# 中央値を取る
b = BN[len(BN) // 2]
# 最適な b で実際の計算をする
ans = 0
for i in range(N):
    ans += abs(AN[i] - (b + i + 1))
print(ans)

Submission status: Accepted

Solution code:
import math
import sys

sys.setrecursionlimit(10**8)

N = int(input())

A = list(map(int,input().split()))

B = []
sum = 0

for i in range(N):
	aa = A[i] - i - 1
	B.append(aa)
	
B.sort()

if N%2 == 0:
	best = (B[N//2] + B[N//2-1])//2
else:
	best = B[N//2]

ans = 0
	
for i in range(N):
	ans += abs(B[i]-best)
	

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from statistics import median
n = int(stdin.readline().rstrip())
a = [int(x) for x in stdin.readline().rstrip().split()]
bi = [x -( i +1) for i,x in enumerate(a)]
b = median(bi)
s = 0
i = 0
while i < n:
    s += abs(bi[i] - b)
    i = i+1
print(int(s))

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
a = list(map(int,input().split()))
for i in range(n): a[i] -= i+1
a=np.array(a)
a.sort()
x= a[(n-1)//2] if n%2==1 else round((a[n//2-1]+a[n//2])/2.)
a=a-x
print(int(sum(abs(a))))

Submission status: Accepted

Solution code:
import statistics

n = int(input())
l = input().split()
lst = list(map(int,l))
x = []

for i in range(n):
    x.append(0)
    x[i] = lst[i] - (i+1)

#print(x)
#x.sort()
#print(x)

#b = x[n//2]

b = statistics.median(x)
b = int(b)
#print(b)

sad = 0

#print(lst)

for i in range(n):
    sad += abs(lst[i]-b-i-1)

print(sad)

Submission status: Accepted

Solution code:
N=int(input())
s=list(map(int,input().split()))
for i in range(N):
    s[i]-=i
s.sort()
print(sum(list(map(lambda x: abs(x-s[N//2]),s))))

Submission status: Accepted

Solution code:
# 整数列A 
# abs(A1-(b+1))+abs(A2-(b+2))+...+abs(An-(b+N))の最小値
# bは任意
# すなわち、その時のbを求めれば良い問題

# 結局、bを、Ai-iの中央値にすれば最適解。

def calcVal(b):
	# print(b)
	val = 0
	for n in range(N):
		val += abs(A[n]-(b+n+1))
		# print(A[n])
		# print(n)
		# print(val)
		# print(abs(A[n]-(b+n+1)))
		# print("")
	return val

N=int(input())
A=list(map(int,input().split()))

M=[]

for i,a in enumerate(A):
	#if a - (i+1) not in M:
	M.append( a - (i+1) )

M.sort()
lenM=len(M)

if lenM==1:
	ans=calcVal(M[0])

elif lenM==2:
	ans=min(calcVal(M[0]),calcVal(M[1]))


else:
	med1=lenM//2-1
	med2=lenM//2
	#print(M)
	ans=min(calcVal(M[med1]),calcVal(M[med2]),calcVal(0))



print(ans)

Submission status: Accepted

Solution code:
import numpy as np
ans=0
N=int(input())
s1,s_1,s0=[],[],[]
s=list(map(int,input().split()))
s_=np.array(s)-np.array(range(N))
for i in s_:
    if i<0:
        s_1.append(i)
    elif i==0:
        s0.append(i)
    else:
        s1.append(i)
if len(s1)==len(s_1) or (max(len(s1),len(s_1))<=min(len(s1),len(s_1))+len(s0)):
    print(-1*sum(s_1)+sum(s1))
    exit()
s1=sorted(s1)
s_1=sorted(s_1)
p=len(s1)-len(s_1)-len(s0)
q=len(s_1)-len(s1)-len(s0)
t=(max(p,q)-1)//2
if p>0:
    t=s1[t]
if q>0:
    t=s_1[t*(-1)-1]
ss=s1+s0+s_1
for i in ss:
    ans+=abs(i-t)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int, input().split()))
ans = 0

for i in range(n):
  l[i] -= i + 1

l = sorted(l)
b = l[n//2]

for i in l:
  ans += abs(i - b)

print(ans)

Submission status: Accepted

Solution code:
N=int(input())//2
A=sorted(a-i-1 for i,a in enumerate(map(int,input().split())))
print(sum(abs(a-A[N])for a in A))

Submission status: Accepted

Solution code:
N=int(input())
p,q=0,0
import numpy as np
s=list(map(int,input().split()))
s=np.array(s)-np.array(range(N))
s=sorted(s)
t=[N//2,(N-1)//2]
s1=s-np.ones((N))*s[t[0]]
s2=s-np.ones((N))*s[t[0]]
for i in s1:
    p+=abs(i)
for i in s2:
    q+=abs(i)
print(int(min(p,q)))

Submission status: Accepted

Solution code:
n = int(input())
x = [int(i) for i in input().split()]
for i in range(n): x[i]-=(i+1)
x,ans = sorted(x),0
if n%2==1: m = x[(n-1)//2]
else: m = (x[n//2]+x[n//2-1])//2
for i in x: ans+=abs(i-m)
print(ans)

Submission status: Accepted

Solution code:
from statistics import median
N = int(input())
AList = list(map(int, input().split()))
 
L = []
m = 0
for j in range(1, N+1):
    L.append(AList[j-1] - j)
m = median(L)
 
p = 0
for j in range(1, N+1):
    p += abs(AList[j-1] - j - m)
 
print(int(p))

Submission status: Accepted

Solution code:
import numpy as np
def absnuke(a, b, n):
    sum = 0
    for i in range(n):
        sum += abs(a[i]-(b+i+1))
    return sum

n = int(input())
a = list(map(int, input().split()))

b = [a[i]-(i+1) for i in range(n)]
c = sorted(b)
x = int(np.median(c))
print(absnuke(a, x, n))

Submission status: Accepted

Solution code:
import statistics

N = int(input())
A = list(map(int, input().split()))
B = []
li = []
for i in range(N):
  B.append(A[i] - (i+1))
b = int(statistics.median(B))
for i in range(N):
  li.append(abs(A[i] - (b+i+1)))
print(sum(li))

Submission status: Accepted

Solution code:
N = int(input())
An = list(map(int, input().split()))

for n in range(N):
    An[n] -= (n+1)

An.sort()

if (N-1) % 2 != 0:
    m = N//2 - 1
else:
    m = (N-1)//2

bf = -sum(An[0:m+1:]) + (m+1)*An[m]
af = sum(An[m+1::]) - (N-m-1)*An[m]
ans = bf + af
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(t) for t in input().split()]
if len(A) != N: raise

p = [A[i-1] - i for i in range(1, N+1)]
p.sort()

b = p[N // 2]
print(sum(abs(x - b) for x in p))

Submission status: Accepted

Solution code:
N = int(input())
A = map(int, input().split())
B = list(A_i - (i + 1) for i, A_i in enumerate(A))
B_sorted = sorted(B)

ans = []
##中央値のインデックスmを求める
if N % 2 == 1:
    ##Nが奇数: 中央値のインデックスを求める
    m = int((N - 1) / 2 + 1) - 1
    b = B_sorted[m]
    ans += [sum(abs(x - b) for x in B_sorted)]
else:
    ##Nが偶数: 中央値を計算する元になる2数のインデックスを求める
    for m in range(int(N / 2) - 1, int(N / 2) + 1):
        b = B_sorted[m]
        ans += [sum(abs(x - b) for x in B_sorted)]    
print(min(ans))

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
a_list = list(map(int, input().split()))


a_nparray=np.array(a_list)
i_nparray=np.array(range(1,len(a_list)+1))

bi_nparray=a_nparray-i_nparray

b=int(np.median(bi_nparray))

ans=0
for i in range(len(a_list)):
  ans += abs(a_list[i]-(b+(i+1)))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

input_list = []
index = 1
for i in input().split():
    item = int(i) - index
    input_list.append(item)
    index += 1

input_list.sort()
b = input_list[N//2]

print(sum(map(lambda x: abs(x-b), input_list)))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    a[i]-=(i+1)
a.sort()
b=a[n//2]
ans=0

for i in range(n):
    ans+=abs(a[i]-b)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

A_sorted = sorted([A[i] - (i+1) for i in range(N)])

if len(A) != 1:
    b = A_sorted[int((len(A)-1)/2)]
    b2 = A_sorted[int((len(A)-1)/2 + 1)]
    sad_1 = sum([abs(A_sorted[i] - b) for i in range(N)])
    sad_2 = sum([abs(A_sorted[i] - b2) for i in range(N)])
    print(min(sad_1, sad_2))
else:
    print('0')

Submission status: Accepted

Solution code:
import itertools, math
N = int(input())
A = list(map(int,input().split()))
C = [A[i] - (i+1) for i in range(N)]

def SAD(C,b):
	S = 0
	for i in range(N):
		S += abs(C[i] - b)
	return S

MAX, MIN = max(C)+1, min(C)

i = 0
while MAX - MIN > 1:
	mid = (MIN + MAX)//2
#	print((MIN,mid,MAX,":",SAD(C,mid) - SAD(C,mid-1)))
	if 	SAD(C,mid) - SAD(C,mid-1) < 0:
		MIN = mid
	else:
		MAX =mid
print(SAD(C,MIN))

Submission status: Accepted

Solution code:
N=input()
A=map(int, raw_input().split())
B=range(1,N+1)
 
C=[]
for x,y in zip(A,B):
	C.append(x-y)

C.sort()

m=0
if len(C)%2==1:
	m=C[len(C)/2]
else:
	m=(C[len(C)/2-1]+C[len(C)/2])/2

	
ans=0
for x in C:
	ans+=abs(-1*m+x)
print ans

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

n = int(input())
A = list(map(int, input().split()))
A = [A[i]-(i+1) for i in range(n)]
A.sort()

if n == 1:
    print(0)
    exit()

ans = 10**100
for i in [n//2-1, n//2]:
    ans = min(ans, sum([abs(A[j]-A[i]) for j in range(n)]))

print(ans)

Submission status: Accepted

Solution code:
N=input()
A=map(int, raw_input().split())
B=range(1,N+1)
 
C=[]
for x,y in zip(A,B):
	C.append(x-y)

C.sort()

m=0
if len(C)%2==1:
	m=C[len(C)/2]
else:
	m=(C[len(C)/2-1]+C[len(C)/2])/2

	
t=0
for x in C:
	t+=abs(-1*m+x)
print t

Submission status: Accepted

Solution code:
def c_linear_approximation(N, A):
    import numpy
    B = numpy.array([a-k for k, a in enumerate(A)])  # B_k = A_k - k
    b = int(numpy.median(B))  # Bの中央値を選ぶのが最適
    ans = numpy.sum(abs(B - b))  # 実際に悲しみを計算
    return ans

N = int(input())
A = [int(i) for i in input().split()]
print(c_linear_approximation(N, A))

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    B = []
    ans = 0
 
    for i, a in enumerate(A):
        B.append(a - i - 1)

    B.sort()

    b = B[len(B)//2]
    for i, a in enumerate(A):
        ans += abs(a - b - i - 1)

    print(ans)

Submission status: Accepted

Solution code:
import collections
 
N = int(input())
A = [int(i) for i in input().split()]
 
sub = [A[i]-(i+1) for i in range(N)]
res = 0
sub = sorted(sub)
b = sub[int(N/2)]
 
res = 0
for i in range(N):
    res += abs(A[i]-(b+i+1))
 
print(res)

Submission status: Accepted

Solution code:
n = int(input())
l = input().split()
lst = list(map(int,l))
x = []

for i in range(n):
    x.append(0)
    x[i] = lst[i] - (i+1)

#print(x)
x.sort()
#print(x)

b = x[n//2]

#print(b)

sad = 0

#print(lst)

for i in range(n):
    sad += abs(lst[i]-b-i-1)

print(sad)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

input()
data = list(map(int, input().split()))

# Nを打ち消す
lis = [data[i-1]-i for i in range(1, len(data)+1)]

# ソートして中央値をとる
lis.sort()
med = lis[len(lis)//2]

# 各値から中央値を引く
reslis = [abs(i - med) for i in lis]

# 和を出す
print(sum(reslis))

Submission status: Accepted

Solution code:
def c_linear_approximation(N, A):
    import numpy
    B = numpy.array([a-k for k, a in enumerate(A)])
    b = int(numpy.median(B))
    ans = 0
    for b_k in B:
        ans += abs(b_k - b)
    return ans

N = int(input())
A = [int(i) for i in input().split()]
print(c_linear_approximation(N, A))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split(' ')))

p = sorted([v - (i + 1) for i, v in enumerate(A)])

if len(p) >= 3:
    res = min(sum(map(abs, [i - p[N//2] for i in p])), sum(map(abs, [i - p[N//2-1] for i in p])), sum(map(abs, [i - p[N//2+1] for i in p])))
elif len(p) >= 2:
    res = min(sum(map(abs, [i - p[0] for i in p])), sum(map(abs, [i - p[1] for i in p])))
else:
    res = 0
print(int(res))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
Ad = [A[i]-(i+1) for i in range(N)]
Ad.sort()
l = len(Ad)
if l % 2 == 1:
    b = Ad[l//2]
    ans = sum(map(lambda x:abs(x-b), Ad))
else:
    b1, b2 = Ad[l//2], Ad[l//2-1]
    ans = min(sum(map(lambda x:abs(x-b1), Ad)), sum(map(lambda x:abs(x-b2), Ad)))
print(ans)

Submission status: Accepted

Solution code:
# C - Linear Approximation
# https://beta.atcoder.jp/contests/abc102/tasks/arc100_a

# C_Linear_Approximation.py

N = int(input())
a = list(map(int, input().strip().split(" ")))

for i in range(N):
    a[i] = a[i] - (i+1)

a.sort()
if N % 2 != 0:
    mid = (N-1)//2
else:
    mid = N // 2 
b = a[mid]

sadness_left = b * mid - sum(a[:mid])
sadness = sum(a) - b * N + sadness_left * 2

print(sadness)

# 中央値を取るのがみそ

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

for i in range(N):
    A[i] -= i + 1

A = sorted(A)
b = A[N//2]
sad = 0
for i in A:
    sad += abs(i - b)

print(sad)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

b = []

for i in range(n):
  b.append(a[i]-(i+1))

# print(b)
b.sort()
# print(b)

min_b=b[n//2]
# print(min_b)

ans = 0
for i in range(n):
  ans+=abs(a[i]-(min_b+(i+1)))
  # print(ans)
print(ans)

Submission status: Accepted

Solution code:
# C - Linear Approximation
# https://beta.atcoder.jp/contests/abc102/tasks/arc100_a

# C_Linear_Approximation.py

# 7
# 1 1 1 1 2 3 4
#import sys

N = int(input())
a = list(map(int, input().strip().split(" ")))

for i in range(N):
    a[i] = a[i] - (i+1)

a.sort()
if N % 2 != 0:
    mid = (N-1)//2
else:
    mid = N // 2 -1
b = a[mid]

sadness_left = b * mid - sum(a[:mid])
sadness = sum(a) - b * N + sadness_left * 2

print(sadness)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
for j in range(n):
    a[j] = a[j] - (j + 1)
a.sort()
if n % 2 == 0:
    print(sum(a[int(n / 2):]) - sum(a[:int(n / 2)]))
else:
    print(sum(a[int((n + 1) / 2):]) - sum(a[:int((n - 1) / 2)]))