Problem:


Score : 300 points

Problem Statement

Snuke has an integer sequence A of length N.

He will freely choose an integer b.
Here, he will get sad if A_i and b+i are far from each other.
More specifically, the sadness of Snuke is calculated as follows:

abs(A_1 - (b+1)) + abs(A_2 - (b+2)) + ... + abs(A_N - (b+N))

Here, abs(x) is a function that returns the absolute value of x.

Find the minimum possible sadness of Snuke.

Constraints

1 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the minimum possible sadness of Snuke.

Sample Input 1

5
2 2 3 5 5

Sample Output 1

2

If we choose b=0, the sadness of Snuke would be abs(2-(0+1))+abs(2-(0+2))+abs(3-(0+3))+abs(5-(0+4))+abs(5-(0+5))=2.
Any choice of b does not make the sadness of Snuke less than 2, so the answer is 2.

Sample Input 2

9
1 2 3 4 5 6 7 8 9

Sample Output 2

0

Sample Input 3

6
6 5 4 3 2 1

Sample Output 3

18

Sample Input 4

7
1 1 1 1 2 3 4

Sample Output 4

6



Sample input:
5
2 2 3 5 5


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
a = np.array([int(x) for x in input().split()])
for i in range(n):
  a[i] -= i+1
a.sort()

sum_0 = np.sum(np.abs(a-a[0]))
sum_n = np.sum(np.abs(a-a[-1]))

l, r = n//3, n*2//3

while r-l > 1:
  sum_l = np.sum(np.abs(a-a[l]))
  sum_r = np.sum(np.abs(a-a[r]))
  if sum_l < sum_r:
    if sum_r > sum_0:
      r = l
      l = l//2
    else:
      l = (r+l)//2
      sum_0 = sum_l
  else:
    if sum_l > sum_n:
      l = r
      r = (r+n)//2
    else:
      r = (r+l)//2
      sum_n = sum_r

print(min([np.sum(np.abs(a-a[l])), np.sum(np.abs(a-a[r]))]))

Submission status: Time Limit Exceeded

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

for i in range(n):
    lists[i]-=(i+1)
mini=10**100
for k in range(-10**9,10**9):
    sub=0
    for _ in range(n):
        sub+=abs(lists[_]-k)
    mini=min(mini,sub)
           
print(mini)

Submission status: Time Limit Exceeded

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

B.sort()
ans=float('inf')
for i in range(B[0],B[N-1]+1):
  val=0
  for j in range(N):
    val+=abs(B[j]-i)
  ans=min(ans,val)
print(ans)

Submission status: Time Limit Exceeded

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

#y seppen wo motomeru

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

m=min(I)
M=max(I)

opp=10**100
for i in range(m, M+1):
    #print(i)
    temp=sum([abs(val-i) for val in I])
    if temp<opp:
        opp=temp
print(opp)

Submission status: Time Limit Exceeded

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

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


    val=0
    for i in A:
        val += abs(i - statistics.median(A))
    print(int(val))
resolve()

Submission status: Time Limit Exceeded

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 sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline

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

    B=np.array([i for i in range(1,N+1)])

    A=A-B
    val=0
    for i in A:
        val += abs(i - np.median(A))
    print(int(val))
resolve()

Submission status: Time Limit Exceeded

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 sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline

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


    val1 = 0
    val2=0
    for i in A:
        val1 += abs(i - 1)
        val2+=abs(i+1)
    if val1<val2:

        minval = 10 ** 50
        j=0
        temp = 10**50
        while True:
            val=0
            for i in A:
                val+=abs(i-j)
            if val>=temp:
                break
            else:
                temp=val
                minval=min(minval,val)
                j+=1

    else:

        minval = 10 ** 50
        j=0
        temp = 10**50
        while True:
            val=0
            for i in A:
                val+=abs(i+j)
            if val>=temp:
                break
            else:
                temp=val
                minval=min(minval,val)
                j+=1
    print(minval)
resolve()

Submission status: Time Limit Exceeded

Solution code:

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

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

    val1 = 0
    val2=0
    for i in A:
        val1 += abs(i - 1)
        val2+=abs(i+1)
    if val1<val2:

        minval = 10 ** 50
        j=0
        temp = 10**50
        while True:
            val=0
            for i in A:
                val+=abs(i-j)
            if val>=temp:
                break
            else:
                temp=val
                minval=min(minval,val)
                j+=1

    else:

        minval = 10 ** 50
        j=0
        temp = 10**50
        while True:
            val=0
            for i in A:
                val+=abs(i+j)
            if val>=temp:
                break
            else:
                temp=val
                minval=min(minval,val)
                j+=1
    print(minval)
resolve()

Submission status: Time Limit Exceeded

Solution code:

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

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

    minval = 10 ** 50
    j=0
    temp = 10**50
    while True:
        val=0
        for i in A:
            val+=abs(i-j)
        if val>=temp:
            break
        else:
            temp=val
            minval=min(minval,val)
            j+=1

    minval = 10 ** 50
    j=0
    temp = 10**50
    while True:
        val=0
        for i in A:
            val+=abs(i+j)
        if val>=temp:
            break
        else:
            temp=val
            minval=min(minval,val)
            j+=1
    print(minval)
resolve()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

a,b=min(l),max(l)

y=[]
for j in range(a,b+1):
    x=0
    for k in range(n):
        #print(abs(l[k]-j))
        x+=abs(l[k]-j)
    y.append(x)
    #print(x)

#print(n,l,y)
print(min(y))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

ARR = [int(s) for s in input().split(" ")]

import math
import numpy as np

def calculate(n,arr):
    srr = np.array([arr - index - 1 for index,arr in enumerate(arr)])

    maxValue = max(srr)
    minValue = min(srr)

    if maxValue * minValue < 0:
        if math.fabs(maxValue) > math.fabs(minValue):
            pinyizuidaxiang =  int(math.fabs(maxValue))
        else:
            pinyizuidaxiang = int(math.fabs(minValue))
    elif maxValue * minValue > 0:
        pinyizuidaxiang = int(math.fabs(maxValue))
    else:
        if math.fabs(maxValue) != 0:
            pinyizuidaxiang = int(math.fabs(maxValue))
        if math.fabs(minValue) != 0:
            pinyizuidaxiang = int(math.fabs(minValue))
        if (math.fabs(maxValue) == 0)  and (math.fabs(minValue) == 0):
            pinyizuidaxiang = 0


    minest = []

    if pinyizuidaxiang == 0:
        return sum(srr)

    for i in range(-pinyizuidaxiang,pinyizuidaxiang):
        minest.append(sum(np.fabs(srr - i)))

    return int(min(minest))

result = calculate(N,ARR)
print(result)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

ARR = [int(s) for s in input().split(" ")]

import math

def calculate(n,arr):
    srr = [arr - index - 1 for index,arr in enumerate(arr)]

    maxValue = max(srr)
    minValue = min(srr)

    if maxValue * minValue < 0:
        if math.fabs(maxValue) > math.fabs(minValue):
            pinyizuidaxiang =  int(math.fabs(maxValue))
        else:
            pinyizuidaxiang = int(math.fabs(minValue))
    elif maxValue * minValue > 0:
        pinyizuidaxiang = int(math.fabs(maxValue))
    else:
        if math.fabs(maxValue) != 0:
            pinyizuidaxiang = int(math.fabs(maxValue))
        if math.fabs(minValue) != 0:
            pinyizuidaxiang = int(math.fabs(minValue))
        if (math.fabs(maxValue) == 0)  and (math.fabs(minValue) == 0):
            pinyizuidaxiang = 0


    minest = []

    if pinyizuidaxiang == 0:
        return sum(srr)

    for i in range(-pinyizuidaxiang,pinyizuidaxiang):
        minest.append(sum([math.fabs(sr -i) for sr in srr]))

    return int(min(minest))

result = calculate(N,ARR)
print(result)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

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

s=[a[0]]
for i in range(1,n):
    s.append(s[i-1]+a[i])
    
bmin=min(a)-n
bmax=max(a)+n
  
asmin=bmax*n
#m0=0
m1=bisect.bisect(a,bmin)
for b in range(bmin,bmax+1):
    while m1<n and a[m1]<b:
        m1=m1+1
    m=m1
#    m=bisect.bisect(a,b)
    if m<=0:
        asf=-n*b+s[n-1]
    elif m<n:
        asf=(2*m-n)*b+s[n-1]-2*s[m-1]
    elif n<=m:
        asf=n*b-s[n-1]
        
#    print("b",b,"m",m,"asf",asf)
    if asf<asmin:
        asmin=asf

print(asmin)

Submission status: Time Limit Exceeded

Solution code:
import bisect

a=[]
def asff(b,a,n):
    asum=0
    for j in range(n):
        asum=asum+abs(a[j]-(b+j+1))
    return asum    

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

#n=5
#stra="2 2 3 5 5"
#ans=2

#n=9
#stra="1 2 3 4 5 6 7 8 9"
#ans=0

#n=6
#stra="6 5 4 3 2 1"
#ans=18

#n=7
#stra="1 1 1 1 2 3 4"
#ans=6

#a=list(map(int,stra.split()))

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

s=[a[0]]
for i in range(1,n):
    s.append(s[i-1]+a[i])
    
bmin=min(a)-n
bmax=max(a)+n

  
asmin=bmax*n
m0=0
for b in range(bmin,bmax+1):
    m=bisect.bisect(a,b)
    if m<=0:
        asf=-n*b+s[n-1]
    elif m<n:
        asf=(2*m-n)*b+s[n-1]-2*s[m-1]
    elif n<=m:
        asf=n*b-s[n-1]
        
#    print("b",b,"m",m,"asf",asf)
    if asf<asmin:
        asmin=asf

print(asmin)

Submission status: Time Limit Exceeded

Solution code:
a=[]
def asff(b,a,n):
    asum=0
    for j in range(n):
        asum=asum+abs(a[j]-(b+j+1))
    return asum    

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

amin=min(a)-n
amax=max(a)+n

#asmin=amax*n
#for i in range(amin,amax+1):
#    asf=asff(i,a,n)
#    if asf<asmin:
#        asmin=asf

ast=min(a)-n
aed=max(a)+n
asst=asff(ast,a,n)
ased=asff(aed,a,n)

icnt=0
while ast+1<=aed:    
    amed=(ast+aed)//2
    if asst>ased:
        ast=amed
        asst=asff(ast,a,n)
    else:
        aed=amed
        ased=asff(aed,a,n)
    icnt=icnt+1
    if icnt>10000:
        break              
    
print(ased)

Submission status: Time Limit Exceeded

Solution code:
a=[]
def asff(b,a,n):
    asum=0
    for j in range(n):
        asum=asum+abs(a[j]-(b+j+1))
    return asum    

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

amin=min(a)-n
amax=max(a)+n

asmin=amax*n
for i in range(amin,amax+1):
    asf=asff(i,a,n)
    if asf<asmin:
        asmin=asf
            
print(asmin)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = list(map(int,input().split()))
l = list(l[i]-i for i in range(n))
m = 10**15
for i in set(l):
  m = min(m,sum(abs(j-i) for j in l))
print(m)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = list(map(int,input().split()))
l = list(l[i]-i for i in range(n))
m = 10**15
for i in range(min(l),max(l)+1):
  m = min(m,sum(abs(j-i) for j in l))
print(m)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
def quick_sort(a):
    if len(a)<= 1:
        return a
    else:
        b=[]
        c=[]
        for i in range(1, len(a)):
            if a[i]<a[0]:
                b.append(a[i])
            else:
                c.append(a[i])
        return quick_sort(b)+[a[0]]+quick_sort(c)
def abs(x):
    if x>=0:
        return x
    else:
        return x*(-1)
B=[]
for i in range(N):
  B.append(A[i]-i-1)
C=quick_sort(B)
if N%2==0:
  b=(C[N//2]+C[N//2-1])//2
else:
  b=C[N//2-1]
sad=0
for j in range(N):
  sad=sad+abs(C[j]-b)
print(sad)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
def quick_sort(a):
    if len(a)<= 1:
        return a
    else:
        b=[]
        c=[]
        for i in range(1, len(a)):
            if a[i]<a[0]:
                b.append(a[i])
            else:
                c.append(a[i])
        return quick_sort(b)+[a[0]]+quick_sort(c)
def abs(x):
    if x>=0:
        return x
    else:
        return x*(-1)
B=[0]*N
for i in range(N):
  B[i]=A[i]-i-1
C=quick_sort(B)
if N%2==0:
  b=(C[N//2]+C[N//2-1])//2
else:
  b=C[N//2-1]
sad=0
for j in range(N):
  sad=sad+abs(C[j]-b)
print(sad)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
def quick_sort(a):
    if len(a)<= 1:
        return a
    else:
        b=[]
        c=[]
        for i in range(1, len(a)):
            if a[i]<a[0]:
                b.append(a[i])
            else:
                c.append(a[i])
        return quick_sort(b)+[a[0]]+quick_sort(c)
def abs(x):
    if x>=0:
        return x
    else:
        return x*(-1)
B=[0]*N
for j in range(N):
    B[j]=A[j]-j-1
bh=quick_sort(B)[0]
bt=quick_sort(B)[N-1]
def sad(A,b):
  s=[0]*(len(A))
  for m in range(len(A)):
    s[m]=abs(A[m]-(b+m+1))
  return s
def sum(A):
  sum=0
  for n in range(len(A)):
    sum=sum+A[n]
  return sum
l=[]
for o in range(bh-5,bt+5):
  l.append(sum(sad(A,o)))
print(quick_sort(l)[0])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
def abs(x):
    if x>=0:
        return x
    else:
        return x*(-1)
B=[0]*N
for j in range(N):
    B[j]=A[j]-j-1
max=B[0]
min=B[0]
for k in range(len(B)):
  if max<=B[k]:
    max=B[k]
bt=max
for k in range(len(B)):
  if min>=B[k]:
    min=B[k]
bh=min
def sad(A,b):
  s=[0]*(len(A))
  for m in range(len(A)):
    s[m]=abs(A[m]-(b+m+1))
  return s
def sum(A):
  sum=0
  for n in range(len(A)):
    sum=sum+A[n]
  return sum
l=[]
for o in range(bh-5,bt+5):
  l.append(sum(sad(A,o)))
def quick_sort(a):
    if len(a) <= 1:
        return a
    else:
        b = []
        c = []
        for i in range(1, len(a)):
            if a[i] < a[0]:
                b.append(a[i])
            else:
                c.append(a[i])
        return quick_sort(b)+[a[0]]+quick_sort(c)
print(quick_sort(l)[0])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
def abs(x):
    if x>=0:
        return x
    else:
        return x*(-1)
B=[0]*N
for j in range(N):
    B[j]=A[j]-j-1
max=B[0]
min=B[0]
for k in range(len(B)):
  if max<=B[k]:
    max=B[k]
bt=max
for k in range(len(B)):
  if min>=B[k]:
    min=B[k]
bh=min
def sad(A,b):
  s=[0]*(len(A))
  for m in range(len(A)):
    s[m]=abs(A[m]-(b+m+1))
  return s
def sum(A):
  sum=0
  for n in range(len(A)):
    sum=sum+A[n]
  return sum
l=[]
for o in range(bh-5,bt+5):
  l.append(sum(sad(A,o)))
mini=l[0]
for p in range(bt-bh+10):
  if mini>=l[p]:
    mini=l[p]
print(mini)

Submission status: Time Limit Exceeded

Solution code:
num = int(input())
i = list(map(int, input().split())) 
#b=min(i)-num
#b=max(i)-1

b=min(i)-num
mini = float('inf')
while(b!=max(i)):
  sum=0
  for j  in range(num):
     sum+=abs(i[j]-(b+j+1))
  mini = min(sum,mini)
  b+=1
  
print(mini)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a=list(map(int,input().split()))
max=a[0]
b=0
k=0

for i in range(N):
  if a[i]>max:
    max=a[i]
    k=i

answer=max*N

for i in range(max-k):
  for k in range(N):
    b+=abs(a[k]-(k+1)-i)
  if b<answer:
    answer=b
  b=0
  
for i in range(max):
  for k in range(N):
    b+=abs(a[k]-(k+1)+i)
  if b<answer:
    answer=b
  b=0
  
  
print(answer)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a=list(map(int,input().split()))
max=a[0]
b=0

for i in range(N):
  if a[i]>max:
    max=a[i]

answer=max*N

for i in range(max):
  for k in range(N):
    b+=abs(a[k]-(k+1)-i)
  if b<answer:
    answer=b
  b=0
  
for i in range(max):
  for k in range(N):
    b+=abs(a[k]-(k+1)+i)
  if b<answer:
    answer=b
  b=0
  
  
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

import numpy as np

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

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def tleft(fn, lo, hi):
    """
    fn の結果が最も小さくなるインデックスを三分探索する
    :param callable fn:
    :param int lo: 最小のインデックス
    :param int hi: 最大のインデックス + 1
    :return: lo <= ret < hi
    """
    left = lo
    right = hi
    while abs(right - left) >= 3:
        r1 = (left * 2 + right) // 3
        r2 = (left + right * 2) // 3
        if fn(r1) <= fn(r2):
            right = r2
        else:
            left = r1
    if left + 1 >= hi or fn(left) <= fn(left + 1):
        return left
    if left + 2 >= hi or fn(left + 1) <= fn(left + 2):
        return left + 1
    return left + 2


def cost(n):
    return np.abs(A - (np.arange(N) + n)).sum()


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

i = tleft(cost, int(-1e10), int(1e10))
ans = int(cost(i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
L = list(map(int,input().split()))
for i in range(n):
    L[i] = L[i]-(i+1)
sum1 = 0
b = max(abs(max(L)),abs(min(L)))
i = -b
min1 = 10**10
while i<=b:
    sum1 =0
    for j in range(n):
        sum1 += abs(L[j]-i)
    min1 = min(min1,sum1)
    i +=1
print(min1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
def sad(b):
    ret = 0
    for i in range(N):
        ret += abs(A[i]-b-i)
    return ret
L = -(10**10)
R = 10**10
tmp = sad(R)
while L+1<R:
    mid = (L+R)//2
    sm = sad(mid)
    sm1 = sad(mid-1)
    if sm1 < sm:
        R = mid
    elif sm1 == sm:
        ans = sm
        break
    else:
        L = mid
else:
    ans = sad(L)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def func(li,b) :
    sum = 0
    for i in range(len(li)) :
        sum+= abs(li[i] - b - i - 1)
    return sum
def binary_search(li) :
    left = -1000000001
    right = 1000000001
    while right - left > 1 :
        med = (right + left) // 2
        x = func(li,med)
        mdx = func(li,med-1)
        pdx = func(li,med+1)
        if mdx > x and pdx < x :
            left = med
            continue
        elif mdx < x and pdx > x :
            right = med
            continue
        elif mdx >= x and pdx >= x :
            return x
    else :
        return -1
import sys
input = sys.stdin.readline
N = int(input())
A =[int(i) for i in input().split()]
print(binary_search(A))

Submission status: Time Limit Exceeded

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

d = 0
c = []
for b in range(-max(a),min(a)+1):
    for i in range(0,len(a)):
        d += abs(a[i]-(b+i+1))
    c.append(d)
    d = 0
print(min(c))

Submission status: Time Limit Exceeded

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

d = 0
c = []
for b in range(-max(a),max(a)+1):
    for i in range(0,len(a)):
        d += abs(a[i]-(b+i+1))
    c.append(d)
    d = 0
print(min(c))

Submission status: Time Limit Exceeded

Solution code:
from statistics import median
N = int(input())
A = list(map(int, input().split()))
B = list()
sad = 0

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

  b = median(B)

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

print(int(sad))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
B = sorted([A[i]-i for i in range(N)])
# return -A[0]-...-A[k-1]+A[k]+...+A[N-1]
def partial_sum(k):
    return -sum(B[:k]) + sum(B[k:])

l = [partial_sum(i) -(N-2*i)*B[i] for i in range(N)]
print(min(l))

Submission status: Time Limit Exceeded

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

def check(m):
    sm = 0
    for i, a in enumerate(A):
        sm += abs(a - (m+i+1))
    return sm

# 三分探索
low = -INF
hi = INF
while low+2 < hi:
    m1 = (low*2+hi) // 3
    m2 = (low+hi*2) // 3
    res1 = check(m1)
    res2 = check(m2)
    # 今回は下に凸な関数なので値の小さい方に向かって狭めていく
    if res1 <= res2:
        hi = m2
    else:
        low = m1

ans = INF
for i in range(low, low+2):
    ans = min(ans, check(i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=a[0]-1
ans=0
ansl=0
ansr=0
for i in range(n):
    ans+=abs(a[i]-b-i-1)
    ansl+=abs(a[i]-b-i)
    ansr+=abs(a[i]-b-i-2)
    
A=[10**10,ans] 
if ans>ansl:
    b-=1
    A.append(ansl)
    while A[-1]<A[-2]:
        ans=0
        b-=1
        for i in range(n):
            ans+=abs(a[i]-b-i-1)
        A.append(ans) 
elif ans>ansr:
    b+=1
    A.append(ansr)
    while A[-1]<A[-2]:
        ans=0
        b+=1
        for i in range(n):
            ans+=abs(a[i]-b-i-1)
        A.append(ans)
else:
    print(ans)
    exit()
print(A[-2])

Submission status: Time Limit Exceeded

Solution code:
import copy

def get_diff(value, array):
  diff = 0
  for i in array:
    diff += abs(value - i)
  return diff

length = int(input())
inp = input().split(' ')
A = []
for i in range(0, length):
  A.append(int(inp[i]) - i - 1)

initial = int(sum(A)/len(A))
initial_diff = int(get_diff(initial, A))

end_flag = 1
initial_plus = copy.copy(initial)
max_diff = copy.copy(initial_diff)
# print(A)
# print(initial)
# print(initial_diff)

while end_flag == 1:
  initial_plus += 1
  if get_diff(initial_plus, A) < max_diff:
    max_diff = get_diff(initial_plus, A)
    print(max_diff)
  else:
    end_flag = 0

plus_max_diff = max_diff

end_flag = 1
initial_plus = copy.copy(initial)
max_diff = copy.copy(initial_diff)

while end_flag == 1:
  initial_plus -= 1
  if get_diff(initial_plus, A) < max_diff:
    max_diff = get_diff(initial_plus, A)
  else:
    end_flag = 0
    
minus_max_diff = max_diff

print(min(plus_max_diff, initial_diff, minus_max_diff))

Submission status: Time Limit Exceeded

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

def solve(N: int, A: "List[int]"):
    A = np.array(A)
    i_ = np.array(list(range(1, N + 1)))
    ans_set = set(A - i_)

    def get_sadness(b, A=A, i_=i_):
        return sum(abs(A - i_ - b))

    sadness = [0]*len(ans_set)
    for i, b in enumerate(ans_set):
        sadness[i] = get_sadness(b=b)

    ans = sadness[np.argsort(sadness)[0]]
    print(ans)

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]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


ave = sum(al) // len(al)
start = ave
ans = float("inf")
while True:
    tmp = 0
    for idx, a in enumerate(al):
        tmp += abs(start+ idx - a)
    if ans >= tmp:
        ans = tmp
    else:
        break
    start += 1

start = ave
while True:
    tmp = 0
    for idx, a in enumerate(al):
        tmp += abs(start +idx - a)
    if ans >= tmp:
        ans = tmp
    else:
        break
    start -= 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[int(x) for x in input().split()]
def ka(b):
  k=0
  for i in range(N):
    k += abs(A[i]-(b+i+1))
  return k
answer = float('inf')
for j in range(-max(A)*2,max(A)*2):
  answer = min(answer,ka(j))
print(answer)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from itertools import accumulate
import bisect

n = int(stdin.readline().rstrip())
li = list(map(int,stdin.readline().rstrip().split()))
lin = [i+1 for i in range(n)]
point = 0
ls = []
ls.sort()
for i in range(n):
    ls.append(li[i]-lin[i])
ls.sort()
mi = 10**6
for i in ls:
    lin = 0
    for j in range(n):
        lin += abs(ls[j]-i)
    mi = min(lin,mi)

print(mi)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[int(x) for x in input().split()]
s=[0 for x in range(n)]
 
for i in range(n):
  a[i] -= i+1
 
a.sort()
 
if n%2:
  s=0
  for i in range(n):
    s += abs(a[i]-a[n//2])
  print(s)
else:
  m=10**14
  for i in range(a[n//2-1],a[n//2]+1):
    s = 0
    for j in range(n):
      s += abs(a[j]-i)
    m = min(m,s)
  print(m)

Submission status: Time Limit Exceeded

Solution code:
import bisect

n=int(input())
a=[int(x) for x in input().split()]
s=[0 for x in range(n)]

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

a.sort()

s=0
if s%2:
  for i in range(n):
    s += abs(a[i]-a[n//2])
  print(s)
else:
  m=10**14
  for i in range(a[n//2-1], a[n//2]+1):
    s = 0
    for j in range(n):
      s += abs(a[j]-i)
    m = min(m,s)
  print(s)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
a_c = a
for i in range(n):
    a_c[i] -= i
min_a_c = min(a_c)
max_a_c = max(a_c)
scores = []
for j in range(min_a_c, max_a_c + 1):
    tmp_score = 0
    for i in range(n):
        tmp_score += abs(a_c[i] - j)
    scores.append(tmp_score)
print(min(scores))

Submission status: Time Limit Exceeded

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

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

st = min(arr); end = max(arr)

mn_sd = float("inf")
for i in range(st, end+1):
	total = 0
	for ele in arr:
		total += abs(ele - i) 
	mn_sd = min(mn_sd, total)
print(mn_sd)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [A[i] - i - 1 for i in range(N)]
cost = lambda x : sum([abs(b - x) for b in B])
right = max(B)
right_cost = cost(right)
left = min(B)
left_cost = cost(left)
step = (right - left) // 2
while step > 0:
  R = range(left + step, right, step)
  for x in R:
    x_cost = cost(x)
    if x_cost < left_cost:
      left = x
      left_cost = x_cost
    else:
      right = x
      right_cost = x_cost
      continue
  step = step // 2
print(left_cost)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [A[i] - i - 1 for i in range(N)]
cost = lambda x : sum([abs(b - x) for b in B])
right = max(B)
right_cost = cost(right)
left = min(B)
left_cost = cost(left)
step = (right - left) // 2
while step > 0:
  R = range(left + step, right, step)
  for x in R:
    x_cost = cost(x)
    if x_cost < left_cost:
      left = x
      left_cost = x_cost
    else:
      right = x
      right_cost = x_cost
  step = step // 2
print(left_cost)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
l=list(map(int,input().split()))
max_n=max(l)
min_n=min(l)
res=float('inf')
for j in range(max_n-min_n+N+1):
  ans=0
  for i in range(N):
    ans+=abs(max_n+i-l[i]-j)
  if res > ans:
    res = ans
print(res)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
a = [aa-i-1 for i, aa in enumerate(a)]
answer = 100000000
for b in range(min(a), max(a)+1):
  res = 0
  for aa in a:
    res += abs(aa-b)
  answer = min(answer,res)
print(answer)

Submission status: Time Limit Exceeded

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

def f(b):
    r = 0
    for i, ai in enumerate(A):
        r += abs(ai - (b + i + 1))
    return r

mx = (10 ** 9) + 1
mn = (-10 ** 9) - 1

# print(f(0))
while mx - mn > 10:
    m = (mx + mn) // 2
    x = f(m)
    y = f(m+1)
    if x < y:
        mx = m + 1
    else:
        mn = m


ans = []
for i in range(mn, mx+1):
    ans.append(f(i))
print(min(ans))

Submission status: Time Limit Exceeded

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

def f(b):
    r = 0
    for i, ai in enumerate(A):
        r += abs(ai - (b + i + 1))
    return r

mx = (10 ** 9) + 1
mn = (-10 ** 9) - 1

# print(f(0))
while mx - mn > 2:
    m = (mx + mn) // 2
    x = f(m)
    y = f(m+1)
    if x < y:
        mx = m + 1
    else:
        mn = m


ans = []
for i in range(mn, mx+1):
    ans.append(f(i))
print(min(ans))

Submission status: Time Limit Exceeded

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

def f(b):
    r = 0
    for i, ai in enumerate(A):
        r += abs(ai - (b + i + 1))
    return r

mx = 10 ** 10
mn = -10 ** 10

# print(f(0))
while mx - mn > 2:
    m = (mx + mn) // 2
    x = f(m)
    y = f(m+1)
    if x < y:
        mx = m + 1
    else:
        mn = m


ans = []
for i in range(mn, mx+1):
    ans.append(f(i))
print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
Data = []
def diff(b):
    sum1 = 0
    for d in Data:
        sum1 += abs(b-d)
    return sum1

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

ans = 10**20
for d in Data:
    ans = min(ans,diff(d))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
N = int(input())
A = input().split()

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

#print(A)

result = []

saisho = min(-max(A), min(A))

final = 10000000000

for i in range(saisho, max(A)+1):
    sum = 0
    for j in range(len(A)):
        sum += abs(A[j] - i)
    #print(sum)
    result.append(sum)
    if (final > min(result)):
        final = min(result)
    else:
        pass

print(final)

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
N = int(input())
A = input().split()

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

#print(A)

result = []

saisho = min(-max(A), min(A))

for i in range(saisho, max(A)+1):
    sum = 0
    for j in range(len(A)):
        sum += abs(A[j] - i)
    #print(sum)
    result.append(sum)

print(min(result))