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:
# https://qiita.com/_-_-_-_-_/items/34f933adc7be875e61d0
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = map(int,input().split())   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import math
import numpy as np
import copy
from collections import defaultdict, Counter
from itertools import product
from bisect import bisect_left, bisect_right
def inpl(): return list(map(int, input().split()))


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

nA = [ Ai - (i+1) for i, Ai in enumerate(A)]
max_A = max(nA)
min_A = min(nA)

ans = 10e9

for i in range(min_A, max_A+1):
    tmp = sum([ abs(Ai - i) for Ai in nA ])
    if tmp < ans:
        ans = tmp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
num=[a for a in range(1,N+1)]
ave=int((sum(num+A)/(N)))
ans=10**9
for ave in range(-ave,ave):
  tans=0
  for b in range(1,N+1):
    tans+=abs(A[b-1]-ave-b)
  ans=min(ans,tans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

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

Z=list(set(Y))
res=10000000000000000
for i in range(len(Z)):
    cnt=0
    for j in  range(n):
        cnt+=abs(Y[j]-Z[i])
    if cnt<res:
        res=cnt
    
print(res)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

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


res=10000000000000000
for i in range(n):
    cnt=0
    for j in  range(n):
        cnt+=abs(Y[j]-Y[i])
    if cnt<res:
        res=cnt
    
print(res)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
b = 0
before1 = -1
while True:
    s = sum([abs(a - (b + i + 1)) for i, a in enumerate(A)])
    if s == 0:
        print(0)
        exit()
    if before1 != -1 and before1 < s:
        break
    before1 = s
    b += 1
b = -1
before2 = -1
while True:
    s = sum([abs(a - (b + i + 1)) for i, a in enumerate(A)])
    if s == 0:
        print(0)
        exit()
    if before2 != -1 and before2 < s:
        break
    before2 = s
    b -= 1
print(min(before1, before2))

Submission status: Time Limit Exceeded

Solution code:
int_n = int(input())
ar_int_a = list(map(int, input().split()))

max_a = max(ar_int_a)
result = []

for b in range(max_a * -1, max_a + 1):

    # print([abs(x - (b + i + 1)) for i, x in enumerate(ar_int_a)])
    result.append(sum([abs(x - (b + i + 1)) for i, x in enumerate(ar_int_a)]))

print(min(result))

Submission status: Time Limit Exceeded

Solution code:
import statistics
n = int(input())
a = list(map(int, input().split()))
l = []
m = []
for i in range(n):
    m.append(a[i]-i)
for i in range(n):
    l.append(abs(a[i]-(int(statistics.median(m))+i)))
print(sum(l))

Submission status: Time Limit Exceeded

Solution code:
class Solver(object):
    def __init__(self):
        self.n = int(input())
        self.a_s = list(map(int, input().split(" ")))
        self._sadness = {}

    def do_solve(self, b, length):
        b = 0
        current = self.sadness(b)
        left = self.sadness(b-1)
        right = self.sadness(b+1)
        while True:
            # print("{}: {} {} {}".format(b, left, current, right))
            if (left >= current) and (right >= current):
                return b
            elif left < right:  # go left
                b -= 1
            else:  # go right
                b += 1
            current = self.sadness(b)
            left = self.sadness(b-1)
            right = self.sadness(b+1)

    def solve(self):
        b = self.a_s[0] - 1
        for i in range(1, self.n+1):
            b = self.do_solve(b, i)
        print(self.sadness(b))
        
    def sadness(self, b):
        if b not in self._sadness:
            self._sadness[b] = sum(abs(self.a_s[i] - (b+i+1)) for i in range(self.n))
        return self._sadness[b]


if __name__ == "__main__":
    s = Solver()
    s.solve()

Submission status: Time Limit Exceeded

Solution code:
class Solver(object):
    def __init__(self):
        self.n = int(input())
        self.a_s = list(map(int, input().split(" ")))
        self._sadness = {}

    def solve(self):
        b = 0
        current = self.sadness(b)
        left = self.sadness(b-1)
        right = self.sadness(b+1)
        reset_counter = 0
        momentum = 1
        previous = 0  # -1 => left, 1 = right
        while True:
            # print("{}: {} {} {}".format(b, left, current, right))
            if (left >= current) and (right >= current):
                print(current)
                return
            elif left < right:  # go left
                if reset_counter < 4:
                    if previous == -1:
                        momentum *= 3
                    else:
                        reset_counter += 1
                        momentum = 1
                    previous = -1
                b -= momentum
            else:  # go right
                if reset_counter < 4:
                    if previous == 1:
                        momentum *= 3
                    else:
                        reset_counter += 1
                        momentum = 1
                    previous = 1
                b += momentum
            current = self.sadness(b)
            left = self.sadness(b-1)
            right = self.sadness(b+1)
        
    def sadness(self, b):
        if b not in self._sadness:
            self._sadness[b] = sum(abs(self.a_s[i] - (b+i+1)) for i in range(self.n))
        return self._sadness[b]


if __name__ == "__main__":
    s = Solver()
    s.solve()

Submission status: Time Limit Exceeded

Solution code:
class Solver(object):
    def __init__(self):
        self.n = int(input())
        self.a_s = list(map(int, input().split(" ")))
        self._sadness = {}

    def solve(self):
        b = 0
        current = self.sadness(b)
        left = self.sadness(b-1)
        right = self.sadness(b+1)
        reset_counter = 0
        momentum = 1
        previous = 0  # -1 => left, 1 = right
        while True:
            # print("{}: {} {} {}".format(b, left, current, right))
            if (left >= current) and (right >= current):
                print(current)
                return
            elif left < right:  # go left
                if reset_counter < 4:
                    if previous == -1:
                        momentum *= 2
                    else:
                        reset_counter += 1
                        momentum = 1
                    previous = -1
                b -= momentum
            else:  # go right
                if reset_counter < 4:
                    if previous == 1:
                        momentum *= 2
                    else:
                        reset_counter += 1
                        momentum = 1
                    previous = 1
                b += momentum
            current = self.sadness(b)
            left = self.sadness(b-1)
            right = self.sadness(b+1)
        
    def sadness(self, b):
        if b not in self._sadness:
            self._sadness[b] = sum(abs(self.a_s[i] - (b+i+1)) for i in range(self.n))
        return self._sadness[b]


if __name__ == "__main__":
    s = Solver()
    s.solve()

Submission status: Time Limit Exceeded

Solution code:
class Solver(object):
    def __init__(self):
        self.n = int(input())
        self.a_s = list(map(int, input().split(" ")))
        self._sadness = {}

    def solve(self):
        b = 0
        current = self.sadness(b)
        left = self.sadness(b-1)
        right = self.sadness(b+1)
        momentum = 1
        previous = 0  # -1 => left, 1 = right
        while True:
            # print("{}: {} {} {}".format(b, left, current, right))
            if (left >= current) and (right >= current):
                print(current)
                return
            elif left < right:  # go left
                if previous == -1:
                    momentum *= 2
                else:
                    momentum = 1
                b -= momentum
                previous = -1
            else:  # go right
                if previous == 1:
                    momentum *= 2
                else:
                    momentum = 1
                b += momentum
                previous = 1
            current = self.sadness(b)
            left = self.sadness(b-1)
            right = self.sadness(b+1)
        
    def sadness(self, b):
        if b not in self._sadness:
            self._sadness[b] = sum(abs(self.a_s[i] - (b+i+1)) for i in range(self.n))
        return self._sadness[b]


if __name__ == "__main__":
    s = Solver()
    s.solve()

Submission status: Time Limit Exceeded

Solution code:
class Solver(object):
    def __init__(self):
        self.n = int(input())
        self.a_s = list(map(int, input().split(" ")))
        self._sadness = {}

    def solve(self):
        b = 0
        current = self.sadness(b)
        left = self.sadness(b-1)
        right = self.sadness(b+1)
        while True:
            # print("{}: {} {} {}".format(b, left, current, right))
            if (left >= current) and (right >= current):
                print(current)
                return
            elif left < right:
                b -= 1
            else:
                b += 1
            current = self.sadness(b)
            left = self.sadness(b-1)
            right = self.sadness(b+1)

    def sadness(self, b):
        if b not in self._sadness:
            self._sadness[b] = sum(abs(self.a_s[i] - (b+i+1)) for i in range(self.n))
        return self._sadness[b]


if __name__ == "__main__":
    s = Solver()
    s.solve()

Submission status: Time Limit Exceeded

Solution code:
import statistics
from decimal import Decimal,ROUND_HALF_UP

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

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

med = Decimal(str(statistics.median(a))).quantize(Decimal('0'), rounding=ROUND_HALF_UP)
print(sum([abs(i-med) for i in a]))

Submission status: Time Limit Exceeded

Solution code:
import statistics
from decimal import Decimal,ROUND_HALF_UP

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

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

med = Decimal(str(statistics.median(a))).quantize(Decimal('0'), rounding=ROUND_HALF_UP)
if med == 0:
    print(sum([abs(i) for i in a]))
    exit()
    
set_a = list(set(a))
near = float('inf')
for i in range(len(set_a)):
    if abs(med - set_a[i]) < near:
        near = abs(med - set_a[i])
        mid = set_a[i]

print(sum([abs(i-mid) for i in a]))

Submission status: Time Limit Exceeded

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

p = []
m = []
for i in range(n):
    a[i] -= i+1
    if a[i] > 0:
        p += [a[i]]
    elif a[i] < 0:
        m += [a[i]]

if sum(p) == abs(sum(m)):
    print(sum([abs(i) for i in a]))
    exit()

pre = sum([abs(i) for i in a])
if sum(p) > abs(sum(m)):
    while True:
        for i in range(n):
            a[i] -= 1
        total = sum([abs(i) for i in a])
        
        if total >= pre:
            print(pre)
            exit()
        pre = total
else:
    while True:
        for i in range(n):
            a[i] += 1
        total = sum([abs(i) for i in a])
        
        if total >= pre:
            print(pre)
            exit()
        pre = total

Submission status: Time Limit Exceeded

Solution code:
def comp(n, a, i):
    ans, ans_p, ans_m = 0, 0, 0
    for j in range(n):
        ans += abs(a[j] - (j+i+1))
        ans_p += abs(a[j] - (j+i+2))
        ans_m += abs(a[j] - (j+i))
    return ans, ans_p, ans_m

n = int(input())
a = list(map(int, input().split()))
i = 0
while(1):
    num, num_p, num_m = comp(n, a, i)
    if num <= num_p and num <= num_m:
        print(num)
        exit()
    elif num <= num_p and num >= num_m:
        i += -1
    elif num >= num_p and num <= num_m:
        i += 1

Submission status: Time Limit Exceeded

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

minA = 10**9

for b in range(min(A)-10,max(A)+N):
    submin = [abs(A[i]-b-i-1) for i in range(N)]
    # print(submin)
    minA = min(sum(submin),minA)

print(minA)

Submission status: Time Limit Exceeded

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

bmax = max(A)
bmin = min(A)-N

def getSadNess(b):
    return sum([abs(A[i]-(b+i+1)) for i in range(N)]) 

def binSearch(bmin,bmax):
    b = (bmin+bmax)//2
    sadb = getSadNess(b)
    sadm = getSadNess(b-1)
    sadp = getSadNess(b+1)
    if sadb<=sadp and sadb<=sadm:
        return sadb
    elif sadb>sadm:
        return binSearch(bmin,b-1)
    else:
        return binSearch(b+1,bmax)
    
print(binSearch(bmin,bmax))

Submission status: Time Limit Exceeded

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

bmax = max(A)
bmin = min(A)-N

def getSadNess(A,b):
    return sum([abs(A[i]-(b+i+1)) for i in range(N)]) 

def binSearch(A,bmin,bmax):
    b = (bmin+bmax)//2
    sadb = getSadNess(A,b)
    sadm = getSadNess(A,b-1)
    sadp = getSadNess(A,b+1)
    if sadb<=sadp and sadb<=sadm:
        return sadb
    elif sadb>sadm:
        return binSearch(A,bmin,b)
    else:
        return binSearch(A,b,bmax)
    
print(binSearch(A,bmin,bmax))

Submission status: Time Limit Exceeded

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

def getSadness(A,b):
    ret = 0
    for i in range(N):
        ret += abs(A[i]-(b+i+1))
    return ret

sad0 = getSadness(A,0)
sad1 = getSadness(A,1)

min = min(sad0,sad1)
new = min

i=1
while True:
    if sad0<sad1:
        new = getSadness(A,-i)
    else:
        new = getSadness(A,i+1)
    if new<min:
        min = new
    else:
        break
    i += 1

print(min)

Submission status: Time Limit Exceeded

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

sorted_A = sorted(A)

if len(A) == 1:
    ans = 0
elif N % 2 == 1 and not len(A) == 1 :
    ans = sum(map(lambda x: abs(x-sorted_A[N//2+2]),A))
    for x in range(sorted_A[N//2],sorted_A[N//2+2]):
        y = sum(map(lambda z: abs(z -x),A))
        if ans > y :
            ans = y
else:
    ans = sum(map(lambda x: abs(x-sorted_A[N//2+1]),A))
    for x in range(sorted_A[N//2],sorted_A[N//2+1]):
        y = sum(map(lambda z: abs(z -x),A))
        if ans > y :
            ans = y
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A_list = list(map(int, input().split()))
for i in range(n):
    A_list[i] -= i
A_list.sort()
A_cum = [0] * n
for i in range(n):
    if i == 0:
        A_cum[0] = A_list[0]
    else:
        A_cum[i] = A_cum[i-1] + A_list[i]
def findinfindex(sortedlist, key, l, r):
    if r - l <= 0:
        return l
    m = (l+r+1)//2
    if sortedlist[m] > key:
        return findinfindex(sortedlist, key, l, m-1)
    else:
        return findinfindex(sortedlist, key, m, r)
sadmin = -1
for b in range(A_list[0],A_list[n-1]+1):
    lastminus = findinfindex(A_list, b, 0, n-1)
    sadness = (2*lastminus - n + 2)*b - 2*A_cum[lastminus] + A_cum[n-1]
    if sadmin == -1:
        sadmin = sadness
    elif sadness < sadmin:
        sadmin = sadness
    else:
        break
print(sadmin)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A_list = list(map(int, input().split()))
for i in range(n):
    A_list[i] -= i
A_list.sort()
A_cum = [0] * n
for i in range(n):
    if i == 0:
        A_cum[0] = A_list[0]
    else:
        A_cum[i] = A_cum[i-1] + A_list[i]
def findinfindex(sortedlist, key, l, r):
    if r - l <= 0:
        return l
    m = (l+r+1)//2
    if sortedlist[m] > key:
        return findinfindex(sortedlist, key, l, m-1)
    else:
        return findinfindex(sortedlist, key, m, r)
sadnesses=[]
for b in range(A_list[0],A_list[n-1]+1):
    lastminus = findinfindex(A_list, b, 0, n-1)
    sadness = (lastminus + 1)*b - 2*A_cum[lastminus] + A_cum[n-1] - (n - lastminus - 1)*b
    sadnesses.append(sadness)
print(min(sadnesses))

Submission status: Time Limit Exceeded

Solution code:
import collections

def calc_score(key):
    return sum([abs(b - key) for b in bList])

def calc_center():
    ans = 0
    for pair in scList:
        ans += pair[0]*pair[1]
    ans = ans / N
    return ans

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

bList = [a - i - 1 for i,a in enumerate(aList)]
cList = collections.Counter(bList)
scList = cList.most_common()

center = calc_center()
key = scList[0][0]

ans = 100000000
for c in range(min(key, int(center)-1), max(key, int(center)+1)):
    ans = min(ans, calc_score(c))
print(ans)

Submission status: Time Limit Exceeded

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

for i in range(n):
    b = A[i] - (i + 1)
    B.append(b)
    
ans = 10 ** 9
    
for b in B:
    Sum = 0
    for i in range(n):
        Sum += abs(A[i] - (b + (i + 1))) 
    ans = min(ans, Sum)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
for j in range(n):
    a[j] = a[j] -(j + 1)
def cal(b):
    c = 0
    for j in range(n):
        c += abs(a[j] - (b))
    return c    
d = []
for l in set(a):
    d.append(cal(l))
print(min(d))

Submission status: Time Limit Exceeded

Solution code:
a = int(input())
ar = list(map(int,input().split(" ")))
cr = []
for j in range(-max(ar),max(ar)+1):
    count = 0
    for i in range(a):
        count += abs(ar[i] - (i+1 + j))
    cr.append(count)
print(min(cr))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = list(map(int,input().strip().split()))
alist = list(map(int,input().strip().split()))
ans = float("inf")

s = np.array([i for i in range(len(alist))])
slist = alist-s

for i in range(len(alist)):
    num = 0
    xlist = list(map(lambda x:abs(x-slist[i]), slist))
    num = sum(xlist)
    if ans > num:
        ans = num

print(ans)

Submission status: Time Limit Exceeded

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

A = [v-i-1 for i,v in enumerate(A)]
print(min(sum(abs(v - b) for v in A) for b in range(min(A),max(A)+1)))

Submission status: Time Limit Exceeded

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

def sad(A,b):
    return(sum(abs(v - b - i) for i,v in enumerate(A)))

print(min(sad(A,v) for v in range(-len(A),max(A),1)))

Submission status: Time Limit Exceeded

Solution code:
import sys

def cost(N, A, b):
	return sum([abs(A[i] - b - i - 1) for i in range(N)])

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

res = float("inf")
b = 0
if cost(N, A, b) <= cost(N, A, b - 1) and  cost(N, A, b) <= cost(N, A, b + 1):
	print cost(N, A, b)
	sys.exit()
elif cost(N, A, b) < cost(N, A, b + 1):
	delta = -1
else:
	delta = 1
b += delta
pre_delta = delta
while pre_delta == delta:
	if cost(N, A, b) < cost(N, A, b + delta):
		break
	b += delta
print cost(N, A, b)

Submission status: Time Limit Exceeded

Solution code:

def calc(A, b):
    retval = 0
    for a in A:
        retval += abs(a - b)
    return retval


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

    left = min(A)
    right = max(A)

    while left < right:
        c1 = (left + left + right) // 3       # floor
        c2 = -(-(left + right + right) // 3)  # ceil
        if calc(A, c1) <= calc(A, c2):
            right = c2 - 1
        else:
            left = c1 + 1
    print(calc(A, left))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math


def calc(A, b):
    return sum(map(lambda x: abs(x-b), A))


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

    left = min(A)
    right = max(A)

    while left < right:
        c1 = math.floor((left + left + right) / 3)
        c2 = math.ceil((left + right + right) / 3)
        if calc(A, c1) <= calc(A, c2):
            right = c2 - 1
        else:
            left = c1 + 1
    print(calc(A, left))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math


def calc(A, b):
    retval = 0
    for a in A:
        retval += abs(a - b)
    return retval


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

    left = min(A)
    right = max(A)

    while left < right:
        c1 = math.floor((left + left + right) / 3)
        c2 = math.ceil((left + right + right) / 3)
        if calc(A, c1) <= calc(A, c2):
            right = c2 - 1
        else:
            left = c1 + 1
    print(calc(A, left))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math


def calc(A, b):
    retval = 0
    for a in A:
        retval += abs(a - b)
    return retval


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

    left = min(A)
    right = max(A)

    while left < right:
        c1 = math.floor((left + left + right) / 3)
        c2 = math.floor((left + right + right) / 3)
        if calc(A, left) <= calc(A, right):
            right = c2
        else:
            left = c1
    print(calc(A, left))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math


def calc(A, b):
    retval = 0
    for a in A:
        retval += abs(a - b)
    return retval


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

    left = min(A)
    right = max(A)

    while left < right:
        center = math.floor((left + right) / 2)
        if calc(A, left) <= calc(A, right):
            right = center
        else:
            left = center
    print(calc(A, left))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
a2 = []
for i in range(n):
    a2.append(a[i]-i-1)
a3 = []
for i in range(n):
    m = min(a2)
    a3.append(m)
    a2.remove(m)
if n % 2 == 0:
    b = (a3[n//2-1]+a3[n//2])//2
else:
    b = a3[n//2]
s = 0
for i in a3:
    s += abs(i-b)
print(s)

Submission status: Time Limit Exceeded

Solution code:
def 解():
    iN = int(input())
    aA = map(int,input().split())
    aA = sorted(map(lambda x,y:x-y,aA,range(1,iN+1)))
    iL = len(aA)
    if iL % 2 :
        iMed = aA[(iL-1)//2]
    else:
        iMed = aA[iL//2]
    iMean = sum(aA) // 2
    iBlim= min(iMed,iMean)
    iUlim= min(iMed,iMean+1)

    iD = iN*max(abs(_) for _ in aA)
    for i in range(min(iMed,iMean),max(iMed,iMean+1)+1):
        iC = 0
        for a in aA:
            iC += abs(a - i)
        if iD > iC:
            iD = iC
    print(iD)
解()

Submission status: Time Limit Exceeded

Solution code:
# Linear Approximation
from statistics import median
n = int(input())
a = sorted((lambda x: [list(map(int, x.split()))[i] - i - 1 for i in range(n)])(input()))
print(int(sum([abs(i - median(a)) for i in a])))

Submission status: Time Limit Exceeded

Solution code:
count = int(input())
nums = list(map(int, input().split()))


def f(b):
    sum_num = 0
    for x, num in enumerate(nums, 1):
        sum_num += abs(num - (b + x))

    return sum_num


maximum = max(nums)

minimum = 10000000
for i in range(-1 * maximum, maximum + 1):
    calc = f(i)
    if minimum > calc:
        minimum = calc
        ans = calc

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def f(x,i,n):
    sadness = 0
    for j in range(n):
        sadness += abs(x[j]-i)
    return(sadness)
N = int(input())
H = [int(i) for i in input().split()]
for i in range(N):
    H[i] -= i+1
H = sorted(H)
D = f(H,1,N)

for i in range(N):
    D = min(D,f(H,H[i],N))
print(D)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
C - Linear Approximation
https://beta.atcoder.jp/contests/abc102/tasks/arc100_a

"""
import sys
from sys import stdin
input = stdin.readline

from functools import lru_cache
def solve(arr):
    @lru_cache(maxsize=None)
    def calc_score(n):
        return sum([abs(a-(n+i)) for i, a in enumerate(arr, start=1)])

    ub = max(arr)
    lb = -max(arr)

    while True:
        mid1 = (lb*2 + ub) // 3
        mid2 = (lb + ub*2) // 3
        mid1_score = calc_score(mid1)
        mid2_score = calc_score(mid2)

        if mid2_score > mid1_score:
            ub = mid2
        else:
            lb = mid1
        if abs(ub - lb) <= 4:
            break

    ans = float('inf')
    for b in range(lb, ub+1):
        t = calc_score(b)
        ans = min(ans, t)
    return ans


def main(args):
    N = int(input())
    arr = [int(a) for a in input().split()]
    ans = solve(arr)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
C - Linear Approximation
https://beta.atcoder.jp/contests/abc102/tasks/arc100_a

"""
import sys
from sys import stdin
input = stdin.readline


def solve(arr):
    ub = max(arr)
    lb = -max(arr)

    while True:
        mid1 = (lb*2 + ub) // 3
        mid2 = (lb + ub*2) // 3
        mid1_score = sum([abs(a-(mid1+i)) for i, a in enumerate(arr, start=1)])
        mid2_score = sum([abs(a-(mid2+i)) for i, a in enumerate(arr, start=1)])

        if mid2_score > mid1_score:
            ub = mid2
        else:
            lb = mid1
        if abs(ub - lb) <= 4:
            break

    ans = float('inf')
    for b in range(lb, ub+1):
        t = sum([abs(a-(b+i)) for i, a in enumerate(arr, start=1)])
        ans = min(ans, t)
    return ans



def main(args):
    N = int(input())
    arr = [int(a) for a in input().split()]
    ans = solve(arr)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

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

for i in range(n):
    nums[i] -= (i + 1)
    if i == 0:
        x = y =  nums[i]
    else:
        if nums[i] < x:
            x = nums[i]
        elif y < nums[i]:
            y = nums[i]

d = 0
for i in range(x, y):
    c = 0
    for j in range(n):
        c += abs(nums[j] - i)
    else:
        if d != 0 and d < c:
            print(d)
            break
        elif d == 0 and c == 0:
            print(d)
            break
        else:
            d = c
else:
    print(d)

Submission status: Time Limit Exceeded

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

for i in range(n):
    nums[i] -= (i + 1)
    
x = min(nums)
y = max(nums)
z = []
for i in range(x, y+1):
    c = 0
    for j in range(n):
        c += abs(nums[j] - i)
    else:
        z.append(c)

print(min(z))

Submission status: Time Limit Exceeded

Solution code:
ans=9999999999
n=int(input())
b=0-n
list=[int(x) for x in input().split()]
lim=max(list)
while b<=lim:
    val=0
    for i in range(0,n):
        val=val+abs(list[i]-(b+i+1))
    ans=min(ans,val)
    b=b+1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
b=n*(-1)
k=0
ans=0

def sunuke(b):
    ans=0
    for i in range(n):
        ans+=abs(a[i]-b-i-1) 
    return ans 
        
while k<1:
    if sunuke(b)<sunuke(b+1):
        print(sunuke(b))
        k=1
    else:
        b+=1

Submission status: Time Limit Exceeded

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

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

result = 0
while len(A) > 1:
  result += A[-1] - A[0]
  A = A[1:-1]

print(result)

Submission status: Time Limit Exceeded

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

answer = 65535
max_A = max(A)
for x in range(-max_A-1, max_A+1):
    answer = min(answer, sum([abs(num - (i+1) - x) for i, num in enumerate(A)]))

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
N = int(input())
lists = [int(i) for i in input().split()]
sok = sys.maxsize
list2 = [xx - max(lists) for xx in range (2 * max(lists) + 1)]
for b in list2:
    kanashi = 0
    i = 1
    for x in lists:
        kanashi += abs(x - (b + i))
        i += 1
    if (kanashi < sok):
        sok = kanashi
print(sok)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=sorted([int(x)-(i+1) for i,x in enumerate(input().split())])
ans=float("inf")
average=sum(a)//n
for i in a:
    ans=min(ans,sum([abs(x-i) for x in a]),sum([abs(x-i-1) for x in a]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=sorted([int(x)-(i+1) for i,x in enumerate(input().split())])
ans=float("inf")
average=sum(a)//n
for i in range(min(a),max(a)+1):
    ans=min(ans,sum([abs(x-i) for x in a]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
a = list(range(1,N+1))
bbef = -N//2
baft = (-N//2)+1
elementbef = [abs(i-j-bbef) for (i,j) in zip(A,a)]
sumbef = sum(elementbef)
elementaft = [abs(i-j-baft) for (i,j) in zip(A,a)]
sumaft = sum(elementaft)
while(sumaft-sumbef < 0):
    bbef = bbef+1
    baft = baft+1
    elementbef = [abs(i-j-bbef) for (i,j) in zip(A,a)]
    sumbef = sum(elementbef)
    elementaft = [abs(i-j-baft) for (i,j) in zip(A,a)]
    sumaft = sum(elementaft)
print(sumbef)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
a = list(range(1,N+1))
bbef = -N
baft = -N+1
elementbef = [abs(i-j-bbef) for (i,j) in zip(A,a)]
sumbef = sum(elementbef)
elementaft = [abs(i-j-baft) for (i,j) in zip(A,a)]
sumaft = sum(elementaft)
while(sumaft-sumbef < 0):
    bbef = bbef+1
    baft = baft+1
    elementbef = [abs(i-j-bbef) for (i,j) in zip(A,a)]
    sumbef = sum(elementbef)
    elementaft = [abs(i-j-baft) for (i,j) in zip(A,a)]
    sumaft = sum(elementaft)
print(sumbef)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(map(int, input().rstrip().split(" ")))

min_v = 0
for i in range(0, n):
    v = 0
    for j in range(0, n):
        v = v + abs(s[j] - (s[i]-i + j))
    if i == 0 or v < min_v:
        min_v =v
print(min_v)