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
m = int(input())
a = list( map( int, input().split() ) )
maxa = max(a)
na = np.array(a)
nb = np.arange(0,m)
for i in range(-maxa,maxa):
  nb_i = nb + i
  na_i = na - nb_i
  na_i_a = np.abs(na_i)
  temp = np.sum(na_i_a)
  if i == -maxa:
    res = temp
  elif res > temp:
    res = temp
print(res)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
max = max(A)
list = []
x = 0
for b in range(-max,max):
    for i in range(N):
        x = x + abs(A[i]-(b+i))
    list.append(x)
    x = 0
print(min(list))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# AtCoder Beginner Contest


if __name__ == '__main__':
    from statistics import median

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

    # See:
    # https://www.youtube.com/watch?v=UX4AuiCVtN4
    # https://beta.atcoder.jp/contests/abc102/submissions/2768315
    mod_a = sorted([ai - i for i, ai in enumerate(a, 1)])

    for i in range(n):
        total += abs(mod_a[i] - median(mod_a))

    print(int(total))

Submission status: Time Limit Exceeded

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

ans = float("inf")
for b in range(min(A), max(A)+1):
    loss = sum([abs(A[i] - b) for i in range(N)])
    ans = min(ans, loss)


print(ans)

Submission status: Time Limit Exceeded

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

ans = float("inf")
for b in range(min(A), max(A)+1):
    loss = sum([abs(A[i] - b) for i in range(N)])
    if ans > loss:
        ans = loss


print(ans)

Submission status: Time Limit Exceeded

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

i = 0
kari =[]
for j in A:
    i +=1
    B = j-i
    kari.append(B)

sum = 0
for i in kari:
    sum+=abs(i-statistics.median(kari))
print(int(sum))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
li = input().rstrip().split()

le =[0]*N
le2 = [0]*N

for i in range(0,N):
    le[i]=int(li[i])

for i in range(0,N):
    le2[i]=le[i]-i-1
    le2.sort()

b = le2[int(N/2)]
sum = 0
for i in range(0,N):
    sum = sum + abs(le[i]-i-1-b)

print(sum)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
tmp = input().split(' ')

A = []
for i in range(N):
    A.append(int(tmp[i]))

A = np.asarray(A)

z = np.asarray([x for x in range(N)])
A = A - z

ans = np.inf
for b in A:
    tmp = A - b
    tmp = np.absolute(tmp)
    tmp = tmp.sum()
    if ans > tmp:
        ans = tmp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
A_sub_list = [a - (i + 1) for i, a in enumerate(A_list)]
b_max = max(A_sub_list)
b_min = min(A_sub_list)
min_s = pow(10, 10)
for b in range(b_min, b_max + 1):
    s = sum([abs(a - b) for a in A_sub_list])
    min_s = min(min_s, s)
print(min_s)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(s)-i-1 for i, s in enumerate(input().split())]

ans = -1
for b in A:
    sum = 0
    for a in A:
        sum += abs(a-b)
    if ans == -1 or ans > sum:
        ans = sum

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
N=int(input())
li = list(map(int,input().split()))

for i in range(0,N):
	li[i] = li[i] - i -1
a = []
d = copy.copy(li)
while len(d) >= 3:
	d.remove(max(d))
	d.remove(min(d))
for i in range(min(d),max(d)+1):
	k = 0
	for j in range(N):
		k = k + abs(li[j]-i)
	a.append(k)
print(min(a))

Submission status: Time Limit Exceeded

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

for i in range(0,N):
	li[i] = li[i] - i -1
a = []
for i in range(min(li),max(li)+1):
	k = 0
	for j in range(0,N):
		k = k + abs(li[j]-i)
	a.append(k)
print(min(a))

Submission status: Time Limit Exceeded

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

ans = float("inf")
b = -100
while True:
    sad = 0
    for i in range(1, N+1):
        sad += abs(A[i-1] - (b + i))
    if sad <= ans:
        ans = sad
    else:
        break
    b += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def sadden_value(a, b):
    total = 0
    for i in range(0, len(a)):
        total += abs(a[i]-b-i-1)
    return total

n = int(input())
a = list(map(int, input().split()))
b = 1 - n
now = sadden_value(a, b)
while True:
    nex = sadden_value(a, b + 1)
    if now <= nex:
        print(now)
        break
    now = nex
    b += 1

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(_) for _ in input().split()]
i = 1
result = 0
result2=[]
for b in range(abs(max(a))*-1,abs(max(a))):
  for data in a:
    result = result + abs(data - b -i)
    i += 1
  result2.append(result)
  result = 0
  i = 0

print(min(result2))

Submission status: Time Limit Exceeded

Solution code:
def main6():
    buf = int(input(""));
    strbuf = input("");
    strbufs = strbuf.split();
    buf2 = []
    saisyo = 100000000;
    for i in range(buf):
        buf2.append((int(strbufs[i])-(i+1)));
    maxi = max(buf2);
    mini = min(buf2);

    for i in range(mini,maxi+1):
        kari = 0
        for j in range(buf):
            kari = kari + abs(buf2[j]-i);
        if kari < saisyo:
            saisyo = kari;

    print(saisyo);





if __name__ == '__main__':
    main6()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
listNums = list(map(int,input().split()))
listSadness = []
b = 0
c = 1000000000
for b in range(min(listNums) - N, max(listNums) + N):
    for i in range(len(listNums)):
        listSadness.append(abs(listNums[i] - (b + 1 + i)))
    if sum(listSadness) < c:
        c = sum(listSadness)
    listSadness = []
print(c)

Submission status: Time Limit Exceeded

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

A_sunuke = [a - (i+1) for (i,a) in enumerate(A)]

sunuke_cnts = set(A_sunuke) 

idx, cnt = 0, 0
for i in sunuke_cnts:
    a_cnt = A_sunuke.count(i)
    if cnt < a_cnt:
        cnt = a_cnt
        idx = i 

rtn = sum([abs(a - idx) for a in A_sunuke])
print(rtn)

Submission status: Time Limit Exceeded

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

pro_list = [a_list[i-1] - i for i in range(1, n+1)]
ave = int(statistics.mean(pro_list))

b_list = [ave - 1 for i in range(5000)] + [ave + i for i in range(5000)]

ans = [sum([abs(pro-b)for pro in pro_list]) for b in b_list]
print(min(ans))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def calc_sad_param(b):
    global numbers
    sad_param = 0
    for i in range(len(numbers)):
        sad_param += abs(numbers[i] - (b + i))
    return sad_param

n = int(input())
numbers = list(map(int, input().split()))
sad_params = []
for b in range(-sorted(numbers)[-1], sorted(numbers)[-1]):
    sad_params.append(calc_sad_param(b))

sad_params.sort()

print(sad_params[0])

Submission status: Time Limit Exceeded

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

S = {}
def sadness(b):
    if not b in S.keys():
        f = lambda x: abs(x-b)
        S[b] = sum(map(f, A2))
    return S[b]

x3 = max(A2)
x0 = min(A2)

while(True):
    w = (x3 - x0) / 3

    if w < 1:
        print(min([sadness(i) for i in range(x0, x3+1)]))
        break

    x1 = int(x0 + w)
    x2 = int(x0 + w * 2)
    #print(x0, x1, x2, x3)

    s1 = sadness(x1)
    s2 = sadness(x2)
    if s1 > s2:
        x0 = x1
    else:
        x3 = x2

Submission status: Time Limit Exceeded

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

def sadness(b):
    f = lambda x: abs(x-b)
    return sum(map(f, A2))

x3 = max(A2)
x0 = min(A2)

while(True):
    w = (x3 - x0) / 3

    if w < 1:
        print(min([sadness(i) for i in range(x0, x3+1)]))
        break

    x1 = int(x0 + w)
    x2 = int(x0 + w * 2)
    #print(x0, x1, x2, x3)

    s1 = sadness(x1)
    s2 = sadness(x2)
    if s1 > s2:
        x0 = x1
    else:
        x3 = x2

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    N = int(raw_input())
    list_A = map(int, raw_input().split(' '))
    list_A = sorted([list_A[i]-(i+1) for i in range(N)])

    original_b = (list_A[0] + list_A[-1])/2
    b = original_b
    min_sum = sys.maxint

    # search for b++
    while True:
        sum = 0
        for e in list_A:
            sum += abs(e - b)
        if min_sum > sum:
            min_sum = sum
            b += 1
        else:
            break

    # search for b--
    b = original_b-1
    while True:
        sum = 0
        for e in list_A:
            sum += abs(e - b)
        if min_sum > sum:
            min_sum = sum
            b -= 1
        else:
            break
    
    print min_sum

main()

Submission status: Time Limit Exceeded

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

p = [v - (i + 1) for i, v in enumerate(A)]

res = sum(map(abs, [i - statistics.median(p) for i in p]))
print(int(res))

Submission status: Time Limit Exceeded

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

points = [(i+1, y) for i, y in enumerate(A)]

diff_list = [y - x for x, y in points]
diff_list.sort(reverse=True)

max_b = diff_list[0]
min_b = diff_list[-1]


sadness_list = []
for b in diff_list:
    sadness_list.append(sum([abs(y - (b + x)) for x, y in points]))

print(min(sadness_list))

Submission status: Time Limit Exceeded

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

L = []
m = 0
for j in range(1, N+1):
    L.append(AList[j-1] - j)
    m = median(L)

p = 0
for j in range(1, N+1):
    p += abs(AList[j-1] - j - m)

print(int(p))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
Ad = [A[i]-(i+1) for i in range(N)]
max_Ad = max(map(abs, Ad))
min_total = float("inf")

for b in range(-max_Ad, max_Ad+1):
    Ad = list(map(lambda x: x-b, Ad))
    total = sum(map(abs, Ad))
    if min_total > total:
        min_total = total
print(min_total)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
for j in range(n):
    a[j] = a[j] - (j + 1)
a.sort()
asum = sum(a)
sadlist = [asum - n * a[0]]
for i in range(1, n+1):
    sad = asum - 2 * sum(a[:i])
    if i < n/2:
        sad = sad - (n - 2 * i) * a[i]
    elif i > n/2:
        sad = sad - (n - 2 * i) * a[i-1]
    else:
        pass
    sadlist.append(sad)
    if sad == 0 or sadlist[-2] < sad:
        break
print(min(sadlist))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
line=input()
line=line.rstrip().split(" ")
list1=[]
for i in range(N):
    list1.append(int(line[i])-i-1)
#print(list1)

list2=[]
list3=[]
for j in range(2):
    for k in range(N):
        list2.append(abs(list1[k]-1-j))
        
    list3.append(sum(list2))
    list2=[]
#print(list3)

if list3[0]==list3[1]:
    print(list3[0])
elif list3[0]<list3[1]:
    list2=[]
    list3=[]
    count=100000000000000000
    for l in range(1000000000):
        for m in range(N):
            list2.append(abs(list1[m]-1+l))
        if count>=sum(list2):
            count=sum(list2)
            #print(list2)
            list2=[]
            l=l+10
        else:
            count=100000000000000000
            for n in range(l,l+11):
                for o in range(N):
                    list2.append(abs(list1[o]-1+(n-10)))
                if count>=sum(list2):
                    count=sum(list2)
                    list2=[]
                else:
                    print(count)
                    break
            break        
            
        
else: 
    list2=[]
    list3=[]
    count=100000000000000000
    for l in range(1000000000):
        for m in range(N):
            list2.append(abs(list1[m]-1-l))
        if count>=sum(list2):
            count=sum(list2)
            list2=[]
            l=l+10
        else:
            count=100000000000000000
            for n in range(l,l+11):
                for o in range(N):
                    list2.append(abs(list1[o]-1+(n-10)))
                if count>=sum(list2):
                    count=sum(list2)
                    list2=[]
                else:
                    print(count)
                    break
            break

Submission status: Time Limit Exceeded

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

def search_wb():
    sub = 1
    max_abs = abs(A[0] - sub)
    for a in A:
        if max_abs < abs(a - sub):
            max_abs = abs(a-sub)
        sub += 1
    return max_abs, -max_abs

@lru_cache(maxsize=None)
def sunuke(b):
    ret = 0
    sub = 1
    for a in A:
        ret += abs(a - (b+ sub))
        sub += 1
    return ret


maxb, minb= search_wb()

while abs(maxb - minb) > 1:
    mid = (maxb + minb) // 2
    #print("max{} min{} mid{}".format(maxb, minb, mid))
    if sunuke(mid) >  sunuke(mid + 1):
        minb = mid
    else:
        maxb = mid


mins = sunuke(minb)
maxs = sunuke(maxb)
if mins < maxs:
    print(mins)
else:
    print(maxs)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int, input().rstrip().split()))
work=int()
testA=int()
testB=int()
testC=int()
work=sum(A)//N-N//2
test=list((sum(abs(A[i]-i-work+N//2-j) for i in range(N))) for j in range(N))
output=min(test)
print(output)

Submission status: Time Limit Exceeded

Solution code:
import collections
N=int(input())
l=list(map(lambda x:int(x),input().split(' ')))
l=[l[i]-(i+1) for i in range(N)]
dl=collections.Counter(l)
ans=[0]*(len(dl))
n=1
if n<=10:
    n=len(dl)
else:
    n=len(dl)//2
for i in range(n):
    k=dl.most_common()[i][0] 
    k*=-1
    ans[i]=sum([abs(l[j]+k) for j in range(N)])
print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
def abs(x):
    if x>0:
        return x
    else:
        return x * (-1)

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    a_mi = list(a[idx] - (idx + 1) for idx in range(len(a)))
    a_mi_sorted = sorted(a_mi)
    a_mi_sorted.append(a_mi_sorted[-1]+1)##bのrangeを取るため
    setAMI = sorted(list(set(a_mi_sorted)))

    ##print(a_mi_sorted)
    ans = float('inf')
    for i in range(n):
        #i番目までa[i]-bが0以下（absで負扱い）
        buf = sum(a_mi_sorted[:n]) - 2 * (sum(a_mi_sorted[:i+1]))
        for b in range(a_mi_sorted[i], setAMI[setAMI.index(a_mi_sorted[i])+1]):
            ans = min(ans, buf + (2 * (i + 1) - n) * b)
            ##print(i,b,ans)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# C - Linear Approximation
# https://beta.atcoder.jp/contests/abc102/tasks/arc100_a

# C_Linear_Approximation.py

# 7
# 1 1 1 1 2 3 4
#import sys

N = int(input())
a = list(map(int, input().strip().split(" ")))

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

a.sort()
max = a[-1]
min = a[0]

for b in range(min, max + 1):
    sadness_left = 0
    i = 0
    while a[i] < b:
        sadness_left += b - a[i]
        i += 1
    sadness = sum(a) - b * N + sadness_left * 2
    if b == min:
        min_sadness = sadness
    elif min_sadness > sadness:
        min_sadness = sadness

print(min_sadness)

Submission status: Time Limit Exceeded

Solution code:

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

#b_init = sum(A)//N - N*(N+1)//(2*N)
b_init = min(A) + N*(N+1)//(2*N)

while 1:
    #calculate sadness
    sadness = sum([abs(A[i] - (b_init+(i+1))) for i in range(N)])
    sadness_plus1 = sum([abs(A[i] - (b_init+1+(i+1))) for i in range(N)])
    sadness_minus1 = sum([abs(A[i] - (b_init-1+(i+1))) for i in range(N)])
    
    # initial equal ans
    if sadness <= sadness_plus1 and sadness <= sadness_minus1:
        print(sadness)
        break
    
    # right way
    if sadness_plus1 < sadness:
        sad_righter = sadness_plus1
        b = b_init
        while sad_righter <= sadness:
            b+=1
            sadness = sad_righter
            sad_righter = sum([abs(A[i] - (b+(i+1))) for i in range(N)])
    
        print(sadness)
        break
    
    # left way
    if sadness_minus1 < sadness:
        sad_lefter = sadness_minus1
        b = b_init
        while sad_lefter <= sadness:
            b-=1
            sadness = sad_lefter
            sad_lefter = sum([abs(A[i] - (b+(i+1))) for i in range(N)])
    
        print(sadness)
        break

Submission status: Time Limit Exceeded

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

S1=[]
for i in range(N):
    S1.append(S[i])
S1.sort()
chuouchi=S1[len(S1)//2]
chuouchi2=S1[len(S1)//2-1]
ans=10**18
ansj=0
A=chuouchi-N//2-5
B=chuouchi-N//2+5
C=chuouchi2-N//2-10
D=chuouchi2-N//2+10
for i in range(A,B):
    goukei=0
    for j in range(N):
        goukei+=abs(S[j]-(i+j+1))
        
    if ans>goukei:
        ans=goukei
        
for i in range(C,D):
    goukei=0
    for j in range(N):
        goukei+=abs(S[j]-(i+j+1))
        
    if ans>goukei:
        ans=goukei
        
        
print(ans)

Submission status: Time Limit Exceeded

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

for b in range(-N//2,max(A)):
    sad = 0
    for i in range(N):
        sad += abs(A[i] - (b + i + 1))
    ans.append(sad)

print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def calc(A, B):
    return sum([abs(A[i]-B[i]) for i in range(len(A))])
def n(A, B):
    flag = True
    prev = calc(A, B)
    while flag:
        B -= 1
        c = calc(A, B)
        if c < prev:
            prev=c
        else:
            flag=False
    return prev
def p(A, B):
    flag = True
    prev = calc(A, B)
    while flag:
        B += 1
        c = calc(A, B)
        if c < prev:
            prev=c
        else:
            flag=False
    return prev
  
N = int(input())
A = np.array(list(map(int, input().split())))
B = np.array(list(range(int(A.mean()-(N//2)), int(A.mean()-(N//2))+N)))

m = calc(A, B)
_n = calc(A, B-1)
_p = calc(A, B+1)
if _n < m:
    print(n(A, B-1))
elif _p < m:
    print(p(A, B-1))
else:
    print(m)

Submission status: Time Limit Exceeded

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

def search_wb():
    sub = 1
    max_abs = abs(A[0] - sub)
    for a in A:
        if max_abs < abs(a - sub):
            max_abs = abs(a-sub)
        sub += 1
    return max_abs, -max_abs

def sunuke(b):
    ret = 0
    sub = 1
    for a in A:
        ret += abs(a - (b+ sub))
        sub += 1
    return ret


maxb, minb= search_wb()

while abs(maxb - minb) > 1:
    mid = (maxb + minb) // 2
    #print("max{} min{} mid{}".format(maxb, minb, mid))
    if sunuke(mid) >  sunuke(mid + 1):
        minb = mid
    else:
        maxb = mid


mins = sunuke(minb)
maxs = sunuke(maxb)
if mins < maxs:
    print(mins)
else:
    print(maxs)

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    N = int(raw_input())
    list_A = map(int, raw_input().split(' '))
    list_A = [list_A[i]-(i+1) for i in range(N)]
    b = 0
    min_sum = sys.maxint
    # search b >= 0
    while True:
        plus_sum = 0
        minus_sum = 0
        for e in list_A:
            plus_sum += abs(e - b)
            minus_sum += abs(e + b)
        sum = min(plus_sum, minus_sum)
        if min_sum > sum:
            min_sum = sum
            b += 1
        else:
            print min_sum
            break

main()

Submission status: Time Limit Exceeded

Solution code:
def abs(x):
    if x>0:
        return x
    else:
        return x * (-1)

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    a_mi = list(a[idx] - (idx + 1) for idx in range(len(a)))
    a_mi_sorted = sorted(a_mi)
    a_mi_sorted.append(a_mi_sorted[-1]+1)##bのrangeを取るため
    setAMI = sorted(list(set(a_mi_sorted)))

    ##print(a_mi_sorted)
    ans = float('inf')
    for i in range(n):
        #i番目までa[i]-bが0以下（absで負扱い）
        for b in range(a_mi_sorted[i], setAMI[setAMI.index(a_mi_sorted[i])+1]):
            ans = min(ans, sum(a_mi_sorted[:n]) - 2 * (sum(a_mi_sorted[:i+1])) + (2 * (i + 1) - n) * b)
            ##print(i,b,ans)
    print(ans)

Submission status: Time Limit Exceeded

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

import math

n = int(input())
a = [int(i) for i in input().split()]
b = [0 for i in range(n)]
b_sum = 0

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

b_avg = math.floor(b_sum / n)


res = 10**16

tmp = b_avg

while True:
    v = 0
    for i in range(n):
        v += abs(a[i] - tmp - (i + 1))
    if v < res:
        res = v
    elif v > res:
        break
    tmp += 1

tmp = b_avg - 1

while True:
    v = 0
    for i in range(n):
        v += abs(a[i] - tmp - (i + 1))
    if v < res:
        res = v
    elif v > res:
        break
    tmp -= 1

print(res)

Submission status: Time Limit Exceeded

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

ami = [ x - i - 1 for i, x in enumerate(aa)]

def sadness(al, b):
    sadl = [abs(x - b) for x in al]
    return sum(sadl)

avami = sum(ami) // n
sadnl = [sadness(ami, i) for i in range(avami-100000, avami+100000)]
print(min(sadnl))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

remain_list = A-i
while(True):
    zero_count  = np.sum(remain_list==0)
    minus_count = np.sum(remain_list <0)
    plus_count  = np.sum(remain_list >0)

    if zero_count == max(zero_count,minus_count,plus_count) or plus_count == minus_count:
        break

    if plus_count == max(zero_count,minus_count,plus_count):
        remain_list = remain_list - min(remain_list[remain_list > 0])

    if minus_count == max(zero_count,minus_count,plus_count):
        remain_list = remain_list - max(remain_list[remain_list < 0])

print(np.sum(np.abs(remain_list)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def calc(A, B):
    return sum([abs(A[i]-B[i]) for i in range(len(A))])
def n(A, B):
    flag = True
    prev = calc(A, B)
    while flag:
        B -= 1
        c = calc(A, B)
        if c < prev:
            prev=c
        else:
            flag=False
    return prev
def p(A, B):
    flag = True
    prev = calc(A, B)
    while flag:
        B += 1
        c = calc(A, B)
        if c < prev:
            prev=c
        else:
            flag=False
    return prev
  
N = int(input())
A = np.array(list(map(int, input().split())))
B = np.array(list(range(A.min(), N+A.min())))

m = calc(A, B)
_n = calc(A, B-1)
_p = calc(A, B+1)
if _n < m:
    print(n(A, B-1))
elif _p < m:
    print(p(A, B-1))
else:
    print(m)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
nums = list(map(int, input().split()))
nums = [num - (i + 1) for i, num in enumerate(nums)]
min_num = min(nums)
max_num = max(nums)

ans = 10 ** 9 + 1

for i in range(min_num, max_num + 1):
    ans = min(ans, sum([abs(num - i) for num in nums]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# C - Linear Approximation
# https://beta.atcoder.jp/contests/abc102/tasks/arc100_a

# C_Linear_Approximation.py

# 7
# 1 1 1 1 2 3 4
#import sys

N = int(input())
a = list(map(int, input().strip().split(" ")))

#sum = 0
max = a[0]-1
min = a[0]-1
for i in range(N):
    a[i] = a[i] - (i+1)
    #sum += a[i]
    if a[i] > max:
        max = a[i]
    if a[i] < min:
        min = a[i]
a.sort()

for b in range(min, max + 1):
    sadness_left = 0
    i = 0
    while a[i] < b:
        sadness_left += b - a[i]
        i += 1
    sadness = sum(a) - b * N + sadness_left * 2
    if b == min:
        min_sadness = sadness
    elif min_sadness > sadness:
        min_sadness = sadness

print(min_sadness)

Submission status: Time Limit Exceeded

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

for b in range(-N+1,max(A)):
    sad = 0
    for i in range(N):
        sad += abs(A[i] - (b + i + 1))
    ans.append(sad)

print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def mapdict(n, dictionary):
    return dict(map(lambda t:(t[0]-n,t[1]), dictionary.items()))

def count(dic):
    count = 0
    for k,v in dic.items():
        count += abs(k*v)
    return count

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

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


Adic = Counter(A2)
Ax  = A2[N//2]
Adic = mapdict(Ax, Adic)

res = count(Adic)
pl = count(mapdict(1,Adic))
mn = count(mapdict(-1,Adic))


if pl<=res:
    tmp = res
    while tmp <= res:
        res = tmp
        Adic = mapdict(1, Adic)
        tmp = count(Adic)

elif mn<=res:
    tmp = res
    while tmp <= res:
        res = tmp
        Adic = mapdict(-1, Adic)
        tmp = count(Adic)

print(res)

Submission status: Time Limit Exceeded

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

ans = 0
sub = []
for i, a in enumerate(A, 1):
    sub.append(a - i)
    ans += abs(a - i)

#print(sub)

#b = min(sub)
for b in range(min(sub), max(sub) + 1):
    #cand = 0
    cand = sum([abs(s - b) for s in sub])
    #for s in sub:
    #    cand += abs(s - b)
    ans = min(ans, cand)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N = int(input())
input_list = []
input_counter = Counter()
ans = 10**10
index = 1
for i in input().split():
    item = int(i) - index
    input_list.append(item)
    input_counter[item] += 1
    index += 1


for i in input_counter.keys():
    ans = min(ans, sum(map(lambda x: abs(x-i)*input_counter[x], input_counter.keys())))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def calc(A, B):
    return sum([abs(A[i]-B[i]) for i in range(len(A))])
def n(A, B):
    flag = True
    prev = calc(A, B)
    while flag:
        B -= 1
        c = calc(A, B)
        if c < prev:
            prev=c
        else:
            flag=False
    return prev
def p(A, B):
    flag = True
    prev = calc(A, B)
    while flag:
        B += 1
        c = calc(A, B)
        if c < prev:
            prev=c
        else:
            flag=False
    return prev
  
N = int(input())
A = np.array(list(map(int, input().split())))
B = np.array(list(range(N)))

m = calc(A, B)
_n = calc(A, B-1)
_p = calc(A, B+1)
if _n < m:
    print(n(A, B-1))
elif _p < m:
    print(p(A, B-1))
else:
    print(m)

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    N = int(raw_input())
    list_A = map(int, raw_input().split(' '))
    list_A = [list_A[i]-(i+1) for i in range(N)]
    b = 0
    min_sum = sys.maxint
    # search b >= 0
    while True:
        sum = 0
        for e in list_A:
            sum += abs(e - b)
        if min_sum > sum:
            min_sum = sum
            b += 1
        else:
            break

    b = -1
    while True:
        sum = 0 
        for e in list_A:
            sum += abs(e - b)
        if min_sum > sum:
            min_sum = sum
            b -= 1
        else:
            print min_sum
            break
        

main()

Submission status: Time Limit Exceeded

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

max = max(a)
min = max * -1
ans = 10000000
prev = 10000000
t = len(a)
flag = 0
for b in range(min,max):
  sum = 0
  for i in range(t):
    sum += abs(a[i] - (b+i+1))
  if ans > sum:
    ans = sum
  if prev < sum:
    flag += 1
  if flag == 2:
    break
  prev = sum

print(ans)

Submission status: Time Limit Exceeded

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

new_A = [a-i-1 for i, a in enumerate(A)]

m = min(new_A)
M = max(new_A)

min_s = 0
for a in new_A:
    min_s += abs(a - M)

for d in range(m, M):
    s = 0
    for a in new_A:
        s += abs(a - d)
    if s < min_s:
        min_s = s

print(min_s)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
line=input()
line=line.rstrip().split(" ")
list1=[]
for i in range(N):
    list1.append(int(line[i])-i-1)
#print(list1)

list2=[]
list3=[]
for j in range(2):
    for k in range(N):
        list2.append(abs(list1[k]-1-j))
        
    list3.append(sum(list2))
    list2=[]
#print(list3)

if list3[0]==list3[1]:
    print(list3[0])
elif list3[0]<list3[1]:
    list2=[]
    list3=[]
    count=100000000000000000
    for l in range(1000000000):
        for m in range(N):
            list2.append(abs(list1[m]-1+l))
        if count>=sum(list2):
            count=sum(list2)
            #print(list2)
            list2=[]
        else:
            print(count)
            #print(list2)
            break
        
else: 
    list2=[]
    list3=[]
    count=100000000000000000
    for l in range(1000000000):
        for m in range(N):
            list2.append(abs(list1[m]-1-l))
        if count>=sum(list2):
            count=sum(list2)
            list2=[]
        else:
            print(count)
            #print(list2)
            break

Submission status: Time Limit Exceeded

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

A = np.array(A)
I = np.array(list(range(1, N + 1)))
G = A - I
#print(G)
b = np.min(G)
#print(b)

re = -1
if b == 0:
    G = np.absolute(G)
    re = np.sum(G)
else:
    uG = np.unique(G)
    for i in uG:
        temp = np.sum(np.absolute(G - np.full(N , i)))
#        print(temp)
        if re > temp or re == -1:
            re = temp
print(int(re))