ARC225 D - Gap Swap (easy)

考え方

各状態に対して、$S$ の値を以下のように定義する。

• $S$ は、数列内の各数について以下の値の合計値である
• ある数が本来そこより $k$ 個右にいるべき場合、値は $k$
• ある数が本来そこより $k$ 個左にいるべき場合、値は $0$
• 正しい位置にいる場合も $0$

さて、コストを $c$ 払うと、距離 $c$ 離れた位置にある $2$ つの数を入れ替えることができる。
左へ動いた分は $S$ の値を減少させることがなく、右へ動いた分は最大で $c$ まで減少させられる。
よって、コストを $c$ 払ったときの $S$ の値の減少量は、大きくても $c$ である。

また、各数について、以下の文字を対応させて長さ $N$ の文字列を作る。

• ある数が本来そこより右にいるべき場合、'R'
• ある数が本来そこより左にいるべき場合、'L'
• 正しい位置にいる場合は 'N'

この文字列で、'N' 以外で最初に出現する文字は必ず 'R' である。
また、'N' 以外で最後に出現する文字は必ず 'L' である。
したがって、'N' を無視した場合に 'R' の次に 'L' があるところが少なくとも $1$ ヶ所ある。
この 'R' と 'L' の組にあたる部分に操作を行うと、払ったコストを $c$ とすると $S$ は必ず $c$ 減少する。

以上により、初期状態での $S$ の値を $S_0$ とすると、以下の $2$ つがわかった。

• 総コストは少なくとも $S_0$ かかる
• 総コスト $S_0$ である手順が必ず存在する

したがって、$S_0$ そのものが答えである。

計算量は、$O(N)$ である。

入力例1での動作

入力を受け取り、各要素から $1$ を引いて 0-indexed に直す。

n: 6
a: {5, 1, 2, 4, 3, 0}

各位置について、本来もっと右にあるべき値の移動距離を求める。

これらの合計は $5+1=6$ である。
したがって、答えは $6$ となる。

注意点

答えは、int 型からはみ出る。
long long 型を用いること。

別解

特になし。