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:
# サンプル3
# 6
# 6 5 4 3 2 1
# b=3で2+0+2+4+6+8 = 22 b=4で1+1+3+5+7+9=26
# わからんからコード書いて試す
n = int(input())
a = list(map(int, input().split()))
# for b in range(-10, 10):
#     tmp = 0
#     for i, v in enumerate(a):
#         tmp += abs(v - (b + i + 1))
#     print(f"b={b}, tmp={tmp}")
# でかくても小さくてもダメっぽい
# 三分探索？やったことないしやり方わからんからググる
# めぐる式にこれhttps://qiita.com/ganariya/items/1553ff2bf8d6d7789127をしただけ

ok, ng = -10**9, 10**9 + 1


def calc(b):
    ret = 0
    for i, v in enumerate(a):
        ret += abs(v - (b + i + 1))
    return ret


# なぜかTLEなるのでカウンタを設置してみた
c = 0
while ng - ok > 1 and c < 100000:
    c += 1
    c1 = (2 * ok + ng) // 3
    c2 = (ok + 2 * ng) // 3
    b1, b2 = calc(c1), calc(c2)
    if b1 > b2:
        ok = c1 + 1  # +1のきもちは不明
    else:
        ng = c2

print(calc(ok))

Submission status: Time Limit Exceeded

Solution code:
# サンプル3
# 6
# 6 5 4 3 2 1
# b=3で2+0+2+4+6+8 = 22 b=4で1+1+3+5+7+9=26
# わからんからコード書いて試す
n = int(input())
a = list(map(int, input().split()))
# for b in range(-10, 10):
#     tmp = 0
#     for i, v in enumerate(a):
#         tmp += abs(v - (b + i + 1))
#     print(f"b={b}, tmp={tmp}")
# でかくても小さくてもダメっぽい
# 三分探索？やったことないしやり方わからんからググる
# めぐる式にこれhttps://qiita.com/ganariya/items/1553ff2bf8d6d7789127をしただけ

ok, ng = -10**9, 10**9 + 1


def calc(b):
    ret = 0
    for i, v in enumerate(a):
        ret += abs(v - (b + i + 1))
    return ret


# なぜかTLEなるのでカウンタを設置してみた
c = 0
while ng - ok > 1 or c < 100000:
    c += 1
    c1 = (2 * ok + ng) // 3
    c2 = (ok + 2 * ng) // 3
    b1, b2 = calc(c1), calc(c2)
    if b1 > b2:
        ok = c1 + 1  # +1のきもちは不明
    else:
        ng = c2

print(calc(ok))

Submission status: Time Limit Exceeded

Solution code:
# サンプル3
# 6
# 6 5 4 3 2 1
# b=3で2+0+2+4+6+8 = 22 b=4で1+1+3+5+7+9=26
# わからんからコード書いて試す
n = int(input())
a = list(map(int, input().split()))
# for b in range(-10, 10):
#     tmp = 0
#     for i, v in enumerate(a):
#         tmp += abs(v - (b + i + 1))
#     print(f"b={b}, tmp={tmp}")
# でかくても小さくてもダメっぽい
# 三分探索？やったことないしやり方わからんからググる
# めぐる式にこれhttps://qiita.com/ganariya/items/1553ff2bf8d6d7789127をしただけ

ok, ng = -10**9, 10**9 + 1


def calc(b):
    ret = 0
    for i, v in enumerate(a):
        ret += abs(v - (b + i + 1))
    return ret


while ng - ok > 1:
    c1 = (2 * ok + ng) // 3
    c2 = (ok + 2 * ng) // 3
    b1, b2 = calc(c1), calc(c2)
    if b1 > b2:
        ok = c1 + 1  # +1のきもちは不明
    else:
        ng = c2

print(calc(ok))

Submission status: Time Limit Exceeded

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

def solve(N: int, A: "List[int]"):
    from scipy.optimize import dual_annealing
    A = [a-i for i, a in enumerate(A, 1)]
    def f(b):
        return sum(abs(a-b) for a in A)
    res = dual_annealing(f, [[min(A), max(A)+1]], maxiter=100)
    #print(res)
    b = res.x[0]
    return min(f(int(round(b))), f(int(round(b+1))))

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"    
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Time Limit Exceeded

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

def solve(N: int, A: "List[int]"):
    from scipy.optimize import rosen, differential_evolution, minimize, basinhopping
    A = [a-i for i, a in enumerate(A, 1)]
    def f(b):
        return sum(abs(a-b) for a in A)
    res = differential_evolution(f, [[min(A), max(A)]])
    b = res.x[0]
    return min(f(int(round(b))), f(int(round(b+1))))

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"    
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Time Limit Exceeded

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

left = -10**10
right = 10**10

def get_score(b):
    score = 0
    for i in range(N):
        score += abs(A[i]-b-i)
    return score

while(right > left + 1):
    mid = (left+right) // 2
    if get_score(mid+1) - get_score(mid) < 0:
        left = mid
    else:
        right = mid

print(get_score(right))

Submission status: Time Limit Exceeded

Solution code:
mina=10**10
R=0
N=int(input())
L=list(map(int,input().split()))
for i in range(N):
  L[i]=L[i]-i-1
a=max(L)
b=min(L)
for i in range(b,a+1):
  for j in range(N):
    R=R+abs(L[j]-i)
  mina=min(R,mina)
  R=0
print(mina)

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

n = INT()
a = LIST()
c = [a[i] - i - 1 for i in range(n)]
tmp = set(c)
ans = inf
for j in tmp:
    ans = min(ans, sum([abs(c[i] - j) for i in range(n)]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def calc(b,A):
  ret=0
  for i,num in enumerate(A):
    ret += abs( num-(b+i+1) )
  return ret    
##########################

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

L=-1*10**9
R=10**9
i=(L+R)//2

while True:
  s=calc(i-1,A)
  t=calc(i,A)
  u=calc(i+1,A)
  if s<t<u:
    R=i
    i=(L+R)//2
  elif s>t>u:
    L=i
    i=(L+R)//2
  else:
    print(t)
    break

Submission status: Time Limit Exceeded

Solution code:
def main():
    from decimal import Decimal

    N = int(input())
    *A, = map(Decimal, input().split())
    A = [x - i for i, x in enumerate(A, start=1)]
    A.sort()

    median = -1
    if N % 2 == 1:
        median = A[N // 2]
    else:
        median = (A[N // 2 - 1] + A[N // 2]) / 2  # ->ここで0.5が生じても偶数個足し合わせてintに戻る

    ans = sum(map(lambda x: abs(x - median), A))
    print(int(ans))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main(n,a):
  import numpy as np
  a=np.array([a[i]-i for i in range(n)])
  #print(a)
  #print(len(a[a<0]))
  #print(len(a[a>0]))
  if len(a[a<0])==len(a[a>0]):
    print(sum(list(map(abs,a))))
    exit()
  elif len(a[a<0])>len(a[a>0]):
    while len(a[a<0])>len(a[a>=0]):
      a+=np.min(a[a<0])
    print(sum(list(map(abs,a))))
    exit()
  elif len(a[a<0])<len(a[a>0]):
    while len(a[a<=0])<len(a[a>0]):
      a-=np.min(a[a>0])
    print(sum(list(map(abs,a))))
    exit()
if __name__=='__main__':
  import sys
  input = sys.stdin.readline
  n=int(input())
  a=list(map(int,input().split()))
  main(n,a)

Submission status: Time Limit Exceeded

Solution code:
def main(n,a):
  import numpy as np
  a=np.array([a[i]-i for i in range(n)])
  #print(a)
  #print(len(a[a<0]))
  #print(len(a[a>0]))
  if len(a[a<0])==len(a[a>0]):
    print(sum(list(map(abs,a))))
    exit()
  elif len(a[a<0])>len(a[a>0]):
    while len(a[a<0])>len(a[a>=0]):
      a+=1
    print(sum(list(map(abs,a))))
    exit()
  elif len(a[a<0])<len(a[a>0]):
    while len(a[a<=0])<len(a[a>0]):
      a-=1
    print(sum(list(map(abs,a))))
    exit()
if __name__=='__main__':
  import sys
  input = sys.stdin.readline
  n=int(input())
  a=list(map(int,input().split()))
  main(n,a)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int,input().split()))
A = [j-i-1 for i,j in enumerate(A)]
top = max(A)
bottom = min(A)
def sad(b):
  ret=0
  for i in A:
    ret += abs(i-b)
  return ret
while top - bottom > 2:
  mid1 = (top + bottom*2)//3
  mid2 = (top*2 + bottom)//3
  if sad(mid1) < sad(mid2):
    top = mid2
  else:
    bottom = mid1
print(min(sad(bottom), sad((bottom+top)//2), sad(top)))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[a[i]-(i+1) for i in range(n)]
ans=9999999999999999
for bi in set(b):
    ans=min(ans,sum([abs(b[j]-bi) for j in range(n)]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[a[i]-(i+1) for i in range(n)]
ans=9999999999999999
min_b=min(b)
max_b=max(b)
for i in range(min_b,max_b+1):
    ans=min(ans,sum([abs(b[j]-i) for j in range(n)]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
A = [int(i) for i in input().split()]
A = np.array([A[i] - i - 1 for i in range(N)])
ans = 0
for i in range(N):
    if i == 0:
        ans = np.sum(np.abs(A - np.ones(N) * A[i]))
    else:
        ans = min(ans, np.sum(np.abs(A - np.ones(N) * A[i])))
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

t = []
for b in range(-max(A),max(A)):
  s = []
  for idx,elem in enumerate(A):
    s.append(abs(elem-(b+(idx+1))))
  t.append(sum(s))

print(min(t))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
arr=list(map(int,input().split()))
pc=0
mc=0
zc=0
p=[]
m=[]
for i in range(n):
  arr[i]-=(i+1)
  if arr[i]>0:
    pc+=1
    p.append(arr[i])
  elif arr[i]<0:
    mc+=1
    m.append(arr[i])
  else:
    zc+=1
p=sorted(p)
m=sorted(m,reverse=True)
diff=0
while 1:
  if pc+zc>=mc and mc+zc>=pc:
    print(sum(p)+abs(sum(m))+diff)
    break
  else:
    if pc+zc<mc:
      diff+=abs(m[0])*(pc+zc)
      tm=[]
      tmp=abs(m[0])
      pc+=zc
      zc=0
      for i in range(mc):
        m[i]=m[i]+tmp
        if m[i]!=0:
          tm.append(m[i])
        else:
          mc-=1
          zc+=1
      m=tm
    else:
      diff+=p[0]*(mc+zc)
      tp=[]
      tmp=p[0]
      mc+=zc
      zc=0
      for i in range(pc):
        p[i]=p[i]-tmp
        if p[i]!=0:
          tp.append(p[i])
        else:
          pc-=1
          zc+=1

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=list(map(int,input().split()))
l=[x-i-1 for i,x in enumerate(l)]
ans=10**9
for i in l:
    cal=[abs(x-i) for x in l]
    ans=min(ans,sum(cal))
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 = 10 ** 9
#print (min(A))
for i in range(min(A), max(A)+1):
    b = [abs(A[j]-i) for j in range(N)]
#    print (sum(b))
#    print (b)
    ans = min(ans, sum(b))

print (ans)

Submission status: Time Limit Exceeded

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

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

import math
#import statistics
#b=statistics.median(a)
b=math.floor(sum(a)/n)


def p(b,k):
  s=0
  t=0
  for i in a:
      s+=abs(i-b)
      t+=abs(i-b-1) 
  if s>t:
    if k==-1:
      print(t)
    else:
      return p(b+1,1)
  elif s==t:
    print(s)
  else:
    if k==1:
      print(s)
    else:
      return p(b-1,-1)
  
p(b,0)

Submission status: Time Limit Exceeded

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

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

import math
#import statistics
#b=statistics.median(a)
b=math.floor(sum(a)/n)


def p(b,k):
  s=0
  for i in a:
      s+=abs(i-b)
  t=0
  for i in a:
      t+=abs(i-b-1) 
  if s>t:
    if k==-1:
      print(t)
    else:
      return p(b+1,1)
  elif s==t:
    print(s)
  else:
    if k==1:
      print(s)
    else:
      return p(b-1,-1)
  
p(b,0)

Submission status: Time Limit Exceeded

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

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

import math
b=math.floor(sum(a)/n)


def p(b,k):
  s=0
  for i in a:
      s+=abs(i-b)
  t=0
  for i in a:
      t+=abs(i-b-1) 
  if s>t:
    if k==-1:
      print(t)
    else:
      return p(b+1,1)
  else:
    if k==1:
      print(s)
    else:
      return p(b-1,-1)
  
p(b,0)

Submission status: Time Limit Exceeded

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

aa = [ai - i-1 for i,ai in enumerate(a)]

def tri_search(f:"f(x:float)->float", left, right, iter=100)->float:
    for _ in range(iter):
        ml = (left*2 + right) / 3
        mr = (left + right*2) / 3
        if f(ml) < f(mr):
            right = mr
        else:
            left = ml
    # print(left, right)
    return (right + left) / 2

def f(x):
    ret = 0
    x = round(x)
    for aai in aa:
        ret += abs(aai - x)
    return ret

b = tri_search(f, -10**9, 10**9)
print(f(b))

Submission status: Time Limit Exceeded

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

aa = [ai - i-1 for i,ai in enumerate(a)]
aa.sort()

def tri_search(f:"f(x:float)->float", left, right, iter=100)->float:
    for _ in range(iter):
        ml = (left*2 + right) / 3
        mr = (left + right*2) / 3
        if f(ml) < f(mr):
            right = mr
        else:
            left = ml
    # print(left, right)
    return (right + left) / 2

def f(x):
    ret = 0
    x = round(x)
    for aai in aa:
        ret += abs(aai - x)
    return ret

b = tri_search(f, -10**9, 10**9)
print(f(b))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math

N = int(input())
a = np.array(list(map(int, input().split())))
adj = a - np.arange(1,N+1)
ave = np.average(adj)
med = np.median(adj)

ans = 10 ** 10
if ave <= med:
	t0 = int(math.floor(ave))
	t1 = int(math.ceil(med)) + 1
else:
	t0 = int(math.floor(med))
	t1 = int(math.ceil(ave)) + 1

for opt in range(t0,t1):
	res = 0
	for i in range(N):
		res += abs(adj[i] - opt)
	ans = min(ans, res)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n = I()
    a = LI()
    for i in range(n):
        a[i] -= i+1
    a.sort()
    ans = float("inf")
    for b in a:
        m = 0
        for i in range(n):
            m += abs(a[i]-b)
        ans = min(ans,m)
    print(ans)

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

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

Submission status: Time Limit Exceeded

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

m = []
for i in range(n):
    m.append(l[i]-i)

b = set(m)
max = 0
index = 0
for i in b:
    if max < m.count(i):
        max = m.count(i)
        index = i

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

print(ans)

Submission status: Time Limit Exceeded

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

N, As = int(input()), list(map(int, input().split()))
As = [As[i] - i - 1 for i in range(N)]
ans = sys.maxsize
for b in range(min(As), max(As) + 1):
    ans = min(ans, sum(map(lambda A: abs(A - b), As)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
N=int(input().strip())
a=list(map(int, input().strip().split(' ')))
for i in range(N):
    a[i]=a[i]-(i+1)
b=sum(a)/N
ans1=0
ans2=0
for i in range(N):
    ans1+=abs(a[i]-math.floor(sum(a)/N))
for i in range(N):
    ans2+=abs(a[i]-math.ceil(sum(a)/N))


print(min(ans1,ans2))

Submission status: Time Limit Exceeded

Solution code:
def func(A,b):
  s=0
  for i in range(len(A)):
    s+=abs(A[i]-(b+i))
  return s

N=int(input())
A=[int(i) for i in input().split(' ')]
MIN=None
for b in range(min(A[0],A[-1]-len(A)),max(A[-1],A[0]+len(A))):
  if MIN==None:
    MIN=func(A,b)
  elif MIN>func(A,b):
    MIN=func(A,b)
print(MIN)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

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

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

B = sorted(A2)

i1 = int(N/2) - 1
i2 = int(N/2)


b1 = B[i1]
b2 = B[i2]


def calcSad(A2, b):
    sum = 0
    for i in A2:
        sum += abs(i - b)
    return sum


sum = 99999999999999999999999
for b in range(b1, b2+1):
    s = calcSad(B, b)
    sum = min(sum, s)

print(sum)


sys.exit(0)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
answer = 0
r = 0
flag = 0
gear = 0
for i in range(N) :
    A[i] = A[i]-(i+1)
    if A[i] <= 0 :
        r += 1
    answer += abs(A[i])
if r == N :
    gear += 1
while flag == 0 :
    p = 0
    q = 0
    if gear == 0 :
        for j in range(N) :
            A[j] = A[j]-1
            if A[j] <= 0 :
                q += 1
            p += abs(A[j])
    else :
        for j in range(N) :
            A[j] = A[j]+1
            if A[j] >= 0 :
                q += 1
            p += abs(A[j])
    if p < answer :
        answer = p
    if q == N :
        flag += 1
print(answer)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
As = sorted([int(a)-i for i, a in enumerate(input().strip().split(' '))])

for i, a in enumerate(As):
    temp = min(temp, -1 * sum([x-As[i] for x in As[:i]]) + sum([x-As[i] for x in As[i:]])) if i!= 0 else -1 * sum([x-As[i] for x in As[:i]]) + sum([x-As[i] for x in As[i:]])
print(temp)

Submission status: Time Limit Exceeded

Solution code:

import sys
import collections


l1 = sys.stdin.readline()
l2 = sys.stdin.readline()
N = int(l1.strip())
l2 = [int(x.strip()) for x in l2.split()]
l2 = [l2[i] - (i+1) for i in range(0,len(l2))]


A = sorted(l2)
minA = min(A)
maxA = max(A)

def culc(x):
	return sum([abs(y - x) for y in A])

res = culc(minA)
resMin = res

C = collections.Counter(A)
# 辞書をソートしなくてもいいや。indexのlistつくる。
#C = sorted(C.items(), key=lambda x: x[0])

Ind = sorted(list(set(A)))

#print(A)
#print(C)
#print(Ind)

i = 0
k = Ind[i]

lowsum = C[k]

for x in range(minA+1, maxA+1):
	#print(res)
	# x <= A[j]
	#print("{}, {}".format(x, lowsum))
	res += lowsum #xが増えた分、x以下の分が増える
	res -= (N-lowsum) #xが増えた分、x以上の分が減る
	#print("i{}, Ind{}, x{}".format(i, k, x))

	# x-1<A[j], x=A[j]の場合
	if x >= Ind[i+1]:
		i += 1
		k = Ind[i]
		lowsum += C[k]
	
	resMin = min(res, resMin)


print(resMin)

Submission status: Time Limit Exceeded

Solution code:
import sys

l1 = sys.stdin.readline()
l2 = sys.stdin.readline()
N = int(l1.strip())
l2 = [int(x.strip()) for x in l2.split()]
l2 = [l2[i] - (i+1) for i in range(0,len(l2))]

A = sorted(l2)
minA = min(A)
maxA = max(A)

res = -1

#途中で反転するのを入れると、処理楽そう？

def culc(x):
	return sum([abs(y - x) for y in A])

for x in range(minA, maxA+1):
	if res == -1:
		res = culc(x)
	else:
		res = min(res,culc(x))

print(res)

Submission status: Time Limit Exceeded

Solution code:
def getinputdata():

    # 配列初期化
    array_result = []
    
    data = input()
    
    array_result.append(data.split(" "))

    flg = 1

    try:

        while flg:

            data = input()

            if(data != ""):
                
                array_result.append(data.split(" "))

            else:

                flg = 0
    finally:

        return array_result

arr_data = getinputdata()

n = int(arr_data[0][0])
arr = [int(x) for x in arr_data[1]]
maxdata=max(arr)

val=float('inf') 
for b in range(maxdata*-1,maxdata):
    
    mysum=0
    for i in range(n):

        mysum+=abs(arr[i]-(b+i+1))

    val=min(val,mysum)
    
print(val)

Submission status: Time Limit Exceeded

Solution code:
a=int(input())
while True:
  a=a+1

Submission status: Time Limit Exceeded

Solution code:
import statistics
import math

N = int(input())
a = input().split()
ans = 0
for i in range(0,N):
	a[i] = int(a[i])-i
ave = sum(a)/len(a)
for i in range(0,N):
	ans += abs(a[i]-int(statistics.median(a)))
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
for i in range(n):
    a[i] -= i+1

def hoge(b):
    v = 0
    for x in a:
        v += abs(x-b)
    return v

tmp = float('inf')
for x in set(a):
    if hoge(x) < tmp:
        tmp = hoge(x)

print(tmp)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
for i in range(n):
    a[i] -= i+1

def hoge(b):
    t = [abs(x-b) for x in a]
    return sum(t)

tmp = float('inf')
for x in a:
    if hoge(x) < tmp:
        tmp = hoge(x)

print(tmp)

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
n = int(input())
nums = sorted([num - i for i, num in enumerate(list(map(int,input().split())), 1)])


sums = [None for i in range(n)]
sums[0] = nums[0]
allv = sum(nums)

minv = nums[0] * (2 - n) - 2 * sums[0] + allv
for i in range(n-1):
    sums[i+1] = sums[i] + nums[i+1]
    for b in range(nums[i], nums[i+1]+1):
        p = b * (2*(i+1) - n) -2 * sums[i] + allv
        minv = min(minv,p)

print(minv)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
 
n = int(input())
a = list(map(int, input().split(" ")))

b = [i for i in range(1, n+1, 1)]

a = np.array(a)
b = np.array(b)

a -= b

ans = sum(abs(a))
flag = 0
while(flag < 500):
    a1 = a[a < 0]
    a2 = a[a > 0]

    if(len(a1) > len(a2)):
        if(len(a1) == 0): tmp = 1
        elif(flag == 0): tmp = -int(np.average(a1))
        else: tmp = -min(a1)
        a += tmp
    else:
        if(len(a2) == 0): tmp = 1
        elif(flag == 0): tmp = int(np.average(a2))
        else: tmp = max(a2)
        a -= tmp
    if(ans <= sum(abs(a))): flag += 1
    else: ans = sum(abs(a))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
a = int(input())
b = list(map(int,input().split()))
 
for i in range(a):
	b[i] -= i + 1
 
b.sort()
s = 0
co = 0
ss = 0
coco = 0
cococo = 0
summ = 0
su = 0
bb = 0
for i in range(a):
	if b[i] < 0:
		co += 1
	elif b[i] > 0:
		coco += 1
	else:
		cococo += 1
	su += abs(b[i])

if co > coco:	
	while su != 0:
		bb = 0
		for i in range(a):
			b[i] += 1
			bb += abs(b[i])
		if bb > su:
			print(su)
			break
		su = bb
		bb = 0


elif coco >= co:
	while su != 0:
		for i in range(a):
			b[i] -= 1
			bb += abs(b[i])
		if bb > su:
			print(su)
			break
		su = bb
		bb = 0

if su == 0:
	print(0)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
 
n = int(input())
a = list(map(int, input().split(" ")))

b = [i for i in range(1, n+1, 1)]

a = np.array(a)
b = np.array(b)

a -= b

ans = sum(abs(a))
flag = 0
while(flag < 1000):
    a1 = a[a < 0]
    a2 = a[a > 0]

    if(len(a1) > len(a2)):
        if(len(a1) == 0): tmp = 1
        elif(flag == 0): tmp = -int(np.average(a1))
        else: tmp = -min(a1)
        a += tmp
    else:
        if(len(a2) == 0): tmp = 1
        elif(flag == 0): tmp = int(np.average(a2))
        else: tmp = max(a2)
        a -= tmp
    if(ans <= sum(abs(a))): flag += 1
    else: ans = sum(abs(a))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
 
n = int(input())
a = list(map(int, input().split(" ")))

b = [i for i in range(1, n+1, 1)]

a = np.array(a)
b = np.array(b)

a -= b

ans = sum(abs(a))
while(True):
    a1 = a[a < 0]
    a2 = a[a > 0]

    if(len(a1) > len(a2)):
        if(len(a1) == 0): tmp = 1
        else: tmp = -max(a1)
        a += tmp
    else:
        if(len(a2) == 0): tmp = 1
        else: tmp = min(a2)
        a -= tmp
    if(ans <= sum(abs(a))): break
    else: ans = sum(abs(a))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
AA = sorted([ a - i - 1 for i,a in enumerate(A) ])
C = []
for i,a in enumerate(AA):
    if i == 0:
        C.append(a)
    else:
        C.append(C[-1] + a)
ans = ""
#print(C)
for b in AA:
    sample = 0
    num = 0
    for i,a in enumerate(AA):
        if b <= a:
            num = i -1 
            break
        else:
            num = i
    if num == -1:
        sample = C[-1]  - b * (N - 2 * (num + 1))
    else:
        sample = C[-1] - 2 * C[num] - b * (N - 2 * (num + 1))
    if ans == "":
        ans = sample
    if ans > sample:
        ans = sample
if ans == "":
    ans = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import collections
n = int(input())
a = np.array(list(map(int, input().split())))
check = np.arange(1, n+1)
c = list(a - check)
b = collections.Counter(c)
b = np.array(list(b.keys()))
count = 0
for i in range(1, n+1):
    count += abs(a[i-1] - i - b)
print(min(count))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    p, z, m = [], 0, []
    for i in range(n):
        t = a[i] - (i + 1)
        if t > 0:
            p.append(t)
        elif t == 0:
            z += 1
        else:
            m.append(-t)
    if sum(m) > sum(p):
        p, m = m[:], p[:]

    ps, ms = sum(p), sum(m)
    pl, ml = len(p), len(m)
    p.sort()
    m.sort()
    x = 0
    ans = ms + ps
    while True:
        if pl <= 0:
            break
        t = p.pop(0)
        t, x = t - x, t
        ps -= pl * t
        pl -= 1
        if t > 0:
            ml += z
            ms += ml * t
            z = 1
        else:
            z += 1
        if ms + ps < ans:
            ans = ms + ps
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
AA = sorted([ a - i - 1 for i,a in enumerate(A) ])
C = []
for i,a in enumerate(AA):
    if i == 0:
        C.append(a)
    else:
        C.append(C[-1] + a)
ans = ""
#print(C)
for b in range(AA[0],AA[-1]):
    sample = 0
    num = 0
    for i,a in enumerate(AA):
        if b <= a:
            num = i -1 
            break
        else:
            num = i
    if num == -1:
        sample = C[-1]  - b * (N - 2 * (num + 1))
    else:
        sample = C[-1] - 2 * C[num] - b * (N - 2 * (num + 1))
    if ans == "":
        ans = sample
    if ans > sample:
        ans = sample
if ans == "":
    ans = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
p = []
m = []
z = 0
for i in range(n):
    a[i] = a[i] - (i + 1)
    if a[i] > 0:
        p.append(a[i])
    elif a[i] == 0:
        z += 1
    else:
        m.append(-a[i])
if sum(m) > sum(p):
    p, m = m[:], p[:]

ps = sum(p)
ms = sum(m)
pl = len(p)
ml = len(m)
p.sort()
m.sort()
x = 0
ans = ms + ps
while True:
    if pl <= 0:
        break
    t = p.pop(0)
    t, x = t - x, t
    ps -= pl * t
    pl -= 1
    if t > 0:
        ml += z
        ms += ml * t
        z = 1
    else:
        z += 1
    if ms + ps < ans:
        ans = ms + ps
print(ans)

Submission status: Time Limit Exceeded

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

A_dash = []
for i, A_i in enumerate(A):
    A_dash.append(A_i - (i))
A_dash.sort()

tmp_ans = sum(A_dash)
ans = 0
left, right = min(A_dash), max(A_dash)
mid = (left+right)//2
ans_left, ans_mid, ans_right = 0, 0, 0
for A_dash_i in A_dash:
    ans_left += abs(A_dash_i - (mid-1))
    ans_mid += abs(A_dash_i - (mid))
    ans_right += abs(A_dash_i - (mid+1))

while not (ans_left >= ans_mid and ans_mid <= ans_right):
    mid = (left+right)//2
    ans_left, ans_mid, ans_right = 0, 0, 0
    for A_dash_i in A_dash:
        ans_left += abs(A_dash_i - (mid-1))
        ans_mid += abs(A_dash_i - (mid))
        ans_right += abs(A_dash_i - (mid+1))
    if ans_left < ans_mid:
        right = (left+right)//2
    else:
        left = (left+right)//2

print(ans_mid)

Submission status: Time Limit Exceeded

Solution code:
inf = float("inf")

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

bmin = inf
bmax = -inf

for b in range(0, N):
    bmin = min(bmin, A[b] - b)
    bmax = max(bmax, A[b] - b)

bb = inf

mn = round(bmin + bmax)
for d in range(mn, bmin -1, -1):
    df = 0
    for b in range(0, N):
        df = df + abs(A[b] - (d + b))
    if df < bb:
        bb = df
    else:
        break

for d in range(mn, bmax + 1):
    df = 0
    for b in range(0, N):
        df = df + abs(A[b] - (d + b))
    if df < bb:
        bb = df
    else:
        break

print(bb)

Submission status: Time Limit Exceeded

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

Ans = 0
pans = 0
low,high = -(10**5),10**9
for i in range(120):
    anslow,anshigh = 0,0
    for i in range(N):
        anslow += abs(A[i]-(i+low))
        anshigh += abs(A[i]-(i+high))
    if anshigh > anslow:
        high=(high+low)//2
    else:
        low=(high+low)//2
    Ans = min(anshigh,anslow)

print(Ans)