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:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def main():
    n = I()
    a = LI()
    t = sorted([a[i]-i-1 for i in range(n)])
    b = t[n//2]
    r = 0
    for i in range(n):
        r += abs(a[i]-(b+i+1))

    return r



print(main())

Submission status: Accepted

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

A = [A[i] - (i + 1) for i in range(len(A))]
A = sorted(A)
b = A[N // 2]
ans = [abs(a - b) for a in A]
print(sum(ans))

Submission status: Accepted

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

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()
if N % 2 == 1:
	b = A[(N//2)]
	ans = list(map(lambda x:abs(x-b),A))
	print(sum(ans))
else:
	b1 = (A[N//2-1] + A[(N//2)])//2
	ans1 = list(map(lambda x:abs(x-b1),A))
	b2 = b1 + 1
	ans2 = list(map(lambda x:abs(x-b2),A))
	print(min(sum(ans1),sum(ans2)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
 
for i in range(N):
    A[i] -= i
 
A.sort()
 
Ans = 0
mi = len(A)//2 # 中央値のindex
for i in range(N):
    Ans += abs(A[i]-A[mi])
 
print(Ans)

Submission status: Accepted

Solution code:
import statistics

def f(a, n):
    a2 = [ai - (i+1) for (i,ai) in enumerate(a)]
    b = int(statistics.median(a2))
    
    sadness = sum(abs(ai - b) for ai in a2)
    
    b += 1
    sadness2 = sum(abs(ai - b) for ai in a2)

    
    return min(sadness, sadness2)
    
n = int(input())
a = [int(i) for i in input().split()]
print(f(a, n))

Submission status: Accepted

Solution code:
import numpy as np

N=int(input())
A=input().split(" ")
for i in range(N):
	A[i]=int(A[i])

A=np.array(A)
B=A-np.arange(1,N+1)
print(int(np.sum(np.abs(B-np.median(B)))))

Submission status: Accepted

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

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

A.sort()

Ans = 0
mi = len(A)//2 # 中央値のindex
for i in range(N):
    Ans += abs(A[i]-A[mi])

print(Ans)

Submission status: Accepted

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

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

sortA = sorted(A)

if(N>1):
    b1 = sortA[(N-1)//2]
    b2 = sortA[(N-1)//2+1]

    ans1 = 0
    ans2 = 0
    for i in range(N):
        ans1 += abs(b1-A[i])
        ans2 += abs(b2-A[i])

    print(min(ans1, ans2))
else:
    print(0)

Submission status: Accepted

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

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

a.sort()
b = [0]
for i in a:
    b.append(b[-1] + i)
hi = len(a)
lo = 0


def score(index):
    return abs(abs((index + 1) * a[index] - b[index+1]) + abs(b[-1] - b[index+1] - (len(a) - index - 1) * a[index]))


for i in range(10000):
    lft = (hi + 2 * lo) // 3
    rgt = (2 * hi + lo) // 3
    ltmp = score(lft)
    rtmp = score(rgt)
    if ltmp <= rtmp:
        lo = lft
    else:
        hi = rgt

print(min([score(i) for i in range(len(a))]))

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())

B = np.array([0]*N)

l = input().split()

for i in range(N):
    B[i] = int(l[i]) - (i+1)
    
B = np.sort(B)

if N % 2 == 1:
    b_mid = B[int(N/2)]
else:
    mid = int(N/2) - 1
    b_mid = int( (B[mid] + B[mid+1])/2 )

dif = B - b_mid

print(np.sum(abs(dif)))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a = sorted([a[i] - (i + 1) for i in range(n)])

def sadness(index):
	return sum([abs(a[i] - a[index]) for i in range(n)])

if n % 2 == 1:
	print(sadness((n - 1) // 2))

else:
	print(min(sadness(n // 2), sadness(n // 2 - 1)))

Submission status: Accepted

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

mem = [a-i-1 for i,a in enumerate(src)]
center = sorted(mem)[N//2]

ans = 0
for a in mem:
    ans += abs(a - center)
print(ans)

Submission status: Accepted

Solution code:
#coding:utf-8
n = int(input())
nums = sorted([num - i for i, num in enumerate(list(map(int,input().split())), 1)])


sums = [None for i in range(n)]
sums[0] = nums[0]
allv = sum(nums)

minv = nums[0] * (2 - n) - 2 * sums[0] + allv
for i in range(n-1):
    sums[i+1] = sums[i] + nums[i+1]
    p = nums[i] * (2*(i+1) - n) -2 * sums[i] + allv
    minv = min(minv,p)

print(minv)

Submission status: Accepted

Solution code:
def calc(b,A,N):
    sadness = 0
    for i in range(N):
        sadness += abs(A[i] - (b + i))
    return sadness

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

k = []
for i in range(N):
    k.append(A[i] - i)

k = sorted(k)

sadness = 0
if N % 2 == 1:
    sadness = calc(k[N//2],A,N)
else:
    sadness = min(calc(k[N//2],A,N),calc(k[(N//2)+1],A,N))

print(sadness)

Submission status: Accepted

Solution code:
n = int(input())
aaa = list(map(int, input().split()))
aam = [a - i - 1 for i, a in enumerate(aaa)]
aam.sort()
b = aam[n // 2]
print(sum(abs(am - b) for am in aam))

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()
m1 = a[n//2]
m2 = a[n//2-1]
ans1 = sum([abs(ele-m1) for ele in a])
ans2 = sum([abs(ele-m2) for ele in a])
print(min(ans1, ans2))

Submission status: Accepted

Solution code:
from statistics import median

N = int(input())
A = list(map(int, input().split()))
for i in range(N):
    A[i] -= i+1
 
A.sort()
b = median(A)
sad = 0
for i in range(N):
    sad += abs(A[i]-b)
print(int(sad))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A_dash = []
for i, A_i in enumerate(A):
    A_dash.append(A_i-(i+1))
A_dash.sort()

med = A_dash[N//2]

ans = 0
for i, A_i in enumerate(A_dash):
    ans += abs(A_i - (med))

print(ans)

Submission status: Accepted

Solution code:
import functools
N = int(input())
A = [int(x) for x in input().split()]
Ai = sorted([A[i] - i - 1 for i in range(N)])
if N % 2:
  med = N // 2
  ans = functools.reduce(lambda x, y: x + y, [abs(a - Ai[med]) for a in Ai])
else:
  med = N // 2
  ans1 = functools.reduce(lambda x, y: x + y, [abs(a - Ai[med]) for a in Ai])
  ans2 = functools.reduce(lambda x, y: x + y, [abs(a - Ai[med - 1]) for a in Ai])
  ans = min(ans1, ans2)
print(ans)

Submission status: Accepted

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

for i in range(a):
	su += abs(b[i] - c)

print(su)

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 - 1) // 2]
ans = 0
for i in range(n): ans += abs(a[i] - b)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
if n == 1:
    a = input()
    print(0)
else:
    a = np.array(list(map(int, input().split())))
    check = np.arange(1, n+1)
    c = sorted(list(a - check))
    b1 = c[int(n/2)]
    b2 = c[int(n/2)+1]
    count1 = 0
    count2 = 0
    for i in range(1, n+1):
        count1 += abs(a[i-1] - i - b1)
        count2 += abs(a[i-1] - i - b2)
    print(min(count1, count2))

Submission status: Accepted

Solution code:
def bisect(l, r):
    while l < r:
        m = (l + r) // 2
        s1 = sum(abs(am - m) for am in aam)
        s2 = sum(abs(am - m - 1) for am in aam)
        if s1 < s2:
            r = m
        else:
            l = m + 1
    return l


n = int(input())
aaa = list(map(int, input().split()))
aam = [a - i - 1 for i, a in enumerate(aaa)]
aas = sum(aam)
b = bisect(int(-1e9), int(1e9))
print(sum(abs(am - b) for am in aam))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    p, z, m = [], 0, []
    for i in range(n):
        t = a[i] - (i + 1)
        if t > 0:
            p.append(t)
        elif t == 0:
            z += 1
        else:
            m.append(-t)
    if sum(m) > sum(p):
        p, m = m[:], p[:]

    p.sort()
    ps, ms = sum(p), sum(m)
    pl, ml = len(p), len(m)
    x = 0
    ans = ms + ps
    for t in p:
        t, x = t - x, t
        ps -= pl * t
        pl -= 1
        if t > 0:
            ml += z
            ms += ml * t
            z = 1
            a = ms + ps
            if a < ans:
                ans = a
        else:
            z += 1
    print(ans)


main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
AA = sorted([ a - i - 1 for i,a in enumerate(A) ])
C = []
for i,a in enumerate(AA):
    if i == 0:
        C.append(a)
    else:
        C.append(C[-1] + a)
ans = ""
#print(C)
for i,b in enumerate(AA):
    sample = 0
    num = i-1
    if num == -1:
        sample = C[-1]  - b * (N - 2 * (num + 1))
    else:
        sample = C[-1] - 2 * C[num] - b * (N - 2 * (num + 1))
    if ans == "":
        ans = sample
    if ans > sample:
        ans = sample
if ans == "":
    ans = 0
print(ans)

Submission status: Accepted

Solution code:
from math import ceil,floor
n=int(input())
if n==1:
  print(0)
  exit()
a=[int(i) for i in input().split()]
for i in range(n):
  a[i]-=(i+1)
a.sort()

b1=a[ceil(n/2)]
b2=a[floor(n/2)]

def c1(x):
    return abs(x-b1)
def c2(x):
    return abs(x-b2)
print(min(sum(list(map(c1,a))),sum(list(map(c2,a)))))

Submission status: Accepted

Solution code:
import numpy as np

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

list = []

for b in range(0, N):
    list.append(A[b] - b)

md = int(np.median(list))

bb = 0
for b in range(0, N):
    bb += abs(list[b] - md)

print(bb)

Submission status: Accepted

Solution code:
from statistics import median

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

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

ave = int(median(a))

sad = 0
for i in range(n):
  sad += abs(a[i] - ave)

print(sad)

Submission status: Accepted

Solution code:
import sys
N = int(sys.stdin.readline())
As = list(map(int, sys.stdin.readline().split()))
bs = []
for i, a in enumerate(As):
    bs.append(a-(i+1))
bs.sort()

cumsum = [0]
s = 0
for b in bs:
    s += b
    cumsum.append(s)

def func(j):
    b = -bs[j]

    s_l = cumsum[j+1] - cumsum[0] #seq[:j]
    s_r = cumsum[N] - cumsum[j+1] #seq[j:]

    res = abs(s_l+b*(j+1)) + abs(s_r+b*(N-(j+1)))
    return res

res = float('inf')
for j, b in enumerate(bs):
    res = min(res, func(j))
print(res)

Submission status: Accepted

Solution code:
import statistics
import math

n = int(input())
a = [int(i) - (index+1) for index, i in enumerate(input().split())]

abs_total = 0
for i in a:
  abs_total += abs(i)

median = statistics.median(a) 


if n % 2 == 0 and median.is_integer() is False:
  median_high = statistics.median_high(a)
  median_low = statistics.median_low(a)

  abs_high = 0
  abs_low = 0
  for i in a:
    abs_high += abs(i-median_high)
    abs_low += abs(i-median_low)

  if abs_high < abs_low:
    print(int(abs_high))
  else:
    print(int(abs_low))
else:
  abs_total = 0
  for i in a:
    abs_total += abs(i-median)
  print(int(abs_total))

Submission status: Accepted

Solution code:
a=int(input())
b=list(map(int, input().split()))
c=list(range(1,a+1))
b2=[b[i]-c[i] for i in range(a)]
#print(b2)
d=sorted(b2)
#print(d)
if a%2==1:
    b3=[abs(i-d[len(d)//2]) for i in b2]
else: 
    if d[len(d)//2]<0:
        if d[len(d)//2+1]<0:
            b3=[abs(i-d[len(d)//2+1]) for i in b2]
    else:
        b3=[abs(i-d[len(d)//2]) for i in b2]
#print(b3)
print(sum(b3))

Submission status: Accepted

Solution code:
N = int(input())
data = list(map(int, input().split()))
for i in range(N):
    data[i] -= (i + 1)
ave = sum(data) / N
if ave > 0:
    key = int(ave + 1)
    key1 = int(ave)
else:
    key = int(ave - 1)
    key1 = int(ave)
data.sort()
sumdata = 0
sumdata2 = 0
key = data[int(N / 2) - 1]
key2 = data[int(N / 2)]
for i in data:
    sumdata += abs(i - key)
    sumdata2 += abs(i - key2)

#print(sumdatax)
#print(data)
print(min([sumdata, sumdata2]))

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = np.array(list(map(int,input().split())))
n = np.array([i for i in range(A.size)][::-1])
A = A+n
ave = np.median(A)
round = lambda x:int(x*2+1)//2
ave = round(ave)
A = A-ave
A = np.abs(A)
print(A.sum())

Submission status: Accepted

Solution code:

def mi():
	return map(int, input().split())

n = list(mi())[0]
a = list(mi())
for i in range(len(a)):
	a[i]-=i+1
s = 0

import statistics
b = a.copy()
for i in range(n):
	b[i] = abs(a[i])

a1 = statistics.median(a)
a2 = statistics.median(b)

s = 0
s1 = 0
for i in range(n):
	s+=abs(a[i]-a1)
	s1+=abs(a[i]-a2)
s = min(s,s1)
print (int(s))

Submission status: Accepted

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

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

a.sort()

d1 = a[len(a) // 2]
print(sum([abs(i - d1) for i in a]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):

    tmp = [a-(i+1) for i, a in enumerate(A)]

    
    def sk(b):
        s = 0
        for i, a in enumerate(A):
            s += abs(a-(b+i+1))
        return s

    # for i in range(-10, 10):
    #     print(i, sk(i))

    s = -int(1e+10)
    e = int(1e+10)
    ssk = sk(s)
    esk = sk(e)
    # print(s, ssk)
    # print(e, esk)
    while abs(s - e) > 1:
        m = (s+e)//2
        msk = sk(m)
        # print(m, msk)
        if ssk < esk:
            esk = msk
            e = m
        else:
            ssk = msk
            s = m
    
    return min(sk(s), sk(e))


def main():
    N = read_int()
    A = read_int_n() 
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math 
import sys
N=int(input())
A=[int(i) for i in input().split()]
for i in range(N):
    A[i]=A[i]-i-1
A.sort()
ans =0
a=A[N//2]
for i in range(N):
    ans+=abs(A[i]-a)
print(ans)

Submission status: Accepted

Solution code:
import math
import numpy as np

n = int(input())
a_list = list(map(int, input().split()))
a_list2 = sorted([a - (i + 1) for i, a in enumerate(a_list)])

s_cand = []
b_cand = [math.floor(sum(a_list2) / n), math.ceil(sum(a_list2) / n), int(np.median(a_list2))]

for b in b_cand:
    s = 0
    for a in a_list2:
        s += int(abs(a - b))
    s_cand.append(s)
    
print(min(s_cand))

Submission status: Accepted

Solution code:

import statistics
import math
n = int(input())
A = list(map(int, input().split()))

aa = []

for i in range(n):
    aa.append(A[i] - 1 - i)
# print(aa)
b = int(statistics.median(aa))

ans = 0

for a in aa:
    ans += abs(a-b)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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


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

np_A = np.array(A)
b = -np.median(np_A)

np_A += b.astype("i")
res = np.abs(np_A).sum()
print(res)

Submission status: Accepted

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

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

b = statistics.median(c)
ret0 = 0
ret1 = 0
ret2 = 0
for i in range(n):
    ret0 += abs(a[i] - b - i)
    ret1 += abs(a[i] - b - i - 1)
    ret2 += abs(a[i] - b - i - 2)

print(int(min(ret0, ret1,ret2)))

Submission status: Accepted

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


if N % 2 == 1:
    X = A[N // 2]
    ans = 0
    for a in A:
        ans += abs(a - X)
    print(ans)
else:
    X = (A[N // 2] + A[N // 2 -1]) / 2
    X1 = ceil(X)
    X2 = floor(X)
    ans1, ans2 = 0, 0
    for a in A:
        ans1 += abs(a - X1)
        ans2 += abs(a - X2)

    print(int(min(ans1, ans2)))

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.sort()

center = n // 2

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

print(ans)

Submission status: Accepted

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

aSum = [0] * (n + 1)
aSum[0] = a[0]
for i in range(1, n+1):
    aSum[i] = aSum[i - 1] + a[i]

minSad = float('inf')
for i in range(1, n + 1):
    b = a[i]
    tempL = b * i - (aSum[i] - aSum[0])
    tempR = (aSum[n] - aSum[i]) - b * (n - i) 
    minSad = min(minSad, tempL + tempR)

print(minSad)

Submission status: Accepted

Solution code:
n=int(input())
s=input().split()
l=[]
for i in s:
    l.append(int(i))
s=0
for i in range(n):
    l[i]-=i+1
l.sort()
b=l[n//2]
for i in range(n):
    l[i]-=b
    l[i]=abs(l[i])
print(sum(l))

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()
mean = A[N//2]
print(sum([abs(a - mean) for a in A]))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A2 = []
for i, a in enumerate(A):
    A2.append(a-i)
A2.sort()
m = A2[(N-1)//2]
ans = 0
for a in A2:
    ans += abs(m-a)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

def ii():
    return int(input())


def lii():
    return list(map(int, input().split(' ')))


def lvi(N):
    l = []
    for _ in range(N):
        l.append(ii())
    return l


def lv(N):
    l = []
    for _ in range(N):
        l.append(input())
    return l


def main():
    N = ii()
    A = lii()
    for i in range(N):
        A[i] -= (i + 1)

    A = np.array(sorted(A))
    offset = A[0]
    A = A - offset
    s1 = A.sum()
    mins = s1
    s2 = 0
    nowv = 0

    for i, v in enumerate(A):
        if nowv < v:
            s1 -= (v - nowv) * (N - i)
            s2 += (v - nowv) * i
            nowv = v
            if s1 + s2 < mins:
                mins = s1 + s2

    return mins

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import numpy as np
N = int(input())
A = list(map(int, input().split()))
A = sorted([a-(i+1) for i, a in enumerate(A)])
m = A[N//2]
ans = 0
for a in A:
    ans += abs(a-m)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    a[i] -= i
a.sort()
b = a[n // 2]
answer = 0
for a_i in a:
    answer += abs(a_i - b)
print(answer)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
try: from typing import Any, Union, List, Tuple, Dict
except ImportError: pass
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)


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

min_ = 10**20

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

B.sort()

Bplus = sum(B)
Bminus = 0
for n in range(N//2):
    sad = Bplus - Bminus
    sad += (2*n-N)*B[n]
    min_ = min(sad, min_)

    Bplus -= B[n]
    Bminus += B[n]

for n in range(N//2, N):
    sad = Bplus - Bminus
    sad += (2*n-N)*B[n-1]
    min_ = min(sad, min_)

    Bplus -= B[n]
    Bminus += B[n]

print(min_)

Submission status: Accepted

Solution code:
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]


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



def check(b):
    res = 0
    for i in range(N):
        res += abs(A[i] - (b+(i+1)))
    #print(b, res)
    return res

def ternarySearchInt(small, big):
    # 初期条件
    if small == big:
        return small
    elif big - small == 1:
        if check(small) <= check(big):
            return small
        else:
            return big

    def func(small, big):
        midl = (big + small) // 2
        midr = midl + 1
        if big - small == 2:  # 終了条件
            mid = midl
            if check(small) <= check(mid):
                if check(small) <= check(big):
                    return small
                else:
                    return big
            else:
                if check(mid) <= check(big):
                    return mid
                else:
                    return big
        else:
            if check(midl) >= check(midr):
                return func(midl, big)
            else:
                return func(small, midr)
    return func(small, big)

ans = ternarySearchInt(-int(1e9), int(1e9))
#print(check(0))
print(check(ans))

Submission status: Accepted

Solution code:

import statistics

N = int(input())
A_suc = [int(a) for a in input().split()]
B_suc = [i + 1 for i in range(len(A_suc))]
C_suc = [i - j for i, j in zip(A_suc, B_suc)]
median = int(statistics.median(C_suc))
D_suc = [abs(i - median) for i in C_suc]
print(sum(D_suc))

Submission status: Accepted

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

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

b = sorted(a)[int(n / 2)]
print(sum(map(lambda x: abs(x - b), a)))

Submission status: Accepted

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

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

b = sorted(B)[N // 2]

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

Submission status: Accepted

Solution code:
import math
N = int(input())
A = list(map(int,input().split()))
for i in range(N):
    A[i] = A[i]-i-1
A.sort()
f = math.floor(N/2)

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
A = sorted(a-i for i,a in enumerate(A))

a = (len(A)+1)//2-1
b = len(A)//2

print(sum(A[b:])-sum(A[:a+1]))

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[N//2]
ans=0
for i in range(N):
    ans+=abs(B[i]-b)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int,input().split()))
for i in range(len(a)):
  a[i] = a[i]-i-1
a = sorted(a)
import numpy as np
a = np.array(a)
b = np.median(a)
a = a-b
a = abs(a)
print(int(sum(a)))

Submission status: Accepted

Solution code:
n = int(input())
a = [int(x) - i - 1 for i, x in enumerate(input().split())]
a.sort()
m = a[(n - 1)//2]
s = 0
for x in a: s += abs(x - m)
print(s)

Submission status: Accepted

Solution code:
from statistics import median
def inpl(): return map(int, input().split())
N = int(input())
A = [j-i for i, j in enumerate(inpl(), start=1)]
m = median(A)
print(int(sum([abs(a-m) for a in A])))

Submission status: Accepted

Solution code:
n = int(input())
alst = list(map(int, input().split()))
for i in range(n):
  alst[i] -= (i + 1)
alst.sort()
c1 = alst[n // 2]
c2 = alst[n // 2 - 1]

ans = min(sum([abs(a - c1) for a in alst]), sum([abs(a - c2) for a in alst]))
print(ans)

Submission status: Accepted

Solution code:

import sys
#sys.stdin=open("data.txt")
input=sys.stdin.readline

n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    a[i]-=i
a.sort()

a.sort()
ans=0
median=a[n//2]
for i in range(n):
    ans+=abs(a[i]-median)
print(ans)

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N = read()
A = reads()

B = [A[i] - i for i in range(N)]
B.sort()

med = B[N//2]
ans = sum(abs(b - med) for b in B)

print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
for i in range(N):
  A[i]-= i+1
A.sort()
total = sum(A)
mean1 = total//N
mean2 = total//N + 1
med1 = A[N//2]
med2 = A[N//2+1]
ans1 = 0
ans2 = 0
ans3 = 0
ans4 = 0 
for a in A:
  ans1+=abs(a-mean1)
  ans2+=abs(a-mean2)
  ans3+=abs(a-med1)
  ans4+=abs(a-med2)
print(min([ans1,ans2,ans3,ans4]))

Submission status: Runtime Error

Solution code:
n,*a=map(int,open(0).read().split())
b=[q-i for i,q in enumerate(a,1)]
b.sort()

c=b[(n+1)//2]+b[::-1][(n+1)//2]
c//=2

ans=float("inf")
for i in range(-10+c,11+c):
  tmp=sum(map(abs,[q-i for q in b]))
  ans=min(ans,tmp)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

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

arr = np.arange(n) + 1
diff = a - arr

diff.sort()

diff -= np.median(diff)

print(int(np.abs(diff).sum()))

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N = I()
A = LI()
for i in range(N):
    A[i] -= i+1
A.sort()

x = A[N//2]
y = A[(N-1)//2]
z = (A[x]+A[y])//2

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

Submission status: Runtime Error

Solution code:
import sys

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

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

A_dash.sort()
ans = -float("inf")
if N % 2 == 0:
    tmp = 0
    b = A_dash[N // 2]
    for i in range(N):
        tmp += abs(A_dash[i] - b)
    print(tmp)
else:
    tmp1 = 0
    b = A_dash[N // 2]
    for i in range(N):
        tmp1 += abs(A_dash[i] - b)
    
    tmp2 = 0
    b = A_dash[N // 2 + 1]
    for i in range(N):
        tmp2 += abs(A_dash[i] - b)
    print(min(tmp1, tmp2))

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math
n = int(input())
#x, y = map(int,input().split())
A = list(map(int,input().split()))
ans = 0
B=  []
for i in range(n):
    B.append(A[i]-(i+1))
B.sort()
m = B[n//2]
m2=B[n//2+1]
tmp1=0
tmp2=0
#print(m,m2)
for i in range(n):
    tmp1 += abs(A[i]-(i+1)-m)
    tmp2 += abs(A[i]-(i+1)-m2)
print(min(tmp1, tmp2))

Submission status: Runtime Error

Solution code:
n,*a = map(int,open(0).read().split())
a = [a[i] -i -1 for i in range(n)]
a.sort()
if n % 2 == 0:
  b = a[n//2]
  c = b + 1
else:
  b = (a[n//2]+a[n//2+1])//2
  c = b + 2
ans = min([sum([abs(i - j) for i in a]) for j in range(b,c)])
print(ans)

Submission status: Runtime Error

Solution code:
n,*a = map(int,open(0).read().split())
a = [a[i] -i -1 for i in range(n)]
a.sort()
b = a[n//2]
if n % 2 == 0:
  c = b + 1
else:
  c = a[n//2+1]+1
ans = min([sum([abs(i - j) for i in a]) for j in range(b,c)])
print(ans)

Submission status: Runtime Error

Solution code:
n,*a = map(int,open(0).read().split())
a = [a[i] -i -1 for i in range(n)]
a.sort()
print(a)
b = a[n//2]
if n % 2 == 0:
  c = b + 1
else:
  c = a[n//2+1]+1
ans = min([sum([abs(i - j) for i in a]) for j in range(b,c)])
print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect
import numpy

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

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

def f(k):
    return sum(map(lambda x: abs(x-k), a))

c = numpy.median(a)
print(int(f(c)))

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
num = list(map(int,input().split()))
for i in range(1, N+1):
    num[i-1] -= i
numbers = np.array(num)
b = round(np.median(numbers))
numbers-= b
number = np.abs(numbers)
print(number.sum())

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
num = list(map(int,input().split()))
for i in range(1, N+1):
    num[i-1] -= i
numbers = np.array(num)
b = round(np.median(numbers))
numbers-= b
print(numbers.sum())

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys

def solve(N: int, A: "List[int]"):
    from scipy.optimize import dual_annealing
    A = [a-i for i, a in enumerate(A, 1)]
    def f(b):
        return sum(abs(a-b) for a in A)
    res = dual_annealing(f, [[min(A), max(A)]], maxiter=500)
    # print(res)
    b = res.x[0]
    return min(f(int(round(b))), f(int(round(b+1))))

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"    
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()