ABC092 C - Traveling Plan - ツバサの備忘録

解法

毎回愚直に計算するともちろん間に合わないので何か工夫をする必要があります。そこで登場するのが累積和です。
まず、始点と終点も観光スポットとみなし、 $A_{0} = A_{N+1} = 0$ としておきます。

$s[i] =$ 観光スポット $0$ から $i$ まで順番に行ったときにかかる金額の総和

とします。
これは、
$\displaystyle s[i] = \sum_{k=1}^{i} |A_{k} - A_{k-1} |$
という計算をすることで求めることができます。しかし、 $s[i]$ を求めるのに、 $s[i-1]$ を利用すると、
$\displaystyle s[i] = \sum_{k=1}^{i-1} |A_{k} - A_{k-1} | + |A_{i} - A_{i-1} |$
であることから、
$s[i] = s[i-1] + |A_{i} - A_{i-1} |$
というように変形できます。
これにより、 $s[i]$ を $O(1)$ で、 $1$ から $N+1$ すべてについての $s[i]$ を求めるのに $O(N)$ で計算できるようになりました。
さて、 $s[i]$ は、観光スポット $0$ から、という区間についてしか計算できません。 $[i,j]$ という区間についてのみ移動した場合の金額を計算するにはどうすればよいかというと、
$\displaystyle \sum_{k=i+1}^{j} |A_{k} - A_{k-1} |$
という計算ができればよいので、式を変形すると
$\displaystyle \sum_{k=0}^{j} |A_{k} - A_{k-1} | - \sum_{k=0}^{i} |A_{k} - A_{k-1} |$
となります。
よって、始点を $0$ にした計算式に置き換えることができたので、 $s[i]$ を利用して、
$s[j] - s[i]$
と計算すればよいことになります。

さて、下準備ができたので、 $i$ 番目のスポットに行かない場合の金額の計算を行います。
このとき、移動ルートは次のようになり、それぞれ以下のようにして計算できます。