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 numpy as np
import math

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

base = np.arange(N, dtype=int) + 1
tmp = A - base
b = math.floor(np.median(tmp))
ans = np.abs(tmp - b).sum()
print(ans)

Submission status: Accepted

Solution code:
import sys
import statistics                                                                                                                       
readInt = lambda f=sys.stdin: [int(i) for i in f.readline().split()];
n = readInt()[0]
A = readInt()
C = [a - i for i, a in enumerate(A)]
b = int(statistics.median(C))
ans = sum([abs(c - b) for c in C])

print(ans)

Submission status: Accepted

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

print(s)

Submission status: Accepted

Solution code:
import math

N= int(input())
A = list(map(int, input().split()))
 
B=[0]*N
for i in range(N):
    B[i]=A[i]-(i+1)

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

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

print(s)

Submission status: Accepted

Solution code:
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    a = list(map(int, input().rstrip('\n').split()))
    for i in range(n):
        a[i] -= i + 1
    a.sort()
    t = a[n // 2]
    mt = 0
    for v in a:
        mt += abs(t - v)
    print(mt)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import numpy as np
import math

N = int(input())
A = np.array(list(map(int, input().split())))
base = np.arange(N, dtype=int) + 1

tmp = A - base
b = math.floor(np.median(tmp))
ans = tmp - b
print(np.abs(ans).sum())

Submission status: Accepted

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

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

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

print(sadness(sA[len(A)//2]))

Submission status: Accepted

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

ad = sorted([a[i] - i - 1 for i in range(n)])
b = ad[n // 2]

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

print(ans)

Submission status: Accepted

Solution code:
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = list(map(int, readline().split()))
    for i in range(n):
        a[i] -= i + 1
    a.sort()
    t1 = 0
    t2 = 0
    for i in range(n):
        t1 += abs(a[i] - a[n//2])
        t2 += abs(a[i] - a[n//2 - 1])
    print(min(t1, t2))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import numpy as np
N=int(input())
A=[int(i) for i in input().split()]
A=[A[i]-i for i in range(N)]
#print(A)
b=np.median(A)
K=[abs(A[i]-b) for i in range(N)]
print(int(sum(K)))

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+1)

B.sort()

b=[]
if N%2==1:
    b.append(B[(N+1)//2-1])
elif N%2==0:
    b.append(B[N//2-1])
    b.append(B[N//2])

ans=[]
for i in b:
    sum=0
    for j in range(N):
        sum+=abs(B[j]-i)
    ans.append(sum)

print(min(ans))

Submission status: Accepted

Solution code:
N = int(input())
if N == 1:
    print(0)
    exit()
A = [int(i) for i in input().split()]
A = [A[i] - i - 1 for i in range(N)]
A.sort()
if N == 2:
    print(abs(A[0] - A[1]))
    exit()

sum_A = [0, 0]
for i in range(N):
    sum_A[0] += abs(A[i] - A[N // 2])
sum_2 = 0
for i in range(N):
    sum_A[1] += abs(A[i] - A[N // 2 + 1])
print(min(sum_A))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
l = sorted([ A[i]-(i+1) for i in range(n) ])
c = 0
m = l[n//2]
for i in l:
  c += abs(i-m)
print(c)

Submission status: Accepted

Solution code:
n=int(input())
a1=list(map(int,input().split()))
a2=sorted([a1[i-1]-i for i in range(1,n+1)])
if len(a2)%2==0:
    m1=a2[len(a2)//2]
    m2=a2[len(a2)//2-1]
else:
    m1=a2[len(a2)//2]
    m2=m1
ans1,ans2=0,0
for i in a2:
    ans1+=abs(i-m1)
    ans2+=abs(i-m2)
print(min(ans1,ans2))

Submission status: Accepted

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


aaa=sorted(aa)
if len(aaa)%2==0:
    m1=aaa[len(aaa)//2]
    m2=aaa[len(aaa)//2-1]
else:
    m1=aaa[len(aaa)//2]
    m2=m1
ans1,ans2=0,0
for i in aa:
    ans1+=abs(i-m1)
    ans2+=abs(i-m2)
print(min(ans1,ans2))

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-1)//2]
else:
    b = a[n//2]

ans = 0
for i in a:
    ans += abs(i-b)
print(ans)

Submission status: Accepted

Solution code:
import math
import copy
import sys
import bisect
input = sys.stdin.readline

def main():
    n=int(input())
    a = list(map(int,input().split()))
    b=[0 for _ in range(n)]
    for i in range(n):
        b[i]=a[i]-i-1
    b.sort()
    if n%2==1:
        mid=b[(n-1)//2]
        ans=0
        for i in range(n):
            ans+=abs(b[i]-mid)
        print(ans)
    else:
        mid = (b[(n//2)-1]+b[(n//2)])//2
        ans=float('inf')
        for i in range(mid,mid+2):
            ans1=0
            for j in range(n):
                ans1+=abs(b[j]-i)
            ans=min(ans1,ans)
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
# coding: utf-8
# Your code here!
N=int(input())
A=list(map(int,input().split()))

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

A.sort()

temp1=A[N//2]
temp2=A[N//2-1]

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

ans2=0
for i in range(N):
    ans2+=abs((A[i])-temp2)
    
print(min(ans1,ans2))

Submission status: Accepted

Solution code:
def total(inlist,k):
    print(sum([ abs(i-k) for i in inlist ]))
    return
n = int(input())
a_list = [ int(v) for v in input().split() ]
a_list = [ v-i for i, v in enumerate(a_list,1) ]
a_list.sort()

total(a_list,a_list[n//2])

Submission status: Accepted

Solution code:
# from statistics import median

n = int(input())
a = map(int, input().split())
a = tuple(sorted(x - i for i, x in enumerate(a, 1)))

# b = median(a)
b = a[n // 2]  # 要素が偶数個のとき、中央値の計算に使用する2値のいずれでもよい

ans = sum(abs(x - b) for x in a)
print(ans)

Submission status: Accepted

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

def calc(A, b):
    c = 0
    for i, x in enumerate(A):
        c += abs(x - (b + (i+1)))
    return c

def solve(N, A):
    B = []
    for i, a in enumerate(A):
        B.append(a - (i+1))
    return calc(A, sorted(B)[N // 2])

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import copy
N=int(input())
lst=list(map(int,input().split()))
lst2=copy.copy(lst)
for i in range(1,N+1):
  lst2[i-1]-=i
lst2=sorted(lst2)
b=lst2[N//2]
ans=0
for i in range(N):
  ans+=abs(lst[i]-(b+i+1))
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))
sub = np.array(list(range(n)))
b = sorted(a - sub)[n // 2]
print(sum(abs(a - (b + sub))))

Submission status: Accepted

Solution code:
import sys
n = int(input())
a_ls = [int(i) for i in sys.stdin.readline().split()]
a_ls = [i - j - 1 for j, i in enumerate(a_ls)]
base = sorted(a_ls)[n // 2]
print(sum([abs(a - base) for a in a_ls]))

Submission status: Accepted

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

avg=[]
for i in range(len(A)):
    avg.append(A[i]-(i+1))
avg.sort()
b=avg[int(n/2)]

sum = 0
for j in range(len(A)):
    sum += abs(A[j]-(b+j+1))

print(sum)

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

Submission status: Accepted

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

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

A.sort()
if N%2==1:
  ma=A[N//2]
  print(sum([abs(i-ma) for i in A]))
else:
  ma=[A[N//2]-1,A[N//2]]
  a=[]
  for m in ma:
    a.append(sum([abs(i-m) for i in A]))
  print(min(a))

Submission status: Accepted

Solution code:
from statistics import median
N = int(input())
A = list(map(int, input().split()))
B = [a-i for i, a in enumerate(A)]
m = int(median(B))
print(sum(abs(b-m) for b in B))

Submission status: Accepted

Solution code:
n=int(input())
a=sorted([x-i for i,x in enumerate(list(map(int,input().split())))])
if n%2==1:
  print(sum([abs(x-a[n//2]) for x in a]))
else:
  print(min(sum([abs(x-a[n//2]) for x in a]),sum([abs(x-a[n//2+1]) for x in a])))

Submission status: Accepted

Solution code:
n = int(input())
an = sorted([int(j)-(i+1) for i,j in enumerate(input().split())])
print(sum(abs(i - an[len(an)//2]) for i in an))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.readline().strip()

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

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

med = A[N//2]

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

Submission status: Accepted

Solution code:
import numpy as np

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

A_rot = np.array(list(enumerate(A, 1))).T.astype(np.float128)
theta = np.pi / 4
R = np.array([[np.cos(theta), np.sin(theta)], [-np.sin(theta), np.cos(theta)]], dtype=np.float128)
A_rot = np.dot(R, A_rot).T
loss = np.abs(A_rot[:, 1] - np.median(A_rot[:, 1])).sum()
print(int(np.round(np.sqrt(2) * loss)))

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()
#print(A)

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

if N % 2 == 1:
  print(calc(A[N//2]))
else:
  print(min(calc(A[N//2]),calc(A[(N-1)//2])))

Submission status: Accepted

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

for i in range(1,N+1):
  A[i-1]-=i
A.sort()
#print(A,(N-N%2)//2)
m=A[(N-N%2)//2]
#print(m)

A=list(map(lambda x: abs(x-m),A))
print(sum(A))

Submission status: Accepted

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

Submission status: Accepted

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

B=[A[i]-(i+1) for i in range(N)]
B.sort()
temp=0

if N%2==0:
  ans = B[N//2]
  ans2= B[N//2 -1]
  temp=0
  for j in range(N):
    temp+= abs(B[j] - ans)
  temp2=0
  for j in range(N):
    temp2+= abs(B[j] - ans2)
  ans= min(temp,temp2)
else:
  ans = B[N//2]
  temp=0
  for j in range(N):
    temp+= abs(B[j] - ans )
  ans=temp
print(ans)

Submission status: Accepted

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

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

if N%2==0:
  ans = B[N//2]
  ans2= B[N//2 -1]
  temp=0
  for j in range(N):
    temp+= abs(B[j] - ans)
  temp2=0
  for j in range(N):
    temp2+= abs(B[j] - ans2)
  ans= min(temp,temp2)
else:
  ans = B[N//2]
  temp=0
  for j in range(N):
    temp+= abs(B[j] - ans )
  ans=temp
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

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

a.sort()
m = a[n//2]

print(sum(abs(i-m) for i in a))

Submission status: Accepted

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

import sys
import math
import bisect
import time
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
b = [a[i] - (i+1) for i in range(n)]
b.sort()
if n % 2:
    c = b[n//2]
else:
    c = (b[n//2]+b[n//2-1])//2
ans = 0
for i in range(n):
    ans += abs(a[i] -(c + i+1))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = [A[n]-n for n in range(N)]
A.sort()
if N % 2 == 1:
  A = [abs(a - A[N//2]) for a in A]
  ans = sum(A)
else:
  temp = A
  A = [abs(a - A[N//2]) for a in A]
  ans = sum(A)
  A = [abs(a - temp[N//2-1]) for a in temp]
  ans = min(ans, sum(A))

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

Submission status: Accepted

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = list(map(int, input().rstrip('\n').split()))
    b = []
    for i, v in enumerate(a):
        b.append(v - (i + 1))
    b.sort()
    t = b[len(b) // 2]
    s = 0
    for i, v in enumerate(a):
        s += abs(v - (t + (i + 1)))
    print(s)


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a = [i-idx-1 for idx,i in enumerate(a)]
import statistics as st
b = st.median(a)
print(int(sum([abs(i-b) for i 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()
x=(n-1)//2
ans=0
for i in range(n):
	ans+=abs(a[i]-a[x])
print(ans)

Submission status: Accepted

Solution code:
from statistics import median
import math
n = int(input())
a = [int(i) for i in input().split()]
for i in range(n):
    a[i] -= i+1
a_fl = math.floor(median(a))
a_ce = math.ceil(median(a))
ans_fl=ans_ce=0

for i in range(n):
    ans_fl += abs(a[i]-a_fl)
    ans_ce += abs(a[i]-a_ce)
print(int(min(ans_fl,ans_ce)))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res

def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

n = I()
a = LI()
if n == 1:
    print(0)
    quit()
for i in range(n):
    a[i] -= i+1
a.sort()
b = a[n>>1]
ans = 0
for i in a:
    ans += abs(i-b)
if n%2:
    b = a[(n>>1)+1]
    ans_ = 0
    for i in a:
        ans_ += abs(i-b)
    if ans > ans_:
        ans = ans_
    b = (a[(n>>1)+1]+a[n>>1])>>1
    ans_ = 0
    for i in a:
        ans_ += abs(i-b)
    if ans > ans_:
        ans = ans_
print(ans)

Submission status: Accepted

Solution code:
# 2019/08/13

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

amin=float('inf')
for i in range(n):
    a[i]-=i+1

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
minA = min(A)
for i in range(N):
    A[i] -= i+1 
minA = min(A)
for i in range(N):
    A[i] -= minA
A.sort()
#print(A)

if N %2 == 1:
    ans = A[(N-1)//2]
    t = 0
    for i in range(N):
        t += abs(A[i]-ans)
    ans = t

else:
    ans1 = A[(N)//2]
    ans2 = A[(N)//2 -1]
    t = 0
    for i in range(N):
        t += abs(A[i]-ans1)
    s = 0
    for i in range(N):
        s += abs(A[i]-ans2)
    ans = min(t, s)

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)
B.sort()
b = B[N//2]-1

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

Submission status: Accepted

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

A_diff = []
for i, a in enumerate(A):
    A_diff.append(a - (i + 1))
    

A_diff.sort()
A_diff.reverse()

print(sum(list(map(lambda x : abs(x - A_diff[N//2]), A_diff))))

Submission status: Accepted

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

    b = c[n // 2]
    sad = sum([abs(cc - b) for cc in c])
    print(sad)


main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [a - i for i, a in enumerate(A, 1)]
sorted_B = sorted(B)
b = sorted_B[N // 2]
ans = 0
for i, a in enumerate(A, 1):
    ans += abs(a - (b + i))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
for i in range(N):
  A[i] -= i
A.sort()
med = N//2
b = A[med]
ans = 0
for i in range(N):
  ans += abs(A[i]-b)
print(ans)

Submission status: Accepted

Solution code:
from statistics import median
import math
n = int(input())
a = list(map(int,input().split()))
for i in range(0,n):
    a[i] = a[i]-(i+1)
b1 = round(median(a)) 
a1 = []
a2 = []
for i in range(0,n):
    a1.append(abs(a[i]-b1))
print(sum(a1))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = []
for i in range(N):
    A[i] -= i+1
A.sort()
#for i in range(N):
#    B.append(A[i]-i-1)
#B.sort()
med = N // 2
grief = 0
for i in range(N):
    grief += abs(A[i]-A[med])
#for i in range(N):
#    grief += abs(B[i]-B[med])
print(str(grief))

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = [0] * n
ans = 0

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

sort_b = sorted(b)
num = sort_b[n // 2]

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

print(ans)

Submission status: Accepted

Solution code:
# ARC100C - Linear Approximation (ABC102C)
def main():
    n = int(input())
    A = tuple(map(int, input().rstrip().split()))
    A = sorted(j - i for i, j in enumerate(A, start=1))
    b = A[n // 2]
    ans = sum(abs(a - b) for a in A)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from statistics import median
N = int(input())
As = list(map(int,input().split()))
calcA = sorted([As[i]-(i+1) for i in range(len(As))])
med = median(calcA)
print(int(sum([abs(As[i]-(med+i+1)) for i in range(len(As))])))

Submission status: Accepted

Solution code:
import sys
import numpy as np


def main():
    n = int(input())
    a = np.array([int(x) for x in input().split()])
    a -= np.arange(1, n + 1)
    a -= int(np.median(a))
    print(np.sum(np.abs(a)))


main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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

a.sort()
if n % 2 == 0:
    center = (a[n//2] + a[n//2-1]) // 2
else:
    center = a[(n-1)//2]
sub = lambda x: abs(x - center)
print(sum(list(map(sub, a))))

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

b = A_[N//2]
print(sum([abs(ai-b) for ai in A_]))

Submission status: Accepted

Solution code:
N = int(input())
Ap = [int(x) for x in input().split()]
A = sorted([Ap[i]  -i-1 for i in range(N)])

if N % 2 != 0:
    b = A[(N+1)//2 - 1]
    print( sum( [abs(x-b) for x in A] ) )
else:
    mf,mb = A[N//2-1], A[N//2]
    if mb - mf >= 2:    b = mb -1
    else:  b = mb
    print( sum( [abs(x-b) for x in A] ) )

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
for i in range(n):
    a[i]-=(1+i)
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()))

Alist = [A[i]-(i+1) for i in range(N)]
Alist.sort()
x = N//2
b = Alist[x]
ans = 0
for i in range(N) :
    ans += abs(Alist[i]-b)
    
print(ans)

Submission status: Accepted

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

a = sorted([aa - i for i, aa in enumerate(a, start = 1)])
b = a[n//2] if n%2 > 0 else (a[n//2-1]+a[n//2])//2
ans = sum([abs(aa - b) for aa 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
  
mode = sorted(A)[N//2]

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a_list=[int(s)-(i+1) for i,s in enumerate(input().split())]
a_list.sort()

total=0
for i in a_list:
    total+=abs(i-a_list[n//2])
print(total)

Submission status: Accepted

Solution code:
import math
import numpy as np
N = int(input())
A = [int(_) for _ in input().split()]
B = [A[i] - i for i in range(N)]
B.sort()
C = np.array(B)
print(np.sum([abs(C[i]-C[math.floor(N/2)]) for i in range(N)]))

Submission status: Accepted

Solution code:
n=int(input())
arr=list(map(int,input().split()))
for i in range(n):
  arr[i]=arr[i]-(i+1)
arr=sorted(arr)
if n%2==1:
  m=arr[n//2]
  ans=0
  for i in range(n):
    ans=ans+abs(arr[i]-m)
  print(ans)
else:
  m1=arr[n//2]
  m2=arr[n//2-1]
  ans1=0
  ans2=0
  for i in range(n):
    ans1=ans1+abs(arr[i]-m1)
    ans2=ans2+abs(arr[i]-m2)
  print(min(ans1,ans2))

Submission status: Accepted

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

l = sorted([ x - (idx+1) for x,idx in enumerate(A)])
#print(l)

import statistics
median = statistics.median(l)
#print(median)

ans = 0
for x in l:
  ans += abs(x - median)
  
print(int(ans))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
li = [ int(it) for it in input().split() ]
li = [ li[i]-i-1 for i in range(N) ]
li.sort()

p = li[N//2]
pi = [ abs(it-p) for it in li ]
print ( sum(pi) )

Submission status: Accepted

Solution code:
#平均値に近づけるという考え方が間違い-->中央値に近づける

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

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

A.sort()

center1 = A[N//2]
if N == 1:
    center2 = 10 ** 9
else:
    center2 = A[(N+2)//2]

ans1 = 0
for i in range(N):
    ans1 +=abs(A[i]-center1)
    
ans2 = 0
for j in range(N):
    ans2 += abs(A[j]-center2)
    
print (min(ans1, ans2))

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.sort()
b=a_list[n//2]
Sum=0
for i in a_list:
    Sum=Sum+abs(i-b)
print(Sum)

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=sorted(B)

center=B[N//2] if N%2==1 else round((B[(N-1)//2]+B[(N+1)//2])/2)
ans=0
for i in B:
    ans+=abs(i-center)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
B = [a - i for i, a in enumerate(A)]
B.sort()
def median(list):
    L = sorted(list)
    n = len(L)
    m = int(n/2)
    if n % 2 == 0:
        return (L[m - 1] + L[m]) / 2
    else:
        return L[(n - 1) // 2]
b = int(median(B))
print(sum(abs(x - b) for x in B))

Submission status: Accepted

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

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

aa=sorted(a)
if n%2==0:
  b=(aa[int(n/2-1)]+aa[int(n/2)])/2
else:
  b=aa[int((n-1)/2)]

s=0
for i in aa:
  s+=abs(i-b)
print(int(s))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
B, SUM = [], 0

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

Bs = sorted(B)
if n%2 == 1:
    b = Bs[n//2]
else:
    b = (Bs[n//2-1]+Bs[n//2])//2
ans = 0
for i in B:
    ans += abs(i-b)
print(ans)

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

Submission status: Accepted

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

aa = [ai - i-1 for i,ai in enumerate(a)]

def tri_search(f:"f(x:float)->float", left, right, iter=100)->float:
    for _ in range(iter):
        ml = (left*2 + right) / 3
        mr = (left + right*2) / 3
        if f(ml) < f(mr):
            right = mr
        else:
            left = ml
    # print(left, right)
    return (right + left) / 2

def f(x):
    ret = 0
    x = int(x+0.5)
    for aai in aa:
        ret += abs(aai - x)
    return ret

b = tri_search(f, -10**9, 10**9)
print(min(f(b), f(b+1), f(b-1)))

Submission status: Accepted

Solution code:
n,a=int(input()),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 a:ans+=abs(i-b)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
B = [a[i] - i 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:
N = int(input())
A = list(map(int,input().split()))
B = []
for i in range(N):
    B.append(A[i] - i - 1)
B.sort()
cen = B[N//2]
sum = 0
for i in range(N):
    sum += abs(B[i]-cen)
print(sum)

Submission status: Accepted

Solution code:
def mm(N, A, x):
  S = 0
  for i in range(N):
    S += abs(A[i] - x)
  return S

N = int(input())
A = []
j = 0
for i in input().split():
  j += 1
  A.append(int(i)-j)
A.sort()
if N % 2 == 0:
  print(mm(N, A, A[N//2]))
elif N == 1:
  print(0)
else:
  print(min(mm(N, A, A[N//2]), mm(N, A, A[N//2 + 1])))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split(' ')))
num = 0
X = []
for i,j in enumerate(A):
  B = j-(i+1)
  X.append(B)
X.sort()
median = 0
if N % 2 == 0:
  median = (X[int(N/2)] + X[int(N/2-1)])/2
else:
  median = X[int((N-1)/2)] 

for x in X:
  num += abs(x-median)
print(int(num))

Submission status: Accepted

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

a = sorted([aa-i for i, aa in enumerate(a, start = 1)])
med = (a[n//2-1]+a[n//2])//2 if n%2 == 0 else a[n//2]
ans = sum([abs(aa - med) for aa in a])
print(ans)

Submission status: Accepted

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

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

if N % 2 == 1:
    median = A[N//2]
    sad = sum([abs(A[i] - median) for i in range(N)])
else:
    hoge, fuga = (A[N//2-1]+A[N//2])//2, (A[N//2-1]+A[N//2])//2+1
    sad = min(sum([abs(A[i] - hoge) for i in range(N)]), sum([abs(A[i] - fuga) for i in range(N)]))
print(sad)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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

l.sort()
t = l[int(len(l) / 2)]

for i in range(len(l)):
    l[i] = abs(l[i] - t)
    
print(sum(l))

Submission status: Accepted

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

B = [a - i for i, a in enumerate(A)]
B.sort()
median = B[(N - 1) // 2]
print(sum(abs(b - median) for b in B))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
#a, b, c = map(int, input().split())
#name1 = str(input())
#alph = {"A": 1, "B": 2, "C": 3, "D": 4, "E": 5}
for i in range(N):
    A[i] = A[i] - (i + 1)
A.sort()
b = A[int(N / 2)]
ans = 0
for i in range(N):
    ans += abs(A[i] - b)
print(ans)