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:
from functools import lru_cache
n = int(input())
a = list(map(int,input().split()))
left = -10**9
right = 10**9

@lru_cache(maxsize=100000)
def cal(num):
  tmp = 0
  for i in range(n):
    tmp += abs(a[i]-(num+(i+1)))
  return tmp
 

while abs(right-left)>1:
  mid = (right+left)//2
  
  if cal(mid-1)<cal(mid+1):
    ans = mid
    right = mid
  else:
    left = mid
print(min(cal(left),cal(right)))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
left = -10**9
right = 10**9
def cal(num):
  tmp = 0
  for i in range(n):
    tmp += abs(a[i]-(num+(i+1)))
  return tmp
 

while abs(right-left)>1:
  mid = (right+left)//2
  if cal(mid-1)<cal(mid+1):
    ans = mid
    right = mid
  else:
    left = mid
print(min(cal(left),cal(right)))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
left = -10**9
right = 10**9
minnum = 0
for i in range(n):
  minnum += abs(a[i]-(left+(i+1)))

ans = 0
def cal(num):
  global minnum
  tmp = 0
  for i in range(n):
    tmp += abs(a[i]-(num+(i+1)))
  return tmp
 

while abs(right-left)>1:
  mid = (right+left)//2
  if cal(mid-1)<cal(mid+1):
    ans = mid
    right = mid
  else:
    left = mid
print(min(cal(left),cal(right)))

Submission status: Time Limit Exceeded

Solution code:
import sys;      from decimal import Decimal
import math;     from itertools import combinations, product
import bisect;   from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def lcm(a: int, b: int) -> int: return (a * b) // math.gcd(a, b)

def binary_search(n, a):
    right = max(a) + 10 ** 9
    left = min(a) - 10 ** 9

    def calc(b):
        score = 0
        for i in range(n):
            score += abs(a[i] - (b + i + 1))
        return score

    while right - left > 1:
        middle = (right + left) // 2
        if calc(middle) < calc(middle + 1):
            right = middle
        else:
            left = middle
    
    return calc(right)

def Main():
    n = read_int()
    a = read_int_list()
    
    print(binary_search(n, a))
    

if __name__ ==  '__main__':
    Main()

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)]
#print(b)

s = sum(b)
m = int(s/n)
ans = float('inf')
if m<0:
  m = m-1
  for i in range(m, 1, 1):
    res = 0
    for j in range(n):
      res += abs(b[j]-i)
    ans = min(ans, res)
else:
  m = m+1
  for i in range(m+1):
    res = 0
    for j in range(n):
      res += abs(b[j]-i)
    ans = min(ans, res)
  
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)]
#print(b)

res1 = min(b)
res2 = max(b)
ans = float('inf')
for j in range(res1, res2+1, 1):
  res = 0
  for i in range(n):
    res += abs(b[i]-j)
    
  ans = min(ans, res)
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=list(map(int,input().split()))
d=sum(A)
for b in range(-max(A),max(A)):
    c=0
    for i in range(len(A)):
        c += abs(A[i]-(b+(i+1)))
    d=min(c,d)
print(d)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=list(map(int,input().split()))
d=sum(A)
e=sum(A)
for b in range(max(A)):
    c=0
    for i in range(len(A)):
        c += abs(A[i]-(b+(i+1)))
    d=min(c,d)
for b in range(-max(A),0,1):
    c=0
    for i in range(len(A)):
        c += abs(A[i]-(b+(i+1)))
    e=min(c,e)     
print(min(d,e))

Submission status: Time Limit Exceeded

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

# 平面座標上で、(i+1, a[i])の点と、直線y = x + bとのy方向への距離の合計を最小とするbの取り方

# bの候補
# (i+1, a[i])を通るような直線 : b = a[i] - (i+1)
bset = set()
for i in range(n):
    bset.add(a[i] - (i+1))

# 各bの候補について距離の合計を計算
ans = float("inf")
for b in bset:
    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:
# abc102_c.py
# https://atcoder.jp/contests/abc102/tasks/arc100_a

# C - Linear Approximation /
# 実行時間制限: 2 sec / メモリ制限: 1024 MB
# 配点 : 300点

# 問題文
# すぬけ君は、長さ Nの整数列 Aを持っています。
# すぬけ君は、整数 bを自由に選びます。 この時、Ai と b+i が離れているとすぬけ君は悲しいです。 
# より具体的には、すぬけ君の悲しさの値は、次の式で計算されます。 なおここで、abs(x) は xの絶対値を返す関数です。
#     abs(A1−(b+1))+abs(A2−(b+2))+...+abs(AN−(b+N))
# すぬけ君の悲しさの値の最小値を求めてください。

# 制約
#     1≤N≤2×105
#     1≤Ai≤109
#     入力はすべて整数である。

# 入力
# 入力は以下の形式で標準入力から与えられる。

# N
# A1 A2 ... AN

# 出力
# すぬけ君の悲しさの値の最小値を出力せよ。

# 入力例 1
# 5
# 2 2 3 5 5

# 出力例 1
# 2

# b=0とすれば、すぬけ君の悲しさの値は、abs(2−(0+1))+abs(2−(0+2))+abs(3−(0+3))+abs(5−(0+4))+abs(5−(0+5))=2 となります。 
# b をどのように選んでも、すぬけ君の悲しさの値を 2 未満にすることは出来ないので、答えは 2になります。

# 入力例 2
# 9
# 1 2 3 4 5 6 7 8 9

# 出力例 2
# 0

# 入力例 3
# 6
# 6 5 4 3 2 1

# 出力例 3
# 18

# 入力例 4
# 7
# 1 1 1 1 2 3 4

# 出力例 4
# 6


def calculation(lines):
    N = int(lines[0])
    values = list()
    for i, value in enumerate(map(int, lines[1].split(' '))):
        values.append(value-i)
    ma = max(values)
    mi = min(values)
    # print(f'ma=[{ma}]')
    # print(f'mi=[{mi}]')
    selected = None
    for i in range(mi, ma+1):
        s = 0
        for j in range(len(values)):
            s += abs(values[j] - i)
        if selected is None:
            selected = s
        elif selected > s:
            selected = s
    return [selected]


# 引数を取得
def get_input_lines(lines_count):
    lines = list()
    for _ in range(lines_count):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['5', '2 2 3 5 5']
        lines_export = [2]
    if pattern == 2:
        lines_input = ['9', '1 2 3 4 5 6 7 8 9']
        lines_export = [0]
    if pattern == 3:
        lines_input = ['6', '6 5 4 3 2 1']
        lines_export = [18]
    if pattern == 4:
        lines_input = ['7', '1 1 1 1 2 3 4']
        lines_export = [6]
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    if len(args) == 1:
        mode = 0
    else:
        mode = int(args[1])
    return mode


# 主処理
def main():
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines(2)
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')


# 起動処理
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

nums = list(map(int, input().split()))
nums = [num - (i + 1) for i, num in enumerate(nums)]

# print(nums)


def compute_sour(num, b):
    return abs(num - b)


usable_nums = sorted(set(nums))
start = usable_nums[0]
end = usable_nums[-1]

# print(start, end)

min_ans = float('inf')
for i in range(start, end + 1):
    ans = []
    for num in nums:
        ans.append(compute_sour(num, i))
    min_ans = min(min_ans, sum(ans))
print(min_ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import math
import copy
input = sys.stdin.readline
 
N = int(input())
A = np.array(list(map(int,input().split())))
r = np.array(list(range(1,N+1)))
B = np.array(sorted(A-r))
bmin = B[N*2//5]
bmax = B[N*3//5]
ans = float('inf')
for bi in range(bmin,bmax+1):
    ans = min(ans,sum(list(map(abs,B - bi))))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import math
import copy
input = sys.stdin.readline
 
N = int(input())
A = np.array(list(map(int,input().split())))
r = np.array(list(range(1,N+1)))
B = np.array(sorted(A-r))
bmin = B[N//4]
bmax = B[N*3//4]
ans = float('inf')
for bi in range(bmin,bmax+1):
    ans = min(ans,sum(list(map(abs,B - bi))))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import math
import copy
input = sys.stdin.readline
 
N = int(input())
A = np.array(list(map(int,input().split())))
r = np.array(list(range(1,N+1)))
B = A-r
ans = float('inf')
for bi in range(min(B),max(B)+1):
    ans = min(ans, sum(list(map(abs,B - bi))))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
 
N = int(input())
A = list(map(int,input().split()))
bmin = float('inf')
bmax = float('inf')*-1
for i in range(N):
    bmin = min(bmin,A[i]-i-1)
    bmax = max(bmax,A[i]-i-1)
sadness = float('inf')
for bi in range(bmin,bmax+1):
    ans = 0 
    for i in range(N):
        ans += abs(A[i]-i-1-bi)
    sadness = min(sadness,ans)
print(sadness)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N = int(input())
    A = list(map(int, input().split()))
    A_i = [A[i] - i - 1 for i in range(N)]
    ans = 10 ** 9
    for i in range(min(A_i), max(A_i) + 1):
        sums = 0
        for a in A_i:
            sums += abs(a - i)
        ans = min(ans, sums)
    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
A = list(map(int,input().split()))
for i in range(N):
    if i == 0:
        b_max = A[i]-i-1
        b_min = A[i]-i-1
    else:
        b_max = max(A[i]-i-1,b_max)
        b_min = min(A[i]-i-1,b_min)


for i in range(b_min,b_max+1):
    a=0
    if i == b_min:
        ns = sum([abs(A[j]-((j+1)+i)) for j in range(N)])
    a =  sum([abs(A[j]-((j+1)+i)) for j in range(N)])
    if ns>= a:
        ns = a
    else:
        break
print(ns)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(a)-i-1 for i,a in enumerate(input().split(),1)]
A.sort()
b = sum(A)//len(A)
d = sum(A)%len(A)
c = 10**9
for j in range(b-d, b+d+1):
    k = sum(map(lambda x:abs(x-j), A))
    c = min(c,k)
print(c)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(a)-i-1 for i,a in enumerate(input().split(),1)]
a = max(A)
b = min(A)
c = 10**9
for j in range(b,a+1):
    k = sum(map(lambda x:abs(x-j), A))
    c = min(k,c)
print(c)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int, input().split()))
ANS = [A[i] - (i+1) for i in range(n)]
ANS.sort()
ans = sum((ANS[i]-ANS[0]) for i in range(n))
for b in range(ANS[0],ANS[n-1]+1):
  k = sum(abs(ANS[i]-b) for i in range(n))
  if ans < k:
    print(ans)
    exit()
  else:
    ans = min(k,ans)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def get_sad(A, b):
    sad = sum(
        [
            abs(a - (b + (i + 1)))
            for i, a in enumerate(A)
        ]
    )
    return sad


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

# check

sad = get_sad(A, 0)
before = sad
b = 1
while sad <= before:
    before = sad
    sad = min(get_sad(A, b), get_sad(A, -b))
    b += 1
else:
    print(before)

Submission status: Time Limit Exceeded

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

B = [0]*n
for i in range(n):
    B[i] = A[i] - (i+1)

B.sort()
# print(B)
bmin = min(B)
bmax = max(B)
ans = 10**18
for b in range(bmin,bmax+1):
    ret = 0
    for bi in B:
        ret += abs(bi-b)
    ans = min(ans, ret)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = 0
nans = 0
for i in range(10**9):
    for j in range(n):
        ans += abs(a[j]-i-j)
    if ans <= nans:
        nans =ans
print(nans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = float("inf")
m = max(a)
for b in range(-m,m+1):
    x = 0
    for i in range(n):
        x+=abs(a[i]-(b+i+1))
    ans = min(ans,x)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = np.array(lr())
A -= np.arange(1, N+1)
answer = 10 ** 15
for i in range(N):
    temp = np.abs(A - A[i]).sum()
    if temp < answer:
        answer = temp

print(answer)

Submission status: Time Limit Exceeded

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

Bs = set()
for i in range(N):
    Bs.add(A[i] - (i+1))

mins = sum(A)
for b in Bs:
    s = 0
    for i, a in enumerate(A):
        s += abs(a - (b+i+1))
    mins = min(mins, s)
print(mins)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
Min = 10**9+1
for i in range(n):
    st = a[i]
    mmin = 0
    for j in range(n):
        mmin += abs(a[j]-(st+(j-i)))
    Min = min(mmin,Min)
print(Min)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import numpy as np
N = int(input())
A = list(map(int, input().split()))

A_diff = np.array([a - i for i, a in enumerate(A, 1)])

ans = float("inf")
for i in range(N):
    A_diff_cp = A_diff.copy()
    A_diff_cp += -1 * A_diff[i]
    ans = min(ans, sum(np.abs(A_diff_cp)))

print(ans) # O(N ** 2なので無理ぽい)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
lst=list(map(int,input().split()))
minu = min(lst)
maxi = max(lst)
sad = 1000000000000
for i in range(minu-maxi, maxi+minu+1):
  temp = 0
  for j in range(n):
    temp += abs(lst[j] - i - (j+1))
  if temp < sad:
    sad = temp
print(sad)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import collections

N = int(input())
A = list(map(int, input().split()))
ans = 10**18
dists_A2i = []

for i in range(1, N+1):
    dist_A2i = A[i-1] - i
    dists_A2i.append(dist_A2i)

c = collections.Counter(dists_A2i)

max_c_list = [key for key, value in c.items() if value == max(c.values())]

dists_A2i = np.array(dists_A2i)

for max_c in max_c_list:
    check_dists_A2i = abs(dists_A2i - max_c)
    ans = min(ans, sum(check_dists_A2i))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
class SplayNode:
    """Splay木のノードを定義
    メンバ変数: 値、サイズ、親へのポインタ、左右の子へのポインタ
    """
    def __init__(self, val):
        self.val = val
        self.size = 1
        self.parent, self.right, self.left = None, None, None


class SplayTree:
    """Splay木を定義"""
    def __init__(self):
        self.root = None

    def __getitem__(self, ind: int):  # O(logN)
        return self.get_ptr(ind, self.root).val
        
    def __setitem__(self, ind: int, val):  # O(logN)
        ptr = self.get_ptr(ind, self.root)
        ptr.val = val

    def __len__(self):  # O(1)
        return self.root.size if self.root is not None else 0

    def update(self, ptr):
        """部分木の情報を更新する"""
        ptr.size = 1
        if ptr.left is not None:
            ptr.size += ptr.left.size
        if ptr.right is not None:
            ptr.size += ptr.right.size

    def state(self, ptr):
        """スプレー操作を行うときの状況判定
        親が存在しない: 0
        左の兄弟が存在する: 1
        右の兄弟が存在する: -1
        """
        if ptr.parent is None:
            return 0
        if ptr.parent.left == ptr:
            return 1
        if ptr.parent.right == ptr:
            return -1

    def splay(self, ptr):
        """ptrが根になるようにスプレー操作を行う"""
        while self.state(ptr) != 0:
            if self.state(ptr.parent) == 0:
                # zigステップ
                self.rotate(ptr)
            elif self.state(ptr) == self.state(ptr.parent):
                # zig-zigステップ
                self.rotate(ptr.parent)
                self.rotate(ptr)
            else:
                # zig-zagステップ
                self.rotate(ptr)
                self.rotate(ptr)
        self.root = ptr

    def rotate(self, ptr):
        """木の回転を行う"""
        p = ptr.parent
        pp = p.parent
        if p.left == ptr:
            c = ptr.right
            ptr.right = p
            p.left = c
        else:
            c = ptr.left
            ptr.left = p
            p.right = c
        if pp is not None and pp.left == p: pp.left = ptr
        if pp is not None and pp.right == p: pp.right = ptr
        ptr.parent = pp
        p.parent = ptr
        if c is not None:
            c.parent = p
        self.update(p)
        self.update(ptr)

    def get_ptr(self, ind, root):
        """ind番目のポインタを取得する"""
        ptr = root
        while True:
            if ptr.left is None:
                l_size = 0
            else:
                l_size = ptr.left.size
            if ind < l_size:
                ptr = ptr.left
            if ind == l_size:
                self.splay(ptr)
                return ptr
            if ind > l_size:
                ptr = ptr.right
                ind = ind - l_size - 1

    def merge(self, lroot, rroot):
        if lroot is None:
            self.root = rroot
            return rroot
        if rroot is None:
            self.root = lroot
            return lroot
        lroot = self.get_ptr(lroot.size - 1, lroot)
        lroot.right = rroot
        rroot.parent = lroot
        self.update(lroot)
        return lroot
      
    def split(self, left_cnt, root):
        if left_cnt == 0:
            return None, root
        if left_cnt == root.size:
            return root, None
        root = self.get_ptr(left_cnt, root)
        lroot = root.left
        rroot = root
        rroot.left = None
        lroot.parent = None
        self.update(rroot)
        return lroot, rroot
      
    def insert(self, ind, val):
        """ind番目の値valの要素を挿入する"""
        lroot, rroot = self.split(ind, self.root)
        new_ptr = SplayNode(val)
        self.merge(self.merge(lroot, new_ptr), rroot)
    
    def delete(self, ind):
        """indの要素を削除する"""
        root = self.get_ptr(ind, self.root)
        lroot = root.left
        rroot = root.right
        if lroot is not None:
            lroot.parent = None
        if rroot is not None:
            rroot.parent = None
        root.relf = None
        root.left = None
        self.update(root)
        return self.merge(lroot, rroot), root

    def add(self, val):
        if self.root is None:
            self.insert(0, val)
            return
        ptr = self.root 
        ind = 0
        while True:
            if val < ptr.val:
                if ptr.left is None:
                    self.insert(ind, val)
                    return
                ptr = ptr.left
            else:
                ind += 1
                if ptr.left is not None:
                    ind += ptr.left.size
                if ptr.right is None:
                    self.insert(ind, val)
                    return
                ptr = ptr.right


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

sp = SplayTree()
for i in range(n)[::-1]:
    sp.insert(0, a[i])
for i in range(n):
    sp[i] = sp[i] - (i + 1)

ave = sorted([sp[i] for i in range(n)])[n // 2]
ans = 0

for i in range(n):
  ans += abs(sp[i] - ave)
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class SplayNode:
    """Splay木のノードを定義
    メンバ変数: 値、サイズ、親へのポインタ、左右の子へのポインタ
    """
    def __init__(self, val):
        self.val = val
        self.size = 1
        self.parent, self.right, self.left = None, None, None


class SplayTree:
    """Splay木を定義"""
    def __init__(self):
        self.root = None

    def __getitem__(self, ind: int):  # O(logN)
        return self.get_ptr(ind, self.root).val
        
    def __setitem__(self, ind: int, val):  # O(logN)
        ptr = self.get_ptr(ind, self.root)
        ptr.val = val

    def __len__(self):  # O(1)
        return self.root.size if self.root is not None else 0

    def update(self, ptr):
        """部分木の情報を更新する"""
        ptr.size = 1
        if ptr.left is not None:
            ptr.size += ptr.left.size
        if ptr.right is not None:
            ptr.size += ptr.right.size

    def state(self, ptr):
        """スプレー操作を行うときの状況判定
        親が存在しない: 0
        左の兄弟が存在する: 1
        右の兄弟が存在する: -1
        """
        if ptr.parent is None:
            return 0
        if ptr.parent.left == ptr:
            return 1
        if ptr.parent.right == ptr:
            return -1

    def splay(self, ptr):
        """ptrが根になるようにスプレー操作を行う"""
        while self.state(ptr) != 0:
            if self.state(ptr.parent) == 0:
                # zigステップ
                self.rotate(ptr)
            elif self.state(ptr) == self.state(ptr.parent):
                # zig-zigステップ
                self.rotate(ptr.parent)
                self.rotate(ptr)
            else:
                # zig-zagステップ
                self.rotate(ptr)
                self.rotate(ptr)
        self.root = ptr

    def rotate(self, ptr):
        """木の回転を行う"""
        p = ptr.parent
        pp = p.parent
        if p.left == ptr:
            c = ptr.right
            ptr.right = p
            p.left = c
        else:
            c = ptr.left
            ptr.left = p
            p.right = c
        if pp is not None and pp.left == p: pp.left = ptr
        if pp is not None and pp.right == p: pp.right = ptr
        ptr.parent = pp
        p.parent = ptr
        if c is not None:
            c.parent = p
        self.update(p)
        self.update(ptr)

    def get_ptr(self, ind, root):
        """ind番目のポインタを取得する"""
        ptr = root
        while True:
            if ptr.left is None:
                l_size = 0
            else:
                l_size = ptr.left.size
            if ind < l_size:
                ptr = ptr.left
            if ind == l_size:
                self.splay(ptr)
                return ptr
            if ind > l_size:
                ptr = ptr.right
                ind = ind - l_size - 1

    def merge(self, lroot, rroot):
        if lroot is None:
            self.root = rroot
            return rroot
        if rroot is None:
            self.root = lroot
            return lroot
        lroot = self.get_ptr(lroot.size - 1, lroot)
        lroot.right = rroot
        rroot.parent = lroot
        self.update(lroot)
        return lroot
      
    def split(self, left_cnt, root):
        if left_cnt == 0:
            return None, root
        if left_cnt == root.size:
            return root, None
        root = self.get_ptr(left_cnt, root)
        lroot = root.left
        rroot = root
        rroot.left = None
        lroot.parent = None
        self.update(rroot)
        return lroot, rroot
      
    def insert(self, ind, val):
        """ind番目の値valの要素を挿入する"""
        lroot, rroot = self.split(ind, self.root)
        new_ptr = SplayNode(val)
        self.merge(self.merge(lroot, new_ptr), rroot)
    
    def delete(self, ind):
        """indの要素を削除する"""
        root = self.get_ptr(ind, self.root)
        lroot = root.left
        rroot = root.right
        if lroot is not None:
            lroot.parent = None
        if rroot is not None:
            rroot.parent = None
        root.relf = None
        root.left = None
        self.update(root)
        return self.merge(lroot, rroot), root

    def add(self, val):
        if self.root is None:
            self.insert(0, val)
            return
        ptr = self.root 
        ind = 0
        while True:
            if val < ptr.val:
                if ptr.left is None:
                    self.insert(ind, val)
                    return
                ptr = ptr.left
            else:
                ind += 1
                if ptr.left is not None:
                    ind += ptr.left.size
                if ptr.right is None:
                    self.insert(ind, val)
                    return
                ptr = ptr.right


from statistics import median

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

sp = SplayTree()
for i in range(n):
    sp.insert(i, a[i])
for i in range(n):
    sp[i] = sp[i] - (i + 1)

ave = int(median([sp[i] for i in range(n)]))
ans = 0

for i in range(n):
  ans += abs(sp[i] - ave)
  
print(ans)

Submission status: Time Limit Exceeded

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

import sys
import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n = ii()
    L = lmi()
    L_dec = [elm - (i + 1) for i, elm in enumerate(L)]
    # ternary search
    left = min(L_dec) - 1
    right = max(L_dec) + 1
    while right - left > 2:
        m_l = (2 * left + right) // 3
        m_r = (left + 2 * right) // 3
        tmp_l = sum([abs(m_l - elm) for elm in L_dec])
        tmp_r = sum([abs(m_r - elm) for elm in L_dec])
        # print(f"{m_l} {tmp_l}, {m_r} {tmp_r}")
        if tmp_l >= tmp_r:
            left = m_l
        else:
            right = m_r
    # print(f"left {left} right {right}")
    
    print(min([sum([abs(j - elm) for elm in L_dec]) for j in range(left, right + 1)]))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

# https://atcoder.jp/contests/abc102/tasks/arc100_a
# 13:03-13:20


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

    B = [A[i]-i for i in range(N)]
    
    b = sum(B) // N

    def sumb(x):
        return sum([abs(b-x) for b in B])
    
    dif = 0
    while sumb(b-(dif+1)) < sumb(b-dif):
        dif += 1
    ans1 = sumb(b-dif)
    
    dif = 0
    while sumb(b+(dif+1)) < sumb(b+dif):
        dif += 1
    ans2 = sumb(b+dif)

    return min(ans1, ans2)


print(main())

Submission status: Time Limit Exceeded

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

b_low=-1*(10**20)
b_high=10**20
b_low_d=sum([abs(a[i]-(b_low+2+i)) for i in range(n)])-sum([abs(a[i]-(b_low+1+i)) for i in range(n)])
b_high_d=sum([abs(a[i]-(b_high+2+i)) for i in range(n)])-sum([abs(a[i]-(b_high+1+i)) for i in range(n)])

while b_high-b_low>10:
  b_tmp=(b_low+b_high)//2
  b_tmp_d=sum([abs(a[i]-(b_tmp+2+i)) for i in range(n)])-sum([abs(a[i]-(b_tmp+1+i)) for i in range(n)])
  if b_tmp_d>0:
    b_high=b_tmp
  else:
    b_low=b_tmp

ans=10**20
for j in range(b_low,b_high):
  ans=min(ans,sum([abs(a[i]-(j+2+i)) for i in range(n)]))

print(ans)

Submission status: Time Limit Exceeded

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


def f(x):
    v = 0
    for i in range(len(A)):
        v += abs(A[i] - (x + i + 1))
    return v


left = -(10**9 + 2 * 10**5)
right = 10**9 + 2 * 10**5
v = 10**18
while left + 1 < right:
    x = (left + right) // 2
    # print('left right x', left, right, x)
    a = f(x)
    v = min(v, a)
    if a <= f(x + 1):
        right = x
    elif f(x - 1) >= a:
        left = x

# ans = f(left)
# print('left ans v', left, ans, v)
print(v)

Submission status: Time Limit Exceeded

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

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

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

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

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

if __name__ == "__main__":
   main()