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 sys
import os
import math
import string

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()
    di = {}
    for i, a in enumerate(A):
        di[i] = - a + i + 1

    di = sorted(di.items(), key=lambda x: x[1])
    md = di[len(di) // 2][1]

    ret = 0
    for d in di:
        ret += abs(md - d[1])

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import os
import math
import string

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')

def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()
    ret = {}
    for i, v in enumerate(A):
        ret[i] = v - (i + 1)

    ret = sorted(ret.items(), key=lambda x:x[1])
    md = ret[len(ret)//2][1]

    ans = 0
    for r in ret:
        ans += abs(r[1] - md)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))
for i in range(n):
  a[i] = a[i]-(i+1)
b = int(np.median(a))
ans = 10**18
ans_lis = [b-1, b, b+1]
for i in ans_lis:
  ans = min(ans, np.sum(np.abs(a-i)))
  
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    A=list(map(int,input().split()))
    for i in range(N):
        A[i]-=i+1
    A.sort()
    def f(x):
        tmp=0
        for a in A:
            tmp+=abs(a-x)
        return tmp
    print(min(f(A[N//2]),f(A[N//2-1])))
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import ceil
n = int(input())
ns = list(map(int, input().split()))
new_ns = sorted([num - i - 1 for i, num in enumerate(ns)])
b = new_ns[n // 2]
print(sum(abs(num-b) for num in new_ns))

Submission status: Accepted

Solution code:
import statistics

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

Submission status: Accepted

Solution code:
import sys
## io
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
MIIZ = lambda: list(map(lambda x: x-1, MII()))
## dp
INIT_VAL = 0
DP2 = lambda d1, d2: [[INIT_VAL]*d2 for _ in range(d1)]
DP3 = lambda d1, d2, d3: [[[INIT_VAL]*d3 for _ in range(d2)] for _ in range(d1)]
## math
DIVC = lambda x, y: -(-x//y)
DIVF = lambda x, y: x//y
from collections import Counter

def main():
    n = II()
    aa = MII()
    aa = [a-(i+1) for i, a in enumerate(aa)]
    aa.sort()
    m = aa[(n//2)]
    res = sum([abs(a-m) for a in aa])
    print(res)

if __name__ == '__main__':
    main()

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 a in A:
    ans+=abs(a-b)
print(ans)

Submission status: Accepted

Solution code:
# solution

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

a_i = sorted([a[i] - (i+1) for i in range(data)])

b = a_i[(data)//2]

result = sum([abs(a_i[i] - b) for i in range(data)])

print(result)

Submission status: Accepted

Solution code:
from statistics import median_low

n = int(input())
lst = list(map(int, input().split()))
mid = [None for i in range(n)]
end = [None for i in range(n)]

for i in range(n):
    mid[i] = lst[i]-i
# print(mid)

num = mid.index(median_low(mid))
for i in range(n):
    end[i] = lst[num]-num+i
# print(end)

ans = 0
for i in range(n):
    ans += abs(lst[i]-end[i])
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.sort()
cnt=0
#print(x)
line=x[N//2]
for i in range(N):
    cnt=cnt+abs(line-x[i])
print(cnt)

Submission status: Accepted

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


pr_abs.sort()
if len(a_list) % 2 == 1:
  median = pr_abs[(n-1)//2]
  ans = 0
  for i in range(n):
    ans += abs(pr_abs[i] - median)
else:
  median = (pr_abs[(n-2)//2] + pr_abs[n//2])//2
  ans = 0
  for i in range(n):
    ans += abs(pr_abs[i] - median)
    
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

a = [int(i)-j for i,j in zip(input().split(),range(n))]

l = -10 ** 10

r = 10 ** 10

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

while r - l > 3:
  l_r = (r - l) // 3
  l_i = l + l_r
  i_r = r - l_r
  if f(l_i) > f(i_r):
    l = l_i
  else:
    r = i_r
print(min(f(l),f(l+1),f(l+2),f(l+3)))

Submission status: Accepted

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



# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N = int(input())
    a = list(map(int,input().split()))
    l = [(a[i]- i-1) for i in range(N)]
    
    l_sorted = sorted(l)
    if N % 2 == 0:
        b_1 = l_sorted[int(N/2)-1]
        b_2 = l_sorted[int(N/2)]
        answer_1 = 0
        answer_2 = 0
        for i in range(N):
            answer_1 += abs(l[i] - b_1)
        for i in range(N):
            answer_2 += abs(l[i] - b_2)

        print(min(answer_1, answer_2))
        exit()
        
    else:
        b = l_sorted[int(N/2)]
        answer = 0
        for i in range(N):
            answer += abs(l[i] - b)

        print(answer)
        return


if __name__ == '__main__':
    main()

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

Submission status: Accepted

Solution code:
from collections import Counter as C
n,*a=map(int,open(0).read().split())
a=C([a[i]-i-1 for i in range(n)])
a=sorted(a.items(),key=lambda x:x[0])
s=0
b=0
ans=0
for i in a:
  s+=i[1]
for i in a[::-1]:
  s-=2*i[1]
  if s<0:
    b=i[0]
    break
for i in a:
  ans+=i[1]*abs(i[0]-b)
print(ans)

Submission status: Accepted

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

'''
A = sorted([i-k-1 for k,i in enumerate(A)])
b = A[N//2]
print(sum(abs(i-b) for i in A))
'''
for i in range(N):
    A[i] = A[i]-i-1
A.sort()
b = A[N//2]
print(sum(list(map(lambda x:abs(x-b),A))))

Submission status: Accepted

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

A = sorted([i-k-1 for k,i in enumerate(A)])
b = A[N//2]
print(sum(abs(i-b) for i in A))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n = ni()
a = nl()

b = sorted([a[i] - i for i in range(n)])
meds = []
out = []
if n % 2 == 1:
    meds.append(b[n//2])
else:
    meds.append(b[n//2])
    meds.append(b[n//2 - 1])

for med in meds:   
    ans = 0   
    for num in b:
        ans += abs(num - med)
    out.append(ans)

print(min(out))

Submission status: Accepted

Solution code:
N=int(input())
A=sorted(a-i-1 for i,a in enumerate(map(int,input().split())))
#A-iを取り出して昇順に並べる
print(sum(abs(a-A[N//2]) for a in A))

Submission status: Accepted

Solution code:
import sys
import numpy as np

n = int(sys.stdin.readline().rstrip())
a = np.array(sys.stdin.readline().split(), dtype=np.int64)
a -= np.arange(1, n + 1)
a.sort()

def main():
    b = a[n//2]
    print(np.absolute(a - b).sum())

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回

mod = 10**9 + 7

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

    n = int(input())
    A = readInts()
    B = [a - i for i,a in enumerate(A,1)] # index 1 から
    from statistics import median

    medi = int(median(B))
    print(sum([abs(a-medi) for a in B]))




    """sumA = sum(A)
    facA = (n * (n+1))//2
    na = sumA - facA

    if na / n < 0:
        p = na/n
        if abs(p) % 10 != 0:
            b = int(p) - 1
        else:
            b = int(p)
    else:
        b = round(na/n)
    #print(b)
    ans = 0
    nya = len(A)
    for i in range(len(A)):
        #print(A[i],b,i+1)
        print(i)
        ans += abs(A[i] - (b + (i+1)))
    print(ans)"""



if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import statistics

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

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

b = int(statistics.median(bi))

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

print(ans)

Submission status: Accepted

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

for i in range(n):
  base[i] = a[i] - (i+1)
  
judge = n%2
temp_1 = 0
temp_2 = 0
ans = 0
base.sort()

if judge == 0:
  for i in range(n):
    temp_1 = temp_1 + abs(base[i] - base[n//2 - 1])
    temp_2 = temp_2 + abs(base[i] - base[n//2])
    
  if temp_1 <= temp_2:
    ans = temp_1
  elif temp_2 < temp_1:
    ans = temp_2
    
elif judge == 1:
  for i in range(n):
    ans = ans + abs(base[i] - base[(n-1)//2])
    
print(ans)

Submission status: Accepted

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

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



med=np.median(A)
def sudness(A):
  sad=0
  for a in A:
    sad+=abs(a)
  return int(sad)

print(sudness(A-med))

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
a = np.array([int(x)-i-1 for x, i in zip(input().split(), range(n))])
ans = np.sum(np.abs(a-int(np.median(a))))
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(x - b[i])
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a_lst = [int(elem) for elem in input().split()]
b_lst = [(a - i - 1) for i, a in enumerate(a_lst)]
b_lst = sorted(b_lst)

med = b_lst[n // 2]
res = 0
for i in range(n):
    res += abs(b_lst[i] - med)
print(res)

Submission status: Accepted

Solution code:
n = int(input())
ai = [int(i) for i in input().split()]
bi = []
for i in range(len(ai)):
    bi.append(ai[i]-(i+1))
bi = sorted(bi)
b = bi[int(len(bi)/2)]
ans = 0
for i in range(len(ai)):
    ans += abs(ai[i] - (b+i+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()

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

Submission status: Accepted

Solution code:
n=int(input())
lists=list(map(int,input().split()))
uselists=[]
for _ in range(n):
    uselists.append(lists[_]-_-1)
uselist=sorted(uselists)
if n%2==0:
    num1=int(n/2-1)
    num2=int(n/2)
    numbers=min(uselist[num1],uselist[num2])
    
if n%2!=0:
    num1=int((n-1)/2)
    numbers=uselist[num1] 
ans=0
for x in range(n):
    ans+=abs(uselist[x]-numbers)
print(ans)

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:

from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from functools import reduce

from collections import deque, Counter, defaultdict
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import statistics
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
def lcm(a, b):
  return a*b//gcd(a, b)

def main():
  n = int(readline())
  a = np.array(readline().split(), np.int64)
  a -= np.arange(1,n+1)
  median = np.median(a).astype(np.int64)

  print(np.abs(a-median).sum())
  
  
  
  
  
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    a = list(map(int, input().split()))
    b = []
    for i in range(n):
        b.append(a[i]-i-1)
    b.sort()
    if n%2==0:
        c = b[n//2]
        d = b[n//2-1]
        res1 = 0
        res2 = 0
        for i in b:
            res1 += abs(i-c)
            res2 += abs(i-d)
        print(min(res1, res2))
        exit()
    else:
        c = b[n//2]
        res = 0
        for i in b:
            res += abs(i-c)
        print(res)
        exit()
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

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

A.sort()
psum = list(itertools.accumulate(A))
# print(A, psum)

right = max(A)
left = min(A)
min_val = float("inf")
for i in range(n):
    low = A[i]*i - psum[i-1] if i > 0 else 0
    high = psum[-1] - psum[i] - A[i]*(n-i-1) if i < n-1 else 0
    min_val = min(min_val, low+high)
    # print(i, low, high, low+high, min_val)

print(min_val)

Submission status: Accepted

Solution code:
import sys
import math

def resolve():
    N = int(input())
    A = list(map(int, input().split(" ")))
    Adiff = sorted([a - i for i, a in enumerate(A)])
    if N % 2 == 0:
        print(min(
            sum([abs(ad - Adiff[N//2]) for ad in Adiff]),
            sum([abs(ad - Adiff[N//2+1]) for ad in Adiff])
        ))
    else:
        print(sum([abs(ad - Adiff[N//2]) for ad in Adiff]))

if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
N=int(input())
alist=list(map(int,input().split()))
#print(alist)

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

blist.sort()
#print(blist)
b=blist[N//2]
#print(b)
answer=0
for i in range(N):
  answer+=abs(alist[i]-(b+i+1))
  
print(answer)

Submission status: Accepted

Solution code:
n = int(input())
ai = [int(e) for e in input().split()]
bi = []
for i in range(len(ai)):
    bi.append(ai[i]-i-1)
bi = sorted(bi)
b = bi[int(len(bi)/2)]
su = 0
for i in range(len(ai)):
    su += abs(ai[i] - (b+i+1))
print(su)

Submission status: Accepted

Solution code:
from statistics import median

N = int(input())
items = list(map(int, input().split()))
items = [item - (k+1) for k, item in enumerate(items)]
items.sort()
ans = 0
for  i in range(len(items)):
  ans += abs(items[i]-items[N//2])
print(ans)

# n = int(input())
# a = list(map(int, input().split()))
# s = 0
# for i in range(n):
#     a[i] -= (i+1)
 
# a.sort()
# for i in range(n):
#     s += abs(a[i]-a[n//2])
 
# print(s)

Submission status: Accepted

Solution code:
sousuu = int(input())
listnum = list(map(int, input().split()))
_list = []
for i in range(sousuu):
    _list.append(listnum[i] - (1 + i))
num = sorted(_list)[sousuu//2]
dst = 0
for i in range(sousuu):
    dst += abs(listnum[i] - (i+1+num))
print(dst)

Submission status: Accepted

Solution code:
import statistics

n = int(input())
a = []
j = 1
for i in list(map(int, input().split())):
    a.append(i - j)
    j += 1
b = statistics.median((a))
res = 0
for i in range(n):
    res += abs(a[i] - b)

print(int(res))

Submission status: Accepted

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

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

Submission status: Accepted

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
Alist = list(map(int,input().split()))
Blist = []
p = 0
q = 0
r = 0
for i in range(N):
    Blist.append(Alist[i] - i- 1)
Blist.sort()
u = Blist[N//2]
for i in range(N):
    q = q + abs(Blist[i]-u)
print(q)

Submission status: Accepted

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

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

calc.sort()

b = calc[n // 2]

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

print(ans)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
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 == 0:
    c = (b[n//2-1] + b[n//2]) // 2
else:
    c = b[n//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()))
calc = []
for i in range(n):
    calc.append(a[i] - (i + 1))

calc.sort()
b = calc[n // 2]
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 = sorted([int(x) - int(i) for i, x in enumerate(input().split(), 1)])
b = A[n//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()))

def func(b):
    return sum([abs(val - b) for val in I])

#y seppen wo motomeru

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

if N % 2 ==1:
    print(func(I[N//2]))
else:
    print(func(I[N//2]))

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)])
ans = 0
if n%2 == 0:
  b = a[n//2 - 1]
else:
  b = a[n//2]
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(' ')))
ans = float('inf')
l = []
for n,i in enumerate(A):
    l.append(i-n-1)
l = sorted(l)
for i in l[N//2-1:N//2+2]:
    tmp = 0
    for j in l:
        tmp += abs(j-i)
    ans = min(ans,tmp)
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)
median=-1
a.sort()
if n%2==0:
    median=(a[n//2]+a[n//2-1])//2
else:
    median=a[n//2]
def comp(x):
    su=0
    for i in a:
        su+=abs(i-x)
    return su
print(min(comp(median),comp(median+1)))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    a[i]-=(i+1)
median=-1
a.sort()
if n%2==0:
    median=(a[n//2]+a[n//2-1])//2
else:
    median=a[n//2]
def comp(x):
    su=0
    for i in a:
        su+=abs(i-x)
    return su
print(min(comp(median-1),comp(median),comp(median+1)))

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 == 1:
    ans = 0
elif n %  2 == 0:
    m, l = 0, 0
    for i in a:
        m += abs(i - a[n // 2])
        l += abs(i - a[n // 2 - 1])
    ans = min(l, m)
else:
    k, m, l = 0, 0, 0
    for i in a:
        k += abs(i - a[n // 2 - 1])
        m += abs(i - a[n // 2])
        l += abs(i - a[n // 2 + 1])
        ans = min(k, m, l)
print(ans)

Submission status: Accepted

Solution code:
import sys

import bisect

# from collections import Counter, deque, defaultdict
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd

import itertools

# from operator import attrgetter, itemgetter
# import math

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(input())
    a1 = list(map(int, readline().split()))
    a2 = [a1[i] - (i + 1) for i in range(n)]

    a2.sort()

    b = a2[(n - 1) // 2]
    a3 = [abs(a2[i] - b) for i in range(n)]

    print(sum(a3))


if __name__ == '__main__':
    main()

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()
k = A[N//2]
for i in range(N):
    A[i] -= k
    A[i] = abs(A[i])
print(sum(A))

Submission status: Accepted

Solution code:


def solve():
    N = int(input())
    As = list(map(int, input().split()))

    Bs = []

    for i in range(N):
        Bs.append(As[i]-i-1)

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

    ans = 0

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

    print(ans)


# Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import numpy as np
def main():
    N = int(input())
    A = map(int, input().split())
    l = []
    for i, v in enumerate(A):
        l.append(v-i-1)
    x = int(np.median(l))
    y = x + 1
    tx = 0
    ty = 0
    for i in l:
        tx += abs(i-x)
        ty += abs(i-y)
    print(min(ty, tx))
main()

Submission status: Accepted

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

Submission status: Accepted

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

a.sort()
for i in range(n):
    s += abs(a[i]-a[n//2])

print(s)

Submission status: Accepted

Solution code:
# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
import numpy as np
#import statistics
#import sys
#sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline

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

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

    B=abs(A-np.median(A))
    print(int(sum(B)))
resolve()

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
A = np.array(list(map(int, input().split())))
i = np.arange(1, n+1)

X = A - i
med = np.median(X)
ans = np.abs(X - med).sum()
print(int(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.sort()
b = (a[n//2]+a[(n-1)//2])//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 = list(map(int, input().split()))

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

ind_B.sort()
b = ind_B[len(ind_B)//2]

ABS = []
for j in ind_B:
  abs = np.abs(j - b)
  ABS.append(abs)

sum = sum(ABS)
print(sum)

Submission status: Accepted

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

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

Submission status: Accepted

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

def main():
    N = int(input())
    A = map(int, input().split())
    A = sorted([a - i - 1 for i, a in enumerate(A)])

    b = A[N//2]
    print(sum([abs(a - b) for a in A]))

if __name__ == '__main__':
    main()

Submission status: Accepted

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


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

    diff = []

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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

N = int(input().strip())
A_list = list(map(int, input().rstrip().split()))
#-----

temp_A=[]
for i in range(len(A_list)):
    temp_A.append( A_list[i] - (i+1) )

temp_A.sort()
median = (temp_A[(N-1)//2] + temp_A[N//2]) // 2

b = median
sum=0
for i,a in enumerate(A_list):
    sum += abs( a - (b+(i+1)) )

print(sum)

Submission status: Accepted

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

N = int(input().strip())
A_list = list(map(int, input().rstrip().split()))
#-----

temp_A=[]
for i in range(len(A_list)):
    temp_A.append( A_list[i] - (i+1) )

temp_A.sort()
if N%2 == 1:
    median = temp_A[ N//2 ]
else:
    median = (temp_A[ N//2 - 1] + temp_A[ N//2 ]) // 2

b = median
sum=0
for i,a in enumerate(A_list):
    sum += abs( a - (b+(i+1)) )

print(sum)

Submission status: Accepted

Solution code:
import statistics  
N = int(input())
A=list(map(int, input().split()))
B=[]
for number, i in enumerate(A, 1):
    B.append(i-number)
median = round(statistics.median(B))
ans2 = 0
for i in B:
    ans2 += abs(i-median)
print(ans2)

Submission status: Accepted

Solution code:
import statistics  
N = int(input())
A=list(map(int, input().split()))
B=[]
for number, i in enumerate(A, 1):
    B.append(i-number)
median = int(statistics.median(B))
ans2 = 0
for i in B:
    ans2 += abs(i-median)
print(ans2)

Submission status: Accepted

Solution code:
from statistics import median

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

b = int(median([v-i for i, v in enumerate(a, 1)]))
res = 0
for i, v in enumerate(a, 1):
    res += abs(v-(b+i))

print(res)

Submission status: Accepted

Solution code:
import math
import statistics
N = int(input())
L = [i for i in map(int,input().split())]
Q = []
for i in range(len(L)):
  Q.append(L[i] - (i+1))
b = statistics.median(Q)
res = 0
for i in range(N):
  res += abs(L[i] - (i+1) - b)
print(int(res))

Submission status: Accepted

Solution code:
import math
import statistics
N = int(input())
L = [i for i in map(int,input().split())]
Q = []
for i in range(len(L)):
  Q.append(L[i] - (i+1))
b = statistics.median(Q)
a = b - 1
c = b + 1
res = 0
res2 = 0
res3 = 0
for i in range(N):
  res += abs(L[i] - (i+1) - b)
  res2 += abs(L[i] - (i+1) - a)
  res3 += abs(L[i] - (i+1) - c)
print(int(min(res,res2,res3)))

Submission status: Accepted

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

B=[A[i]-(i+1) for i in range(n)]
middle=median(B)

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

print(int(ans))

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
ans=[]
ANS=0
for i in range(N):
  ans.append(A[i]-i-1)
re_ans=sorted(ans)

if N%2==1:
  b=re_ans[N//2]
else:
  b=(re_ans[N//2]+re_ans[N//2-1])/2
for j in range(N):
  ANS+=abs(A[j]-b-j-1)
print(int(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()
mid = A[(N + 2 - 1) // 2 - 1]
ans = 0
for a in A:
    ans += abs(a - mid)

print(ans)