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: Accepted

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

def f(x):
    sum = 0
    for i in alta:
        sum += abs(x - i)
    return sum

left, right = 0, max(alta)
while abs(right - left) > 3:
    mid1 = (right * 2 + left) // 3 + 1
    mid2 = (right + left * 2) // 3
    if f(mid1) >= f(mid2):
        # 上限を下げる（最小値をとるxはもうちょい下めの数だな）
        right = mid1
    else:
        # 下限を上げる（最小値をとるxはもうちょい上めの数だな）
        left = mid2
ans = float('inf')
for i in range(left, right + 1):
    ans = min(ans, f(i))
print(ans)

Submission status: Accepted

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

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

A.sort()

tmp = sum(A) - n * A[0]
m = tmp

for i in range(n-1):
    tmp += (A[i+1]-A[i]) * (2*i+2-n)
    m = min(m, tmp)

print(m)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

N = ii()
A = li()

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

A = sorted(A)

if not N % 2:
    num = int((A[N//2] + A[N//2-1]) // 2)
else:
    num = A[N//2]
ans = 0
for i in range(N):
    ans += abs(num - A[i])

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import collections

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

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

dists_A2i = np.array(dists_A2i)
dists_median = np.median(dists_A2i)
dists_A2i = abs(dists_A2i - dists_median)
ans = sum(dists_A2i)
print(int(ans))

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


# ワーシャルフロイド (任意の2頂点の対に対して最短経路を求める)
# 計算量n^3 (nは頂点の数)
def warshall_floyd(d, n):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定



# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
n = int(input())
a = list(map(int, input().split()))

a2 = sorted([a[i] - i for i in range(n)])
median = a2[n // 2]
ans = sum([abs(a2[i] - median) for i in range(n)])
print(ans)

Submission status: Accepted

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: Accepted

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):
    sp.insert(i, 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: Accepted

Solution code:
def main():
    n, *a, = map(int, open(0).read().split())
    a = [x - i for i, x in enumerate(a, 1)]
    a.sort()
    if n % 2 == 0:
        ans = sum(a[n // 2:]) - sum(a[:n // 2])
    else:
        ans = sum(a[n // 2 + 1:]) - sum(a[:n // 2])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from statistics import median

    n, *a, = map(int, open(0).read().split())
    a = [x - i for i, x in enumerate(a, 1)]
    a.sort()
    m = int(median(a))

    ans = sum([abs(x - m) for x in a])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc102/submissions/7991084

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

def abc102_c():
    N = int(readline())
    A = np.array(read().split(), dtype=np.int64)

    # b=0として変形する
    B = A - np.arange(1, N+1)
    # 中央値が0になるよう高さ調整する
    B.sort()
    x = B[N//2]
    # 絶対値の合計をとる
    ans = np.abs(B - x).sum()
    print(ans)

abc102_c()

Submission status: Accepted

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

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

b = a[(N - 1) // 2]

for i in range(N):
    a[i] = abs(a[i] - b)

print(sum(a))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
  a[i] -= i + 1
a = sorted(a)
med = a[n // 2]
ans = 0
for x in a:
  ans += abs(x - med)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
z = list(map(int, input().split()))
a = sorted(t - i - 1 for i, t in enumerate(z))
print(sum(abs(t - a[n//2]) for t in a))

Submission status: Accepted

Solution code:
import math
from statistics import median

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

ai = [a[i] - (i+1) for i in range(n)]

b = round((median(ai)))
result = sum([abs(ai[i] - b) for i in range(n)])
print(result)

Submission status: Accepted

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

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

tmp = int(statistics.median(A))

ans = 0
for i, a in enumerate(A):
    ans += abs(a - tmp)

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
for i in range(n):
    A[i]-=i+1
A.sort()
c=A[n//2]
ans=0
for a in A:
    ans+=abs(a-c)
print(ans)

Submission status: Accepted

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

c = [a[i]-i-1 for i in range(n)]
ans = 0
c.sort()
#print(c)
if n%2 == 1:
    b = c[n//2]
    for i in range(n):
        ans += abs(c[i]-b)
else:
    b = (c[n//2]+c[n//2-1])//2
    #print(b)
    for i in range(n):
        ans += abs(c[i]-b)
print(ans)

Submission status: Accepted

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 = sorted([A[i]-i for i in range(N)])
    
    b = B[N//2]

    return sum([abs(B[i]-b) for i in range(N)])


print(main())

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    N=int(readline())
    A=list(map(int,readline().split()))

    B=[0]*N
    for i in range(N):
        B[i]=A[i]-i
    B.sort()
    if N%2==1:
        b=B[N//2]
    else:
        b=(B[N//2-1]+B[N//2])//2
    
    res=0
    for i in range(N):
        res+=abs(B[i]-b)

    print(res)
if __name__=="__main__":
    main()

Submission status: Accepted

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

arr=sorted([a[i]-i-1 for i in range(n)])

if len(arr)%2==0:
  tmp=[arr[len(arr)//2-1],arr[len(arr)//2]]
else:
  tmp=[arr[len(arr)//2]]

ans=10**20
for b in tmp:
  ans=min(ans,sum([abs(a[i]-b-i-1) for i in range(n)]))
print(ans)

Submission status: Accepted

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

b_low=-1*(10**10)
b_high=10**10
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: Accepted

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

b_low=-1*(10**12)
b_high=10**12
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: Accepted

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

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

A.sort()

b = A[N//2]

ans = 0
for i in range(N):
    ans = ans + abs(A[i]-b)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
B=[]
for i,ai in enumerate(a,start=1):
  B.append(ai-i)
c=sorted(B)
b=c[len(c)//2]

ans=0
for i in B:
  ans+=abs(i-b)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

a2 = [a[i] - i - 1 for i in range(n)]
mean = sum(a2) / len(a2)
median = np.median(np.array(a2))
b = np.floor(median)
a3 = sum([abs(a2[i] - b) for i in range(n)])
b = np.ceil(median)
a4 = sum([abs(a2[i] - b) for i in range(n)])
print(int(min(a3, a4)))

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
list_ai = list(map(int,input().split()))
a1 = np.array(list_ai)-np.arange(1,N+1)
median1 = int(np.floor(np.median(a1)))
ans = np.sum(np.abs(a1-median1))
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
list_ai = list(map(int,input().split()))
list1 = [x-(i+1) for i,x in enumerate(list_ai)]
a1 = np.array(list1)
median1 = int(np.floor(np.median(a1)))
ans = np.sum(np.abs(a1-median1))
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
list_ai = list(map(int,input().split()))
list1 = [x-(i+1) for i,x in enumerate(list_ai)]
a1 = np.array(list1)
median1 = int(np.floor(np.median(a1)))
ans = sum(abs(x-median1) for x in list1)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
idx = [i for i in range(1, n+1)]
a = [int(inp) - i for inp, i in zip(input().split(), idx)]
a.sort()
if n % 2 == 0:
    med = (a[(n-2)//2] + a[(n-2)//2+1])//2
else:
    med = a[(n-1)//2]
ans = 0
for ai in a:
    ans += max(ai-med, -ai+med)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = sorted([A[i] - i - 1 for i in range(len(A))])
# print('B', B)


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


if len(B) % 2 == 0:
    b1 = B[len(B) // 2 - 1]
    b2 = B[len(B) // 2]
    ans = min(f(b1), f(b2))
else:
    b = B[len(B) // 2]
    ans = f(b)
print(ans)

Submission status: Accepted

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

b = sorted(a)
if n % 2 != 0:
    b = b[n // 2]
else:
    b = (b[n // 2] + b[n // 2 - 1]) // 2

a = [abs(a[i] - b) for i in range(n)]
ans = sum(a)
print(ans)

Submission status: Accepted

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

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

a.sort()

mid = statistics.median_low(a)
mid1 = statistics.median_high(a)
ans = [0,0]

for i, aa in enumerate(a):
    ans[0] += abs(aa - mid)
    ans[1] += abs(aa - mid1)
print(min(ans))

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
a_ls = list(map(int, input().split()))
diff_ls = [a - i for i, a in enumerate(a_ls,1)]
diff_ls.sort()
med = int(np.median(diff_ls))
ans = 0
for diff in diff_ls:
    ans += abs(diff - med)
print(ans)

Submission status: Accepted

Solution code:

n=int(input())
a=list(map(int,input().split()))
b=[0]*n
for i in range(n):
    b[i]=a[i]-(i+1)

b.sort()

b2=b[n//2]

bsum=0
for i in range(n):
    bsum+=abs(b[i]-b2)
    
bsum2=0
for i in range(n):
    bsum2+=abs(b[i]-b2-1)

print(min(bsum,bsum2))

Submission status: Accepted

Solution code:
n = int(input())
x = list(map(int,input().split()))
for i in range(n):
    x[i]-=i+1
x.sort()
if n%2==0:
    b = (x[n//2-1]+x[n//2])//2
else:
    b = x[(n-1)//2]
ans=0
for i in range(n):
    ans+=abs(x[i]-b)
print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

def main():
    N = int(readline())
    A = list(map(int, readline().rstrip().split()))
    Ai = [a-i-1 for i, a in enumerate((A))]
    Ai.sort()
    if N % 2 == 1:
        b = Ai[N//2]
    else:
        b = (Ai[N//2-1] + Ai[N//2]) / 2

    print(int(sum([abs(a-b) for a in Ai])))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

A -= np.arange(N)
A.sort()

x = A[N//2]
answer = np.abs(A - x).sum()
print(answer)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
  a[i]-=i
a.sort()
b=(a[n//2]+a[(n-1)//2])//2
print(sum(abs(i-b) for i in a))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
AA = []
for i in range(N):
    AA.append(A[i]-(i+1))
median = sorted(AA)[N//2]
ans = 0
for i in range(N):
    ans += abs(AA[i]-median)
print(ans)

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    A = list(map(int,input().split()))
    B = []
    for i in range(1,N+1):
        B.append(A[i-1] - i)
    B.sort()
    b = 0
    if N % 2 == 0:
        b = (B[N//2] + B[N//2-1]) // 2
    else:
        b = B[N//2]
    
    ans = 0
    for elem in B:
        ans += abs(elem - b)
    
    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import math

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

_A = [A[i] - (i + 1) for i in range(len(A))]
_A.sort()
median = _A[math.floor(len(A) / 2)]

sadness = 0
for i in range(len(A)):
    sadness += abs(A[i] - (i + 1 + median))

print(sadness)

Submission status: Accepted

Solution code:
import math

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

_A = []
for i in range(len(A)):
    _A.append(A[i] - (i + 1))
_A.sort()
median = _A[math.floor(len(A) / 2)]

sadness = 0
for i in range(len(A)):
    sadness += abs(A[i] - (i + 1 + median))

print(sadness)

Submission status: Accepted

Solution code:
import math
n = int(input())
lst = list(map(int, input().split()))

res = 0
lst2 = [0]*n
for i in range(n):
  lst2[i] = lst[i] - i
lst2.sort()

p = lst2[n//2]
q = lst2[n//2-1]
ps = qs = 0
for i in range(n):
  ps += abs(lst[i] - (p+i))
  qs += abs(lst[i] - (q+i))
print(min(ps, qs))

Submission status: Accepted

Solution code:
n=int(input())
l=sorted([v-i-1 for i,v in enumerate(list(map(int,input().split())))])
if n%2:
    m=l[n//2]
else:
    m=(l[n//2]+l[n//2-1])/2
print(int(sum(abs(m-v) for v in l)))

Submission status: Accepted

Solution code:
from statistics import median
n = int(input())
A = list(map(int, input().split()))
B = [(A[i]-(i+1)) for i in range(n)]

def calc_sad(b):
  ret = 0
  for i in range(n):
    ret += abs(B[i]-b)
  return ret

b = median(B)
sad = int(calc_sad(b))
print(sad)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, A: "List[int]"):
    s = sorted(Ai - i - 1 for i, Ai in enumerate(A))
    b = s[N // 2]
    print(sum(abs(Ai - i - 1 - b) for i, Ai in enumerate(A)))


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]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
aa = []
for i in range(n):
    aa.append(a[i]-(i+1))
b = (sorted(aa)[n//2])

ans = 0
for i in range(n):
    ans += abs(a[i]-(b+i+1))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
aa = []
for i in range(n):
    aa.append(a[i]-i)
b = (sorted(aa)[n//2])

ans = 0
for i in range(n):
    ans += abs(a[i]-(b+i))
print(ans)

Submission status: Accepted

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

x = sorted(a - i - 1 for i, a in enumerate(A))
mid = x[N//2] if N % 2 else (x[N//2] + x[N//2-1]) // 2
ans = sum(abs(xi - mid) for xi in x)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = sorted([a-i-1 for i, a in enumerate(map(int, input().split()))])

med_A = A[n//2]
ans = sum([abs(a-med_A) for a in A])

print(ans)