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: Time Limit Exceeded

Solution code:
# encoding:utf-8

def main():
	n = int(input())
	nums_raw = list(map(int, input().split()))
	nums = [nums_raw[i] - i for i in range(n)]
	nums.sort()
	ans = search(nums)
	#print(ans)
	print(sum([abs(nums_raw[i] - (ans + i)) for i in range(n)]))

def search(nums):
	u_nums = list(set(nums))
	left = 0
	right = len(u_nums) - 1

	tmp = 10 ** 10
	while True:
		if calc(nums, u_nums, left) >= calc(nums, u_nums, right):
			new = int((left + right)/2)
			left = new
		else:
			new = int((left + right)/2)
			right = new
		if new == tmp:
			l = []
			l.append(u_nums[new])
			if new + 1 <= len(u_nums) - 1:
				l.append(u_nums[-1])
			if new - 1 >= 0:
				l.append(u_nums[0])

			ans = 10 ** 10
			for i in range(min(l), max(l) + 1):
				#print(i, calc_2(nums, i))
				if calc_2(nums, i) <= ans:
					ans = calc_2(nums, i)
					tmp = i
			#print(ans)
			return tmp
		else:
			tmp = new

def calc(nums, u_nums, i):
	return sum([abs(x - u_nums[i]) for x in nums])

def calc_2(nums, i):
	return sum([abs(x - i) for x in nums])

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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

Ans = 0
pans = 0
low,high = -(10**5),10**9
for i in range(300):
    anslow,anshigh = 0,0
    for i in range(N):
        anslow += abs(A[i]-(i+low))
        anshigh += abs(A[i]-(i+high))
    if anshigh > anslow:
        high=(high+low)//2
    else:
        low=(high+low)//2
    Ans = min(anshigh,anslow)

print(Ans)

Submission status: Time Limit Exceeded

Solution code:
inf = float("inf")

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

bmin = inf
bmax = -inf

for b in range(0, N):
    bmin = min(bmin, A[b] - b)
    bmax = max(bmax, A[b] - b)

bb = inf
for d in range(bmin, bmax + 1):
    df = 0
    for b in range(0, N):
        df = df + abs(A[b] - (d + b))
    bb = min(bb, df)

print(bb)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N= input()
    li = map(int, raw_input().split())
    li = [i - li[i] for i in range(len(li))]
    unique = list(set(li))
    # print(list)
    # mini = min(li)
    # maxi = max(li)
    # print(mini)
    # print(maxi)
    beforesumm = float('inf')
    for b in unique:
        blist = [abs(-b+li[i]) for i in range(len(li))]
        # print(blist)
        summ = sum(blist)
        # print(summ)
        if beforesumm >= summ:
            beforesumm = summ
    print(int(beforesumm))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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
sumdata1 = 0
sumdatax = 0
#for i in data:
 #   sumdata += abs(i - key)
  #  sumdata1 += abs(i - key1)
   # sumdatax += abs(i - ave)
cnt = 0
sumdataa = 0
key = data[0] - 1
for i in data:
    if key != i:
        key = i
        for j in data:
            sumdataa += abs(j - key)
        #print(sumdataa)
        if cnt == 0:
            minsum = sumdataa
        if sumdataa < minsum:
            minsum = sumdataa
    cnt += 1
    sumdataa = 0

#print(sumdatax)
#print(data)
#print(min([sumdata, sumdata1]))
print(minsum)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
from pprint import pprint as pp
import itertools as it
from functools import lru_cache

YN = {True: 'Yes', False: 'No'}
ri = lambda: int(input())
ria = lambda: list(map(int, input().split()))
rian = lambda n: [ria() for _ in range(n)]
rs = lambda: input()
rsa = lambda: input().split()
rsn = lambda n: [rs() for _ in range(n)]

N = ri()
A = ria()

ret = None
ary = [a-i-1 for i,a in enumerate(A)]

ret = sum(abs(a) for a in ary)
for d in range(min(ary),max(ary)+1):
  x = sum(abs(a-i-1-d) for i,a in enumerate(A))
  ret = min(ret,x)
print(ret)

Submission status: Time Limit Exceeded

Solution code:
import sys
def calc(A,b):
    dif = 0
    for i,j in enumerate(A):
        dif+=abs(j-(b+i+1))
    return dif

N = int(input())
A = [int(i) for i in input().split()]
dif = calc(A,0)
if dif > calc(A,1):
    d = 1
    b = 1
    while(True):
        if calc(A,b) > calc(A,b+d):
            dif = calc(A,b+d)
            b+=d
        else:
            break
elif dif > calc(A,-1):
    d = -1
    b = -1
    while(True):
        if calc(A,b) > calc(A,b+d):
            dif = calc(A,b+d)
            b+=d
        else:
            break
ans = dif
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N= input()
    list = map(int, raw_input().split())
    list = [i - list[i] for i in range(len(list))]
    # print(list)
    mini = min(list)
    maxi = max(list)
    # print(mini)
    # print(maxi)
    beforesumm = float('inf')
    for b in list:
        blist = [abs(-b+list[i]) for i in range(len(list))]
        # print(blist)
        summ = sum(blist)
        # print(summ)
        if beforesumm >= summ:
            beforesumm = summ
    print(int(beforesumm))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

average = sum(a) // n

#print(average)

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

result = sadness(a, average)

temp = average
for i in range(1, n):
  temp_result = sadness(a, average + i)
  if result < temp_result:
    break
  else:
     temp = average + i
     result = temp_result

for i in range(1, n):
  temp_result = sadness(a, average - i)
  if result < temp_result:
    break
  else:
     temp = average - i
     result = temp_result

print(result)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int ,input().split()))
s = sum(a)
mean = s / N
cnt = 10**14
for j in range(s//N-10000,s//N+10000):
    tmp = 0
    for i in range(N):
        tmp += abs(a[i]-i-j-1)
    cnt = min(tmp,cnt)
print(cnt)

Submission status: Time Limit Exceeded

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


def solve(xs):
    ys = [x - i for i, x in enumerate(xs, start=1)]

    def f(z):
        return sum(abs(y - z) for y in ys)
    k = min(ys, key=f)
    return f(k)


def main():
    _ = int(input())
    xs = [int(x) for x in input().split()]
    print(solve(xs))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def f(A, b):
    return sum(abs(a - (b + i + 1)) for i, a in enumerate(A))
N = int(input())
A = [int(x) for x in input().split()]
left, right = -10**9, 10**9
while left + 2 < right:
    diff = (right - left) // 3
    m1 = left + diff
    m2 = m1 + diff
    if f(A, m1) > f(A, m2):
        left = m1
    else:
        right = m2
print(min(f(A, i) for i in range(left, right + 1)))

Submission status: Time Limit Exceeded

Solution code:
N = input()
A = map(int, raw_input().split())
l = -2*10**9
r = 2*10**9

def f(t):
  s = 0
  i = 1
  for a in A:
    s += abs(a-t-i)
    i += 1
  return s

while l<r-2:
  m1 = (l*2+r)/3
  m2 = (l+r*2)/3
  s1 = f(m1)
  s2 = f(m2)
  if s1<s2:
    r = m2
  else:
    l = m1

ans = 10**20
for i in range(-5,5):
  ans = min(ans, f(l+i))
print ans

Submission status: Time Limit Exceeded

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

def eva(b):
    r = 0
    for i in range(n):
        r += abs(a[i]-b-i)
    return r

ans = 10**9*n
lo = -10**9
hi = 10**9
while hi-lo > 1:
    mid = (hi+lo)//2
    y = eva(mid)
    z = eva(mid+1)
    ans = min(ans, y, z)
    if y > z:
        lo = mid
    else:
        hi = mid
ans = min(ans, eva(hi), eva(lo))
print(ans)

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

Submission status: Accepted

Solution code:
import statistics

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

value = 0

for _ in range(n):    
    x[_] -= (_ + 1)

x.sort()

for _ in x:
    value += abs(_ - x[n // 2])

print(value)

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 len(B)%2:
    ans = 0
    for i in range(n):
        ans += abs(B[i]-B[len(B)//2])
else:
    ans = float("inf")
    tmp = 0
    for i in range(n):
        tmp += abs(B[i]-B[len(B)//2-1])
    ans = min(ans, tmp)
    tmp = 0
    for i in range(n):
        tmp += abs(B[i]-B[len(B)//2])
    ans = min(ans, tmp)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = input_int()
    A = input_int_list()
    for i in range(n):
        A[i] = A[i] - (i + 1)

    A.sort()

    if n % 2 == 0:
        mid = (A[(n - 1) // 2] + A[((n - 1) // 2) + 1]) // 2
    else:
        mid = A[(n - 1) // 2]

    tmp0 = 0
    tmp1 = 0

    for a in A:
        tmp0 += abs(a - mid)
        tmp1 += abs(a - mid - 1)

    print(min(tmp0, tmp1))

    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

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

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

A.sort()
b = A[(N - int(N % 2 == 0)) // 2]

res = 0
for a in A:
    res += abs(a - b)

print(res)

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()
b = A[n//2]

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[32]:


import numpy as np


# In[22]:


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


# In[41]:


a = np.array(A)
b = a - np.arange(1,N+1)
c = np.median(b)
d = abs(b-c).sum()
print(int(d))


# In[ ]:

Submission status: Accepted

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

import numpy as np
a = np.array(a)
x = np.median(a)
r = 0
for i in range(n):
    r += abs(a[i]-x)
print(int(r))

Submission status: Accepted

Solution code:
# coding: utf-8
n = int(input())
A = list(map(int,input().split()))
L=[]
for i in range(n):
    L.append(A[i]-(i+1))
L.sort()
#print(L)
if n==1:
    b1=L[0]
    b2=L[0]
elif n==2:
    b1=L[0]
    b2=L[1]
else:
    b1=L[n//2]
    b2=L[n//2-1]
ans=0
cnt1=0
cnt2=0
for i in range(n):
    cnt1+=abs(L[i]-b1)
    cnt2+=abs(L[i]-b2)
print(min(cnt1,cnt2))

Submission status: Accepted

Solution code:
import math

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

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

A.sort()

if N % 2 == 0:
    b = (A[N//2-1] + A[N//2]) / 2
    bfl = math.floor(b)
    bce = math.ceil(b)
    ansfl = 0
    ansce = 0

    for i in range(N):
        ansfl += abs(A[i] - bfl)
        ansce += abs(A[i] - bce)

    ans = min(ansfl, ansce)

else:
    ans = 0
    b = A[N//2]

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

print(ans)

Submission status: Accepted

Solution code:
import statistics
import math

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

A_list_min = 10**9+1
A_list_sum = 0
for i in range(N):
    A_list[i] = A_list[i] - (i+1)

A_medi = int(statistics.median(A_list))
ans = 0
for i in range(N):
    ans += abs(A_list[i] - A_medi)
print(ans)

Submission status: Accepted

Solution code:
import math

def main():
    N = int(input())
    A = list(map(int, input().split()))
    for i in range(N):
        A[i] -= (i+1)
    
    A.sort()
    if N%2 == 0:
        b = (A[N//2] + A[N//2 - 1])/2
        bfl = math.floor(b)
        bce = math.ceil(b)
        ansfl = 0; ansce = 0
        for i in range(N):
            ansfl += abs(A[i] - bfl)
            ansce += abs(A[i] - bce)
        ans = min(ansfl, ansce)
    else:
        ans = 0
        b = A[N//2]
        for i in range(N):
            ans += abs(A[i] - b)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from statistics import median_high
n=int(input())
a=list(map(int,input().split()))
b=[]
for i in range(n):
    b.append(a[i]-i-1)
b.sort()
d=median_high(b)
ans=0
for i in range(n):
    ans+=abs(b[i]-d)
print(ans)

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))

######################################################

N,A=ilint()
A=[A[i]-(i+1) for i in range(N)]
A.sort()
k=A[N//2]
ans=0
for a in A:
    ans+=abs(a-k)
print(ans)

Submission status: Accepted

Solution code:
import statistics
import math

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

for i in range(n):
    A[i] = A[i]-i-1
A.sort()
m = statistics.median(A)

f = math.floor(m)
c = math.ceil(m)
sum_f = 0
sum_c = 0

for i in range(n):
    sum_f += abs(A[i]-f)
    sum_c += abs(A[i]-c)
    
print(min(sum_f, sum_c))

Submission status: Accepted

Solution code:
from collections import defaultdict
d = defaultdict(int)
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
  a[i]-=i+1
  d[a[i]]+=1
ans=0
b = min(a)
for i in a:
  ans+=i-b
a = sorted(set(a))
c = 0
i = 0
while i<len(a)-1:
  c+=d[a[i]]
  if c-(n-c)>0:
    print(ans)
    exit()
  ans+=(c-(n-c))*(a[i+1]-a[i])
  i+=1
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
*A,=map(int,input().split())
B=[A[i]-(i+1) for i in range(N)]
B.sort()
b=B[N//2]
print(sum(abs(bb-b)for bb in B))

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()
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]))

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
A = np.array(list(map(int,input().split())))
A -= np.arange(1,N+1)
print(sum(abs(A-int(np.median(A)))))

Submission status: Accepted

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

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

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:
import numpy as np
n = int(input())
a = np.fromstring(input(), dtype=np.int64, sep=' ')
for i in range(n):
    a[i] = a[i] - i - 1
x = int(np.median(a))
r = 0
for i in range(n):
    r += abs(a[i]-x)
print(r)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(j)-int(i)-1 for i, j in enumerate(input().split())]
a.sort()
num = n/2
if num.is_integer():
    num = num-1
val = a[int(num)]
ans = sum([abs(i-val) for i in a])
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7


def run():
    N, *A = map(int, read().split())
    B = [a-k for k, a in enumerate(A, 1)]
    B.sort()
    Bsum = []
    v = 0
    for b in B:
        v += b
        Bsum.append(v)

    min_val = INF
    for k in range(N):
        c = B[k]
        #print(c)
        score = 0
        score -= Bsum[k]
        score += Bsum[-1] - Bsum[k]
        score += -N * c + 2 * c * (k+1)
        #print(score)
        min_val = min(min_val, score)

    print(min_val)


if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
for i in range(N):
  A[i] -= i
A.sort()

n = (N-1) // 2
q = A[n]
ans = 0
for i in range(N):
  ans += abs(A[i]-q)
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    n, *a = map(int, read().split())

    a2 = list([ea - i - 1 for i, ea in enumerate(a)])
    a2.sort()
    n2 = n // 2
    r1 = sum([abs(ea2 - a2[n2]) for ea2 in a2])
    r2 = sum([abs(ea2 - a2[n2-1]) for ea2 in a2])
    print(min(r1, r2))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import statistics

def main():
    N = int(input())
    A = list(map(int, input().split()))
    for i in range(N):
        A[i] -= i + 1
    B = statistics.median_low(A)
    ans = 0
    for a in A:
        ans += abs(a - B)

    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


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

x = (A[N//2]+A[(N-1)//2])//2
print(sum(abs(A[i]-x) for i in range(N)))

Submission status: Accepted

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

memo = []

for key,val in enumerate(A):
    memo.append(val-key-1)
memo.sort()

ans = 0
for key,val in enumerate(A):
    ans += abs(val-key-1-memo[N//2])
print(ans)

Submission status: Accepted

Solution code:
def LI():
    return list(map(int, input().split()))


N = int(input())
A = LI()
x = []
for i in range(N):
    x.append(A[i]-(i+1))

x.sort()
B = x[N//2]

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

Submission status: Accepted

Solution code:
from numpy import*
n=int(input())
a=array(list(map(int,input().split())))
b=a-arange(1,n+1)
c=median(b)
d=abs(b-c).sum()
print(int(d))

Submission status: Accepted

Solution code:
import statistics
n,*a=map(int,open(0).read().split())
b=[q-i for i,q in enumerate(a,1)]
c=statistics.median(b)
ans=sum(map(abs,[p-c for p in b]))
print(int(ans))

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=sorted(b)
if n%2==1:
    ave = b[(n-1)//2]
else:
    ave = (b[n//2] + b[(n//2)-1])//2


ans = 0
for j in range(n):
    ans += abs(b[j]-ave)

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち

import numpy as np
from functools import partial
array = partial(np.array, dtype=np.int64)
zeros = partial(np.zeros, dtype=np.int64)
full = partial(np.full, dtype=np.int64)

ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return np.fromstring(readline(), sep=' ', dtype=np.int64)


def read_matrix(H, W):
    '''return np.ndarray shape=(H,W) matrix'''
    lines = []
    for _ in range(H):
        lines.append(read())
    lines = ' '.join(lines)  # byte同士の結合ができないのでreadlineでなくreadで
    return np.fromstring(lines, sep=' ', dtype=np.int64).reshape(H, W)


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, readline().split())))
    return ret


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import

from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b


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

Submission status: Accepted

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

Submission status: Accepted

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 = diff - np.median(diff)

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

Submission status: Accepted

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 == 1:
    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 - 1]
    for i in range(N):
        tmp1 += abs(A_dash[i] - b)
    
    tmp2 = 0
    b = A_dash[N // 2]
    for i in range(N):
        tmp2 += abs(A_dash[i] - b)
    print(min(tmp1, tmp2))

Submission status: Accepted

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 = (x+y)//2

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
ins = lambda: input().rstrip()
ini = lambda: int(input().rstrip())
inm = lambda: map(int, input().rstrip().split())
inl = lambda: list(map(int, input().split()))
out = lambda x, s='\n': print(s.join(map(str, x)))

n = ini()
a = inl()
j = 1
for i in range(n):
    a[i] -= j
    j += 1
a = sorted(a)
x = a[n//2]
ans = 0
for i in range(n):
    ans += abs(a[i] - x)
print(ans)

Submission status: Accepted

Solution code:

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

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

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

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

print(total)

Submission status: Accepted

Solution code:
N = int(input())

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

memo = []

for key,val in enumerate(A):
    memo.append(val-key-1)

memo.sort()

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

ans  = 0
for key,val in enumerate(A):
    ans += abs(val-(b+key+1))

print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
As = list(mapint())

As = [a-i for i, a in enumerate(As, 1)]
As.sort()
middle = As[N//2]
print(sum([abs(a-middle) for a in As]))

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


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


def f(x):
    return sum(abs(A[i]-x) for i in range(N))


print(f((A[(N-1)//2]+A[N//2])//2))
# 中間値

Submission status: Accepted

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 == 1:
    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 - 1]
    for i in range(N):
        tmp1 += abs(A_dash[i] - b)
    
    tmp2 = 0
    b = A_dash[N // 2]
    for i in range(N):
        tmp2 += abs(A_dash[i] - b)
    print(min(tmp1, tmp2))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
for i in range(N):
  A[i] -= i+1
#print(A)
A.sort()
dic = {}
for x in A:
  if x not in dic:
    dic[x] = 1
  else:
    dic[x] += 1
S = list(dic.keys())
now = 0
for x in A:
  now += abs(A[0]-x)
#print(now)
prev = A[0]
left = dic[S[0]]; right = N- left
for i in range(1,len(S)):
  dif = (left-right)*(S[i]-S[i-1])
  if dif < 0:
    now += dif
  left += dic[S[i]]
  right -= dic[S[i]]
print(now)

Submission status: Accepted

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


def f(x):
    return sum(abs(A[i]-x) for i in range(N))


print(f((A[(N-1)//2]+A[N//2])//2))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = [a-i-1 for i, a in enumerate(A)]
A.sort()
if N%2:
  med = A[(N-1)//2]
  A = [abs(a-med) for a in A]
  print(sum(A))
  exit()
else:
  med1 = (A[N//2-1]+A[N//2])//2
  med2 = med1 + 1
  A1 = [abs(a-med1) for a in A]
  A2 = [abs(a-med2) for a in A]
  print(min(sum(A1), sum(A2)))
  exit()

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = list(map(int,input().split()))
B = [0]*N
ans =0 
for i,j in enumerate(A):
    B[i] = j-(i+1)
B=sorted(B)
b=np.median(np.array(B))
for i,j in enumerate(A):
    ans+= abs(j-(int(b)+i+1))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
A=[int(i) for i in input().split()]
A=[A[i]-i for i in range(n)]
A.sort()
if n%2==0:
    mid2=A[n//2]+A[n//2-1]
else:
    mid2=A[n//2]*2

B=[i*2 for i in A]
ans=0
for i in range(n):
    ans+=abs(B[i]-mid2)
print(ans//2)

Submission status: Accepted

Solution code:
from statistics import median_low

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

a = [ai - i for i, ai in enumerate(a)]
med = median_low(a)
print(sum(abs(ai - med) for ai in a))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
inf = 10**16

def func(b):
    return sum([abs(a[i]-(b+i+1)) for i in range(n)])

# 3分探索を行う
low = -inf
high = inf

while abs(high-low) > 0.01:
    c1 = (low*2 + high)/3
    c2 = (low + high*2)/3

    if func(c1) > func(c2):
        low = c1
    else:
        high = c2
mid = (high+low)/2
ans = min(func(int(mid)), func(int(mid+1)), func(int(mid-1)))
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
a = [(item-i-1) for i,item in enumerate(a)]
a.sort()
m = a[(n-1)//2]
ans = sum(abs(item-m) for item in a)
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
a.sort()
if n%2==0: p=(a[n//2]+a[n//2-1])//2
else: p=a[n//2]
ans=0
for i in a: ans+=abs(i-p)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[int(x) for x in input().split()]

a_i=[]
pl=0
mi=0
mi_cnt=0
pl_cnt=0
for i in range(n):
  a_i.append((a[i]-(i+1)))
  if a[i]-(i+1)<0:
    mi+=a[i]-(i+1)
    mi_cnt+=1
  else:
    pl+=a[i]-(i+1)
    pl_cnt+=1

a_i.sort()
if n%2==0:
  k=a_i[n//2-1]
  k1=a_i[n//2]
  k=(k+k1)//2
else:
  k=a_i[n//2]

ans=0
for i in a_i:
  ans+=abs(i-k)
print(ans)