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 math

N = input()
A = [int(x) for x in input().split()]

Ad = []
for i, v in enumerate(A):
    Ad.append(v - (i + 1))

average = int(round(sum(Ad) / float(len(Ad))))

def get_diff(avg):
    diff = 0
    for i, v in enumerate(A):
        diff += abs(v - (avg + i + 1))
    return diff

d = get_diff(average)

dm = get_diff(average - 1)

while dm < d:
    average = average - 1
    d = dm
    dm = get_diff(average - 1)

dp = get_diff(average + 1)

while dp < d:
    average = average + 1
    d = dp
    dp = get_diff(average + 1)



# print(A)
# print(Ad)
# print(average)
# print(diff1)
# print(diff2)
print(d)

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:
        break
    sadlist.append(sad)
print(min(sadlist))

Submission status: Time Limit Exceeded

Solution code:
N=input()
A=map(int, raw_input().split())
B=range(1,N+1)

C=[]
for x,y in zip(A,B):
	C.append(x-y)

K=set(C)
L=list(K)
L.append(0)
L.sort()

h=len(L)
l=0


ans=float("inf")

for j in range(1000):
	m=(h+l)/2
	x=L[m]
	t=0
	for y in C:
		t+=abs(-1*x+y)

	if t<ans:
		ans=t
		h=m
	else:
		l=m
	ans=min(ans,t)

print 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 - 1

    if minus_count == max(zero_count,minus_count,plus_count):
        remain_list = remain_list + 1

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

Submission status: Time Limit Exceeded

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

min_ans = pow(10,15)
for b in reversed(range(-max(A), 0)):
    ans = 0
    for i in range(len(A)):
        #print(A[i], b, i, abs(A[i] - (b + i + 1)))
        ans += abs(A[i] - (b + i + 1))
    #print("ans", b, ans)
    if min_ans >= ans: min_ans = ans
    else: break


min_ans_b = pow(10,15)
for b in range(0, max(A)):
    ans = 0
    for i in range(len(A)):
        ans += abs(A[i] - (b + i + 1))
    #print("ans", b, ans)
    if min_ans_b >= ans: min_ans_b = ans
    else: break


if min_ans_b < min_ans:
    min_ans = min_ans_b

print(min_ans)

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
list = []
flag = 0
for b in range(min,max):
  sum = 0
  j = 0
  for i in a:
    j += 1
    sum += abs(i - (b+j))
  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:
#! /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)

tmp = b_avg

res = 10**16

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

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

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
    for s in sub:
        cand += abs(s - b)
    ans = min(ans, cand)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def calc_sad_score(a, b):
  return sum([abs(num - (b + i)) for i, num in enumerate(a)])

n = int(input())
numbers = [int(num) for num in input().split(' ')]
answer = 0

tmp = []
for b in range(10**9):
  tmp.append(calc_sad_score(numbers, b))
answer = min(tmp)
print(answer)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
list1=[int(i) for i in input().split()]
list2=[]
for i in range(max(list1)-min(list1)+1):
    kana=0
    for j in range(N):
        kana+=abs(list1[j]-(min(list1)-(max(list1)-min(list1))+i+j))
    list2.append(kana)
print(min(list2))

Submission status: Time Limit Exceeded

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

min_ans = pow(10,15)
for b in range(-max(A), max(A)):
    ans = 0
    for i in range(len(A)):
        #print(A[i], b, i, abs(A[i] - (b + i + 1)))
        ans += abs(A[i] - (b + i + 1))
    #print("ans", b, ans)
    if min_ans >= ans: min_ans = ans
    else: break


"""min_ans_b = pow(10,15)
for b in range(0, max(A)):
    ans = 0
    for i in range(len(A)):
        ans += abs(A[i] - (b + i + 1))
    #print("ans", b, ans)
    if min_ans_b >= ans: min_ans_b = ans
    else: break


if min_ans_b < min_ans:
    min_ans = min_ans_b
"""
print(min_ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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

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

A_max = max(A_) + 1
A_min = min(A_) - 1

A_b = [sum([abs(a - i) for a in A_]) for i in range(A_min, A_max+1)]

print(min(A_b))

Submission status: Time Limit Exceeded

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

for i in range(n):
	A[i] -= i+1
sad = 1000000000000
for b in range(min(A),max(A)+1):
	a = A
	for i in range(n):
		a[i] = abs(a[i]-b)
	sad = min(sad,sum(a))
	
print(sad)

Submission status: Time Limit Exceeded

Solution code:
# Q3
import numpy as np

def kanashii(a,b):
    kanashisa = 0
    for i in range(len(a)):
        kanashisa+=abs(a[i] - b)
#     print('kanashisa:{}'.format(kanashisa))
    return kanashisa

n = int(input())
a = np.array(list(map(int, input().split())))
arr_i = np.array(list(i+1 for i in range(len(a))))
a2 = a - arr_i
# print(a2)

k1=k2=temp =0
for i in range(np.max(a2),np.min(a2)-1,-1):
    temp = kanashii(a2,i)
#     print("b{} k:{}".format(i, temp))
    if(temp<k1 or k1==0):
#         print(i,temp)
        k2=k1
        k1=temp
    if((k1< k2 and k1>temp) or (k1< k2 and k1>temp)):
        break
print(k1)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin


def get_value(b, A):
    return sum([abs(x - (b + i + 1)) for i, x in enumerate(A)])


def main():
    N = int(stdin.readline().rstrip())
    A = [int(x) for x in stdin.readline().rstrip().split()]

    l = -2 * 10 ** 8
    h = 2 * 10 ** 8
    while True:
        idx = (l + h) // 2
        tmp = [get_value(b, A) for b in [idx - 1, idx, idx + 1]]
        if min(tmp) == tmp[1]:
            print(tmp[1])
            return
        elif min(tmp) == tmp[2]:
            l = idx
        else:
            h = idx
        assert l <= h


if __name__ == '__main__':
    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
list = []
for b in range(min,max):
  sum = 0
  j = 0
  for i in a:
    j += 1
    sum += abs(i - (b+j))
  if ans > sum:
    ans = sum
  prev = sum

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
l_abs = []
for i, a_i in enumerate(a):
    l_abs.append(abs((i+1)-a_i))
b = list(set(l_abs))
b_m = [-i for i in b]
b.extend(b_m)
min = 10 ** 16
if sum(l_abs) == 0:
    min = 0
else:
    for i in b:
        sum = 0
        for j, a_j in enumerate(a):
            sum += abs(a_j-(i + j + 1))
        if(min > sum):
            min = sum
print(min)

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]


for b in range(min, max + 1):
    sadness = 0
    for i in range(N):
        if a[i] > b:
            sadness += a[i] - b
        else:
            sadness += b - a[i]
    if b == min:
        min_sadness = sadness
    elif min_sadness > sadness:
        min_sadness = sadness

print(min_sadness)

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

print(ans)

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)

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:
def BinSearch(A, hi, lo):
    b = (hi + lo) // 2
    tmp0 = FindAns(A, b - 1)
    tmp1 = FindAns(A, b)
    if hi == lo:
        tmp2 = FindAns(A, b + 1)
        return min(tmp0, tmp1, tmp2)
    if tmp0 < tmp1:
        return BinSearch(A, b - 1, lo)
    else:
        return BinSearch(A, hi, lo + 1)
    
def FindAns(A, b):
    ans = 0
    for a in A:
        ans += abs(a - b)
    return ans

n = int(input())
A = list(map(int, input().split()))
for i in range(n):
    A[i] -= i + 1
A = sorted(A)
hi = A[int(len(A) / 2 + 1) if int(len(A) / 2 + 1) <  len(A)  else int(len(A) / 2)]
lo = A[int(len(A) / 2 - 1) if int(len(A) / 2 - 1) >= 0 else int(len(A) / 2)]

print(BinSearch(A, hi, lo))

Submission status: Time Limit Exceeded

Solution code:


def sadness(numbers, b, n):
    sum = 0
    for i in range(1, n+1):
        sum += abs(numbers[i-1] - (b+i))
    return sum


n = int(input())
arr = input().split(" ")
numbers = []
for i in range(0,len(arr)):
    numbers.append(int(arr[i]))

max = sorted(numbers)[0]
#print(max)
#print(max)
min = 9223372036854775807

# start at 0, determine direction, and keep on looking

sm1 = s = sadness(numbers,-1,n)
s0 = s = sadness(numbers,0,n)
s1 = s = sadness(numbers,1,n)

goDown = False
if sm1 < s0: goDown = True
if goDown:
    sc = s0
    scp = sm1 = s = sadness(numbers,-1,n)
    current = 0
    while sc > scp:
        current += -1
        sc = scp
        scp = sadness(numbers,current-1,n)
    print(sc)
else:
   # print("tes")
    sc = s0
    scp = sm1 = s = sadness(numbers, 1, n)
    current = 0
    while sc > scp:
        current += 1
        sc = scp
        scp = sadness(numbers, current + 1, n)
    print(sc)


#for i in range(-4, 4):
#   s = sadness(numbers,i,n)
#   #print(min)
#   print(s)
#   if s < min:
#       min = s
#print(min)

Submission status: Time Limit Exceeded

Solution code:

N = int(input())
A = list(int(i) for i in input().split())

candidate = []
for j in range(int(-max(A)/2),max(A)):
    sad = 0
    for i in range(N):
        sad += abs(A[i] - j - i)
    candidate.append(sad)
    if j>=1:
        if min(candidate) <= sad:
            break
ans = min(candidate)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil, floor

N = int(input())
A = [int(t) for t in input().split()]
if len(A) != N: raise

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

q = []
for b in p:
    q.append(sum(abs(x - b) for x in p))
print(min(q))

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]

sadnesses = []

for b in range(min, max + 1):
    sadness = 0
    for i in range(N):
        if a[i] > b:
            sadness += a[i] - b
        else:
            sadness += b - a[i]
    sadnesses.append(sadness)

sadnesses.sort()
print(sadnesses[0])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin


def get_value(b, A):
    return sum([abs(x - (b + i + 1)) for i, x in enumerate(A)])


def main():
    N = int(stdin.readline().rstrip())
    A = [int(x) for x in stdin.readline().rstrip().split()]

    l = -2 * 10 ** 2
    h = 2 * 10 ** 2
    while True:
        idx = (l + h) // 2
        tmp = [get_value(b, A) for b in [idx - 1, idx, idx + 1]]
        if min(tmp) == tmp[1]:
            print(tmp[1])
            return
        elif min(tmp) == tmp[2]:
            l = idx
        else:
            h = idx
        assert l < h


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

N = int(input())
A = list(int(i) for i in input().split())

candidate = []
for j in range(-max(A),max(A)):
    sad = 0
    for i in range(N):
        sad += abs(A[i] - j - i)
    candidate.append(sad)
    if j>=1:
        if min(candidate) <= sad:
            break
ans = min(candidate)
print(ans)

Submission status: Time Limit Exceeded

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

sa = A - np.array(range(1,N+1))
log = float('inf')
for i in range(sa.min(), sa.max()+1):
    sum_ = abs(sa - i).sum()
    if log > sum_:
        log = sum_
    else:
        break
print(log)

Submission status: Time Limit Exceeded

Solution code:
a = int(input())
b = [int(i) for i in input().split()]
n = float("inf")
s = sum(b)-(a*(a+1))/2
c = int(s/a)
for i in range(c-abs(c)-1,c+abs(c)+1):
    k = 0
    for j in range(a):
        k += abs(b[j] - (i + j + 1))
    if k < n:
        n = k
print(n)

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
for i in range(N):
    a[i] = a[i] - (i+1)
    sum += a[i]
#print(a)
A = a[:]
A.sort()
max = A[-1]
min = A[0]

sadnesses = []

for b in range(min, max + 1):
    sadness = 0
    for i in range(N):
        if a[i] > b:
            sadness += a[i] - b
        else:
            sadness += b - a[i]
    sadnesses.append(sadness)

sadnesses.sort()
print(sadnesses[0])

Submission status: Time Limit Exceeded

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

max_num = max(n_list)
min_num = 0 - max_num

min_sad = float('Inf')
prev_sad = float('Inf')

for b in range(min_num, max_num+1):
  sad = 0
  for i, a in enumerate(n_list):
    sad += abs(a-(b+i+1))
  if prev_sad < sad:
    break
  prev_sad = sad

  min_sad = min(min_sad, sad)

print(min_sad)

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)

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:
            print(b)
            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:
            print(b)
            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:
N=int(input())
A=[int(i) for i in input().split()]
s=0
t=0
for i in range(N):
    s+=abs(A[i]-1-i)
    t+=abs(A[i]-i)
if s>t:
    d=0
    while True:
        d-=1
        r=0
        u=0
        for i in range(N):
            r+=abs(A[i]-d-1-i)
            u+=abs(A[i]-d-i)
        if r>u:
            continue
        else:
            print(r)
            break
elif s==t:
    print(s)
else:
    e=0
    while True:
        e+=1
        x=0
        y=0
        for i in range(N):
            x+=abs(A[i]-e-1-i)
            y+=abs(A[i]-e-i)
        if x<y:
            continue
        else:
            print(y)
            break

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

line = list(map(int, input().split( )))
data = []
for i in range(len(line)):
    data.append(line[i] - i-1 )
d = max(data) - min(data) +1
m = min(data)
b = m
c = 0
sad = []
for i in range(d):
    for j in range(len(data)):
        c += abs(data[j] - b)
    sad.append(c)
    c=0
    b += 1

print(min(sad))

Submission status: Time Limit Exceeded

Solution code:
def maxElem( lis ):
  '''
  与えられたリストの中に、最も多く存在する要素を返す
  (最大の数の要素が複数ある場合、pythonのsetで先頭により近い要素を返す)
  '''
  L = lis[:]#copy
  S = set(lis)
  S = list(S)
  MaxCount=0
  ret='nothing...'

  for elem in S:
    c=0
    while elem in L:
      ind = L.index(elem)
      foo = L.pop(ind)
      c+=1
    if c>MaxCount:
      MaxCount=c
      ret = elem
  return ret


if __name__ == "__main__" :
    n = int(input())
    array = list(map(int, input().split()))

    for i in range(0, n):
        array[i] = array[i] - (i + 1)
    elem = int(maxElem(array))
    
    for i in range(0, n):
        array[i] = abs(array[i] - elem)

    sum_n = sum(array)

    print(sum_n)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
AS = input().split()
for i in AS:
    i = int(i)
result = 0
result_f = 0
result_rf = 0
for j in range (1, N+1):
    result += abs(int(AS[j-1]) - 0 - j)
for j in range (1, N+1):
    result_f += abs(int(AS[j-1]) - 1 - j)
for j in range (1, N+1):
    result_rf += abs(int(AS[j-1]) - ( - 1) - j)
if result < result_f and result < result_rf:
    print(result)
else:
    old_list= [0]
    b = 1
    while(not b in old_list):
        counter = 0
        for j in range (1,N+1):
            counter += abs(int(AS[j-1]) - b - j)
        if counter <= result:
            old_list.append(b)
            b += 1
            result = counter
        else:
            old_list.append(b)
            continue
    result_1 = result
    b = -1
    while(not b in old_list):
        counter = 0
        for j in range (1,N+1):
            counter += abs(int(AS[j-1]) - b - j)
        if counter <= result:
            old_list.append(b)
            b -= 1
            result = counter
        else:
            old_list.append(b)
            continue
    result_2 = result
    print (min(result_1,result_2))

Submission status: Time Limit Exceeded

Solution code:
size = int(input())
A = list(map(int,input().split()))
i = list(range(1,size+1))

remain_list = [A-i for(A,i) in zip(A,i)]
while(True):
    zero_count = len([i for i in remain_list if i ==0])
    minus_count = len([i for i in remain_list if i <0])
    plus_count = len([i for i in remain_list if i > 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 = [num - 1 for num in remain_list]

    if minus_count == max(zero_count,minus_count,plus_count):
        remain_list = [num + 1 for num in remain_list]


sum_list =[abs(num) for num in remain_list]

print(sum(sum_list))

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
a= list(map(int,input().split()))
ans = 100000000000
#b = [0 for i in range(n+1)]

#for i in range(n):
#    b[i+1] = b[i] + a[i]
sa = 0
ans = 0
for i in range(n):
    b = abs(a[i] -(i+1))
    #print(b)
    ans += b
    sa = max(sa,b)
#print(ans)
c = 0
d = 0
for i in range(int(sa*2)):
    c=0
    for j in range(n):
        c += abs(a[j] - (j+1 + i - sa))
    #print(c,d)
    ans = min(c,ans)


print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 整数の入力
N = int(input())
l = list(map(int, input().split(" ")))

l_ = [num - i - 1 for i, num in enumerate(l)]
# print(l_)

count_list = []
for j in range(min(l_), max(l_) + 1):
    count = sum([abs(i - j) for i in l_])
    count_list.append(count)

print(min(count_list))

Submission status: Time Limit Exceeded

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

Ai_i = []

for i in range(len(A)):
    Ai_i.append(A[i] - (i+1))

#max_abs = 0
#for i in range(len(Ai_i)):
#    if abs(Ai_i[i]) > max_abs:
#        max_abs = abs(Ai_i[i])

min_ = min(Ai_i)
max_ = max(Ai_i)

if min_ <= 0 and max_ <= 0:
    max_ = max([abs(min_), abs(max_)])

if min_ >= 0 and max_ >= 0:
    min_ = min([-abs(min_), -abs(max_)])    

min_abs = float("inf")
min_index = 0

if sum(Ai_i) < 0:
    min_ = 0
    if max_ == 0:
        max_ = 1
elif sum(Ai_i) > 0:
    max_ = 0
    if min_ == 0:
        min_ = -1


    
for b in range(min_, max_+1):
    abss = []
    for i in range(len(Ai_i)):
        abss.append(abs(Ai_i[i] + b))
    abs_sum = sum(abss)
    if abs_sum < min_abs:
        min_abs = abs_sum
print(min_abs)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
sad=[]
sadsum=[]
sadsum.append(1000000001)
b=int(max(a))
for i in range(-b,b):
    for j in range(n):
        sad.append(abs(a[j]-(i+j+1)))
        if sum(sad)>min(sadsum):
            break
        else:
            pass
        if j==n-1:
            sadsum.append(sum(sad))
            sad=[]
        else:
            pass
print(min(sadsum))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def mapdict(itemfunc, dictionary):
    return dict(map(itemfunc, dictionary.items())) 

def minus(tup):
    return (tup[0]-1,tup[1]) 
def plus(tup):
    return (tup[0]+1,tup[1]) 

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 = [A[i-1]-i for i in range(1,N+1)]
Adic = Counter(A2)
Ax  = Adic.most_common()[0][0]
Adic = mapdict(lambda t: (t[0]+Ax,t[1]), Adic)

res = count(Adic)
pl = count(mapdict(plus,Adic))
mn = count(mapdict(minus,Adic))


if pl<res:
    tmp = float("inf")
    while res <= tmp:
        tmp = res
        Adic = mapdict(plus, Adic)
        res = count(Adic)
    res = tmp

elif mn<res:
    tmp = float("inf")
    while res <= tmp:
        tmp = res
        Adic = mapdict(minus, Adic)
        res = count(Adic)
    res = tmp

print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

dif = []
for idx, v in enumerate(A_list, 1):
    dif.append(v - idx)
b = 0
dif_num = sum(map(abs, (map(lambda x: x + b, dif))))
b = 1
dif_num_plus = sum(map(abs, (map(lambda x: x + b, dif))))
b = -1
dif_num_minus = sum(map(abs, (map(lambda x: x + b, dif))))
if dif_num <= dif_num_plus and dif_num < dif_num_minus:
    print(dif_num)
    sys.exit()

p_f = True
if dif_num_plus < dif_num_minus:
    p_f = True
    b = 1
else:
    p_f = False
    b = -1

dif_num = min(dif_num, dif_num_plus, dif_num_minus)

while True:
    if p_f:
        b += 1
    else:
        b -= 1
    l = list((map(lambda x: x + b, dif)))
    dif_num2 = sum(map(abs, (map(lambda x: x + b, dif))))
    if dif_num2 < dif_num:
        dif_num = dif_num2
    else:
        break
print(dif_num)

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)
for i in range(len(dl)):
    k,v=dl.most_common()[i] 
    k*=-1
    ans[i]=sum([abs(l[j]+k) for j in range(N)])
print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

line = list(map(int, input().split( )))

#print(line)

data = []

for i in range(len(line)):
    data.append(line[0] - i-1 )
    line.pop(0)

#print(data)

d = max(data) - min(data) +1
m = min(data)
b = m
c = 0
sad = []

for i in range(d):
    for j in range(len(data)):
        c += abs(data[j] - b)
    sad.append(c)
    c=0
    b += 1

#print(m)
#print(sad)
print(min(sad))

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())

A = list(map(int, input().split()))
heikin = round(sum(A) / N) - 1

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

s = []
t = []

absmax = max(list(map(abs, A)))
t = [A[i] - absmax - 1 for i in range(N)]

for i in range(-absmax - 1  , absmax + 1):
    t = [t[j] + 1 for j in range(N)]
    s.append(sum(list(map(abs, t))))

print(min(s))

Submission status: Time Limit Exceeded

Solution code:

N = int(input())
A = list(int(i) for i in input().split())

candidate = []
for j in range(int(-max(A)/2),int(max(A)/2)):
    sad = 0
    for i in range(N):
        sad += abs(A[i] - j - i)
    candidate.append(sad)
ans = min(candidate)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def maxElem( lis ):
  '''
  与えられたリストの中に、最も多く存在する要素を返す
  (最大の数の要素が複数ある場合、pythonのsetで先頭により近い要素を返す)
  '''
  L = lis[:]#copy
  S = set(lis)
  S = list(S)
  MaxCount=0
  ret='nothing...'

  for elem in S:
    c=0
    while elem in L:
      ind = L.index(elem)
      foo = L.pop(ind)
      c+=1
    if c>MaxCount:
      MaxCount=c
      ret = elem
  return ret


if __name__ == "__main__" :
    n = int(input())
    array = list(map(int, input().split()))

    for i in range(0, n):
        array[i] = array[i] - i - 1
    elem = int(maxElem(array))
    # print(maxElem(array))
    # print(array)
    
    for i in range(0, n):
        array[i] = abs(array[i] - elem)

    # sum_n = sum(array)

    # if sum_n > n:
    #     for j in range(0, n):
    #         array[j] = array[j] * array[j]
    sum_n = sum(array)

    print(sum_n)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))
max_v = np.max(a)
min = 10 ** 16

for b in range(-(max_v+1), max_v+1):
    sum = 0
    for j, a_j in enumerate(a):
        sum += abs(a_j-(b+j+1))
    if(min > sum):
        min = sum
print(min)

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)

if min(ami) == max(ami):
    print(0)
else:
    sadnl = [sadness(ami, i) for i in range(min(ami),max(ami))]
    print(min(sadnl))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int, input().split()))
number=[]
for i in range (N):
    number.append(i)
diff=[]
for j in range (N):
    diff.append(number[j]-A[j])
import collections
c = collections.Counter(diff)
c.most_common()
for k in range (N):
    diff[k]=abs(diff[k]-c.most_common()[0][0])
print(sum(diff))

Submission status: Time Limit Exceeded

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

A2 = [0] * N
for i in range(0, N):
    A2[i] = A[i] - (i + 1)
#print(A2)

def sad(A, b):
    f = lambda x: abs(x-b)
    return sum(map(f, A))

max_ = max(A2)
min_ = min(A2)

start_b = min_
sad_min = sad(A2, start_b)
#print(start_b, sad_min)
for b in range(start_b+1, max_+1):
    v = sad(A2, b)
    #print(b, v, sad_min)
    if sad_min >= v:
        sad_min = v
#    else:
#        break

print(sad_min)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin


def get_value(b, A):
    return sum([abs(x - (b + i + 1)) for i, x in enumerate(A)])


def main():
    N = int(stdin.readline().rstrip())
    A = [int(x) for x in stdin.readline().rstrip().split()]

    l = -2 * 10 ** 8
    h = 2 * 10 ** 8
    while True:
        idx = (l + h) // 2
        tmp = [get_value(b, A) for b in [idx - 1, idx, idx + 1]]
        if min(tmp) == tmp[1]:
            print(tmp[1])
            return
        elif min(tmp) == tmp[2]:
            l = idx
        else:
            h = idx
        assert l < h


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def calc(B):
    plus = 0
    minus = 0
    zero = 0
    ans1 = 0
    for i in range(N):
        tmp = A[i]-(B+i+1)
        ans1 += abs(tmp)
        if(tmp == 0):
            zero += 1
        elif tmp > 0:
            plus += 1
        else:
            minus += 1
    return ans1, plus, minus, zero

if __name__ == '__main__':
    
    N = int(input())
    A = list(map(int, input().split()))
    plus = 0
    minus = 0
    zero = 0
    target = 0
    while((zero < (N/3))):
        ans, plus, minus, zero = calc(target)
        if(plus > (N/3)):
            target += 1
        if(minus > (N/3)):
            target -= 1
        if plus != 0 and plus == minus:
            break
        # print(ans, plus, minus, zero)
    print(ans)