AtCoder Regular Contest 100 C – Linear Approximation をPython3で解く

Share

AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。

出典:
AtCoder Regular Contest 100 C – Linear Approximation

各点との差分の合計が最も小さくなるのは中央値になるという、マンハッタン距離の性質を知っていれば解きやすい問題。

# AtCoder Regular Contest 100 C - Linear Approximation
# https://atcoder.jp/contests/arc100/tasks/arc100_a
# tag: 数列 マンハッタン距離 最小値 事前変形 中央値

# 引かれる数が 1ずつ増えていくので、あらかじめ
# 引いておいた数列を作成しておく。

# すると、ある数列に対して距離の差分の合計が
# もっとも小さくなる一点を求める、という問題に帰着される。

# これはマンハッタン距離の差分の最小値なので、
# まず中央値を求め、後にその中央値との差分の合計を
# 求めればいい。

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

    # a, a-1, a-2 ... を作成
    converted = [a - i for i, a in enumerate(A)]

    # 中央値
    med = sorted(converted)[N//2]

    # 回答
    print(sum(abs(n - med) for n in converted))

main()
Share

コメントを残す

メールアドレスが公開されることはありません。