ABC102 C - Linear Approximation
備忘録
問題
回答
import sys import os import math import string ii = lambda: int(sys.stdin.buffer.readline().rstrip()) il = lambda: list(map(int, sys.stdin.buffer.readline().split())) fl = lambda: list(map(float, sys.stdin.buffer.readline().split())) iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)] iss = lambda: sys.stdin.buffer.readline().decode().rstrip() sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split())) isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)] lcm = lambda x, y: x * y / math.gcd(x, y) MOD = 10 ** 9 + 7 MAX = float('inf') def main(): if os.getenv("LOCAL"): sys.stdin = open("input.txt", "r") N = ii() A = il() di = {} for i, a in enumerate(A): di[i] = - a + i + 1 di = sorted(di.items(), key=lambda x: x[1]) md = di[len(di) // 2][1] ret = 0 for d in di: ret += abs(md - d[1]) print(ret) if __name__ == '__main__': main()
考え方
整数列A
のindex
と絶対値をとる式の一部を計算しておき、
整数b
で悲しさを算出する。
悲しさを計算する式abs(a - (b + index))
を展開し、
整数b
以外について整数列A
の値とindex
は自明なので先に計算しておく。
その後、計算した値から、
全ての値の最小値を求めることが出来る整数b
を決める。
先に計算しておいた値と整数b
の計算結果を絶対値として、
全て加算すると回答を得られる。
全ての値を最小にすることが出来る整数b
は、
(感覚的に)全ての値の中央値なので、
計算した値をソートし、配列の中央の値を整数b
とした。