【精進記録】AtCoder Beginner Contest 092 C - Traveling Plan

問題

beta.atcoder.jp

解法

しばらく考えて解けなかったので解説を見てAC．

本来の計画の総コストを計算し，取りやめた地点iについて，地点i-1からiへ向かうコストとiから地点i+1へ向かうコストを引いた後に，地点i-1からi+1へのコストを足せば良い．

入力例1のi=2の場合を図示して見た．

コード

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

A.insert(0,0)
A.append(0)

S = 0

for i in range(1,N+2):
    S += abs(A[i]-A[i-1])

for i in range(1,N+1):
    print(S + abs(A[i-1]-A[i+1]) - abs(A[i-1]-A[i]) - abs(A[i]-A[i+1]))

コメント

難しく考えすぎていたのがよくなかった．
単純にできる方法から順に考えていくように気をつけたい．

とりあえず数式で考えたり図示するとわかりやすくなりそう．