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:
n=int(input())
a=list(map(int,input().split()))

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

if n%2==0:
  tmp=(a[n//2]+a[n//2-1])//2
else:
  tmp=(a[n//2])
  
ans=0
for aa in a:
  ans+=abs(aa-tmp)
#print(tmp)
#print(a)
print(ans)

Submission status: Accepted

Solution code:

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

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

X = sorted(X)
#bは数列Xの中央値
if N%2==1:
    b = X[N//2]
else:
    b = (X[N//2-1] + X[N//2]) / 2

out=0
for i in range(N):
    out+=abs(X[i] - b)

print(int(out))

Submission status: Accepted

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()
if n==1:
    m=B[0]
    m2=B[0]
else:
    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: Accepted

Solution code:
n,*a = map(int,open(0).read().split())
a = sorted([a[i] -i for i in range(n)])
print(sum([abs(i - a[n//2]) for i in a]))

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)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

def main():
	n = int(input())
	arr = list(map(int , input().split()))
	for i in range(0 , n):
		arr[i]=arr[i]-(i+1)
	ans=0
	md=0
	arr.sort()
	if n%2==0:
		md = (arr[n//2-1]+arr[(n//2)])//2
	else:
		md = arr[n//2]
	for i in range(0,n):
		ans = ans +abs(arr[i]-md)
	print(ans)
if __name__=="__main__":
	main()

Submission status: Accepted

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 statistics

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 = statistics.median(a)
print(int(f(c)))

Submission status: Accepted

Solution code:

        
def main():
    import sys
    from bisect import bisect_left, bisect_right
    def input(): return sys.stdin.readline().rstrip()

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




                
if __name__ == '__main__':
    main()

Submission status: Accepted

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 = int(round(np.median(numbers)))
numbers-= b
number = np.abs(numbers)
print(number.sum())

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
a = LIST()
for i in range(n):
    a[i] -= i + 1
a.sort()
b = a[n//2]
ans = 0
for x in a:
    ans += abs(x - b)
print(ans)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()


def resolve():
    N = I()
    A = LI()

    AA = [A[i] - (i + 1) for i in range(N)]
    AA.sort()
    b = AA[N//2]
    ans = sum([abs(A[i] - (b + i + 1)) for i in range(N)])

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
#coding: utf-8

import math

N = int(input())
A = [int(n) for n in input().split()]
for i in range(len(A)):
    A[i] -= (i+1)
A.sort()

med = 0
if N % 2 == 0:
    m1 = N // 2
    m2 = m1 - 1
    med = round((A[m1] + A[m2]) / 2)
else:
    m1 = (N+1) // 2
    med = A[m1-1]

sad = sum([abs(a-med) for a in A])

print(sad)

Submission status: Accepted

Solution code:
def solve():
  ans = 0
  N = int(input())
  A = list(map(int, input().split()))
  for i in range(N):
    A[i] -= i+1
  B = sorted(A)
  p = B[N//2]
  for i in range(N):
    A[i] = abs(A[i]-p)
  ans = sum(A)
  return ans
print(solve())

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


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

    A = [a - i for i, a in enumerate(A, start=1)]
    A.sort()

    b = A[(N + 1) // 2 - 1]
    ans = sum(map(lambda x: abs(x - b), A))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import statistics
n = int(input())
a = []
for i,j in enumerate(map(int,input().split())):
  a.append(j-i-1)
b,s = statistics.median(a),0
for i in a:
  s+=abs(i-b)
print(int(s))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from statistics import median
n = int(input())
A = list(map(int,input().split()))
A = [a-i-1 for i,a in enumerate(A)]
A.sort()
mA = int(median(A))
print(min([sum([abs(a-mA-1) for a in A]), sum([abs(a-mA) for a in A]), sum([abs(a-mA+1) for a in A])]))

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = list(map(int,input().split()))
A = [A[i] - i - 1 for i in range(N)]

A = np.array(A)

k = int(np.median(A))

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

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
b=a[:]
b.sort()
mid1=0
mid2=0
if n%2==1:
  ans=0
  mid1=b[n//2]
  for bb in b:
    ans+=abs(bb-mid1)
  print(ans)
else:
  mid1=b[n//2]
  mid2=b[n//2-1]
  ans1,ans2=0,0
  for bb in b:
    ans1+=abs(bb-mid1)
    ans2+=abs(bb-mid2)
  print(min(ans1,ans2))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int,input().split()))
    for i in range(N):
        A[i] -= i+1
    
    def f(b):
        res = 0
        for a in A:
            res += abs(a-b)
        return res
    
    INF = 10**9+10
    l = -INF
    r = +INF

    while l < r-2:
        m1 = (r-l)*2//3+l
        m2 = (r-l)//3+l
        tmp1 = f(m1)
        tmp2 = f(m2)

        if tmp2 < tmp1:
            r = m1
        else:
            l = m2
    print(f((l+r)//2))

main()

Submission status: Accepted

Solution code:

def main():
    from math import floor,ceil
    N = int(input())
    A = list(map(int,input().split()))
    for i in range(N):
        A[i] -= i+1
    
    def f(b):
        res = 0
        for a in A:
            res += abs(a-b)
        return res
    INF = 10**9+10
    l = -INF
    r = INF
    min_saddness = 10**15
    while l < r-2:
        m1 = (r-l)*2//3+l
        m2 = (r-l)//3+l
        tmp1 = f(m1)
        tmp2 = f(m2)

        if tmp2 < tmp1:
            r = m1
        else:
            l = m2
    print(f((l+r)//2))

main()

Submission status: Accepted

Solution code:
n = int(input())
A = [int(x) for x in input().split()]
A_ = sorted([a - i for i, a in enumerate(A, 1)])
i = len(A) // 2
b = A_[i]
ans = sum([abs(a - b) for a in A_])
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split()))) - np.array(list(range(1, N+1)))
A = A.astype(np.int64)
m = np.median(A)
m = m.astype(np.int64)
A -= m
ans = sum(np.abs(A))
print(ans.astype(np.int64))

Submission status: Accepted

Solution code:
import statistics

if __name__ == "__main__":
    N = int(input())
    A = [float(x) for x in input().split(" ")]
    A = [a - i - 1 for i, a in enumerate(A)]
    med = statistics.median(A)
    A = [abs(a - med) for a in A]
    print(int(sum(A)))

Submission status: Accepted

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

def solve(N: int, A: "List[int]"):
    A = sorted(a - i for i, a in enumerate(A))
    m = A[N//2]
    return sum(abs(a-m) for a in A)


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = sorted(int(a) - i for i, a in enumerate(input().split(), 1))
if N % 2:
    median = A[N // 2]
    print(sum(abs(a - median) for a in A))
else:
    median1 = A[N // 2 - 1]
    median2 = A[N // 2]
    print(min(sum(abs(a - median1) for a in A), sum(abs(a - median2) for a 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:
    median = A[N // 2]
    print(sum(abs(a - median) for a in A))
else:
    median1 = A[N // 2 - 1]
    median2 = A[N // 2]
    print(min(sum(abs(a - median1) for a in A), sum(abs(a - median2) for a in A)))

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()
k=B[N//2]

C=map(lambda x:abs(x-k),B)
print(sum(C))

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 range(n):
    ans+=abs(a[i]-b)

print(ans)

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# a^n
def power(a,n,mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod

# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n-1
    while(tmp >= l):
        a = a*tmp%mod
        tmp -= 1
    return a

inf = 10**18
mod = 10**9+7

n = ir()
a = lr()
total = 0
for i,num in enumerate(a):
    a[i]=(num-(i+1))
a.sort()
if n%2 == 0:
    mean = (a[n//2-1]+a[n//2])//2
else:
    mean = a[n//2]
ans = [0,0]
for i in range(mean, mean+2):
    tmp = i%2
    for num in a:
        ans[tmp]+=abs(num-i)
print(min(ans))

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = []
    for i,ai in enumerate(ipt().split()):
        a.append(int(ai)-i-1)
    a.sort()
    b = a[n//2]
    ans = 0
    for i in a:
        ans += abs(i-b)
    print(ans)


    return

if __name__ == '__main__':
    main()

Submission status: Accepted

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

a_new=[0]*n
for i in range(n):
    a_new[i]=a[i]-i
a_new.sort()
b=a_new[(n-1)//2]
ans=0
for i in range(n):
    ans+=abs(a[i]-i-b)

print(int(ans))

Submission status: Accepted

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
for i in range(1, n+1):
    a[i-1] -= i 
a.sort()
b = n // 2
if n % 2 == 1:
    b = a[n//2]
else:
    b = (a[n//2] + a[n//2 - 1])//2
ans = 0
for x in a:
    ans += abs(x - b)
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()
flag = True
if n % 2 == 1:
    b = A[(n-1)//2]
else:
    if A[n//2] == A[n//2-1]:
        b = A[n//2]
    else:
        flag = False
if flag:
    ans = 0
    for i in A:
        ans += abs(i-b)
    print(ans)
else:
    ans1=0
    ans2=0
    for i in A:
        ans1 += abs(i-A[n//2])
        ans2 += abs(i-A[n//2-1])
    print(min(ans1,ans2))

Submission status: Accepted

Solution code:
import math

def isinteger(n):
    if isinstance(n, int):
        return True
    elif isinstance(n,float):
        return n.is_integer()
    return False

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-1)//2]
else:
    b = (A[n//2]+A[n//2]-1)/2
if isinteger(b):
    ans = 0
    for i in A:
        ans += abs(i-b)
    print(ans)
else:
    ans1=0
    ans2=0
    b1= math.floor(b)
    b2=b1+1
    for i in A:
        ans1 += abs(i-b1)
        ans2 += abs(i-b2)
    print(min(ans1,ans2))

Submission status: Accepted

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

A = sorted([a-i-1 for i, a in enumerate(A)])
i = int(len(A)/2)
b = A[i]

print(sum([abs(a-b) for a 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:
    b = a[n//2]
    ans = 0
    for i in range(n):
        ans += abs(a[i] - b)
    print(ans)
else:
    b1 = (a[n//2-1] + a[n//2] + 1) // 2
    b2 = (a[n//2-1] + a[n//2]) // 2
    ans1, ans2 = 0, 0
    for i in range(n):
        ans1 += abs(a[i] - b1)
        ans2 += abs(a[i] - b2)
    print(min(ans1, ans2))

Submission status: Accepted

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

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

rlt = 0
n = N//2
for a in As:
  rlt += abs(a-As[n])

print(rlt)

Submission status: Accepted

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
#from itertools import combinations # (string,3) 3回
#from collections import deque
#from collections import deque,defaultdict
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = readInts()
for i in range(1,n+1):
    A[i-1] -= i
#print(A)
medi = median(A)
medi = int(medi) if medi - int(medi) < 0.5 else int(medi) + 1
ans = 0
for i in range(n):
    ans += abs(A[i] - medi)
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
n = int(input())
arr = np.array(list(map(int, input().split())))

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

diff.sort()

diff = diff - np.median(diff)

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

Submission status: Accepted

Solution code:
import numpy as np

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

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

b = int(np.median(diff))

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, = map(int, input().split())
l = [j-i for i, j in enumerate(A, start=1)]
l.sort()

b = l[N//2]
ans = 0
for i in l:
    ans += abs(i-b)
print(ans)

Submission status: Accepted

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

c1=a[n//2-1]
c2=a[n//2]
ans=float('inf')

for c in [c1,c2]:
    tmp=0
    for i in range(n):
        tmp+=abs(a[i]-c)
    ans=min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
n, *lst = map(int, open(0).read().split())
lst = sorted([lst[i] - i - 1 for i in range(n)])
res = sum(abs(lst[n // 2] - j) for j in lst)
print(res)

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
#import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect

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

Submission status: Accepted

Solution code:
from statistics import median

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

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

b=median(B)

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

print(int(ans))

Submission status: Accepted

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

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

c.sort()
b = c[n//2]
ans = 0
for j in range(n):
    ans += abs(c[j] - b)

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]

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

print(s)

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:
    ans=0
    b=a[n//2]
    for i in a:
        ans+=abs(i-b)
    print(ans)
else:
    ans1,ans2=0,0
    b1=a[n//2-1]
    b2=a[n//2]
    for i in a:
        ans1+=abs(i-b1)
        ans2+=abs(i-b2)
    print(min(ans1,ans2))

Submission status: Accepted

Solution code:

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
import itertools
import math
# import networkx as nx
from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n=n0()
A=n1()

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

if n%2==1:
    b=A2[n//2]
    ans=sum([abs(A[i-1]-i-b) for i in range(1,n+1)])
else:
    b1=A2[n//2-1]
    b2=A2[n//2]
    ans1=sum([abs(A[i-1]-i-b1) for i in range(1,n+1)])
    ans2=sum([abs(A[i-1]-i-b2) for i in range(1,n+1)])
    ans=min(ans1,ans2)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
*A, = map(int, input().split())
B = sorted([j-i for i, j in enumerate(A, start=1)])
b = B[N//2]
print(sum(abs(i-b) for i 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()
ans = 0
b = a[n//2]
for i in range(n):
    ans += abs(a[i]-b)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
x = [int(i) for i in input().split()]
c = []
for i,xi in enumerate(x):
  c.append(xi-i-1)
c.sort()
if n%2 == 1:
  b = c[n//2]
else:
  b = (c[n//2-1]+c[n//2])//2
ans = 0
for i in c:
  ans += abs(i-b)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
aa = []
for i, j in enumerate(a):
    aa.append(j-i-1)
aa.sort()
b = aa[n//2]
ans = 0
for i in aa:
    ans += abs(i-b)
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()
median = b[n // 2]

c = []
for i in range(n):
    c.append(abs(b[i] - median))

print(sum(c))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/arc100/tasks/arc100_a

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

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

Submission status: Accepted

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

for i in range(n):
    list_A[i] -= i + 1
list_A.sort()
b = 0
if n % 2 == 1:
    b = list_A[n//2]
else:
    b = (list_A[n//2]+list_A[n//2-1])//2

ans = 0

for num in list_A:
    ans += abs(num-b)

print(ans)

Submission status: Accepted

Solution code:
import statistics
def main():
    N, A = int(input()), list(map(int, input().split()))
    for i in range(N):
        A[i] -= i + 1
    m = int(statistics.median(A))
    a, b = m, m + 1
    c, d = 0, 0
    for el in A:
        c += abs(el-a)
        d += abs(el-b)
    print(min(c, d))
main()

Submission status: Accepted

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

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

s.sort()
a = s[(n+1)//2 - 1]

res = 0
for ss in s:
    res += abs(ss - a)
print(res)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

sum = 0
for i in A:
    sum += abs(i-median)
print(int(sum))

Submission status: Accepted

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

Submission status: Accepted

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

dic=defaultdict(int)
result=0
posi=0

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

sort_dic=sorted(dic.items())

for j in sort_dic:
    if posi+j[1]>N//2:
        siki=j[0]
        break
    else:
        posi+=j[1]

for k in sort_dic:
    result+=abs(k[0]-siki)*k[1]

print(result)

Submission status: Accepted

Solution code:
n = int(input())
A = [a-i-1 for i, a in enumerate(map(int, input().split()))]
if n & 1:
    mid = n//2
else:
    mid = (n-1)//2
median = sorted(A)[mid]
print(sum(map(lambda x: abs(x-median), A)))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [x - i for i, x in enumerate(map(int, input().split()), start=1)]
    A.sort()

    m = A[N // 2]  # 個数の偶奇によらず、この点は絶対値の総和を最小にする

    ans = sum(abs(x - m) for x in A)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ave = B[N//2]
ans = 0
for i in range(N):
    ans += abs(B[i]-ave)
print(ans)

Submission status: Accepted

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

ave1,ave2 = B[N//2],B[N//2-1]
ans1,ans2 = 0,0
for i in range(N):
    ans1 += abs(B[i]-ave1)
    ans2 += abs(B[i]-ave2)
print(ans1)

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

kb = [b[n//2],b[n//2]]

ans = []

for i in kb:
    x = 0
    for s in range(len(a)):
        x += abs(a[s]-i-s)
    ans.append(x)
    
print(min(ans))

Submission status: Accepted

Solution code:
import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

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

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

    

    
resolve()

Submission status: Accepted

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

B = []
for i,a in enumerate(A):
    B.append(a-(i+1))
B.sort()
C = B[N//2-1:N//2+2]

MIN = 10**18
for j in C:
    ans = 0
    for i in B:
        ans += abs(i-j)

    MIN = min(ans,MIN)

print(MIN)

Submission status: Accepted

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

B.sort()

ans = 0
t = B[len(B)//2]

for x in B:
    ans += abs(x - t)

print(ans)

Submission status: Accepted

Solution code:
import sys
import statistics
sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    b = statistics.median(A)

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

    print(int(res))


if __name__ == '__main__':
    resolve()

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()
lb = [B[N//2]-1,B[N//2]]

sad = float("inf")
for b in lb:
  c = 0
  for j in range(N):
    c += abs( A[j]-(b+j+1) )
  sad = min(sad,c)
print(sad)

Submission status: Accepted

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

ave1,ave2 = B[N//2],B[N//2-1]
ans1,ans2 = 0,0
for i in range(N):
    ans1 += abs(B[i]-ave1)
    ans2 += abs(B[i]-ave2)
print(min(ans1,ans2))

Submission status: Accepted

Solution code:
def resolve():
    n = int(input())
    a = list(map(int, input().split()))
    a1 = []
    for i in range(len(a)):
        a1.append(a[i]-i-1)
    a2 = sorted(a1)
    if len(a2)%2 == 0:
        mda = a2[len(a2)//2]
    else:
        mda = a2[(len(a2)-1)//2]
    ans = 0
    for i in range(len(a2)):
        ans += abs(mda-a2[i])
    print(ans)
resolve()

Submission status: Accepted

Solution code:
n=int(input())
b=[int(a-(i+1))  for i,a in enumerate(list(map(int,input().split())))]
if n==1:
  print(0)
  exit(0)
bm=b[:]
bm.sort()
mid_1=bm[n//2]
mid_2=bm[(n//2)+1]
ans_1,ans_2=0,0
if n%2==1:
  for bb in b:
    ans_1+=abs(bb-mid_1)
  print(ans_1)
else:
  for bb in b:
    ans_1+=abs(bb-mid_1)
    ans_2+=abs(bb-mid_2)
  print(min(ans_1,ans_2))

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()
c=b[n//2]
ans=100000000000000000000
for i in range(c-2,c+3):
  temp=0
  for j in range(n):
    temp+=abs(b[j]-i)
  if temp<ans:
    ans=temp
print(ans)