AtCoder Beginner Contest 264 D問題 "redocta".swap(i,i+1)
問題
提出解答
問題の概要
の並び替え
が与えられる.
に対して隣接する文字の入れ替えを行い
を
にする場合, 最低でも何回入れ替えなければならないか.
制約
は
の並び替え
解法
に対して,
をそれぞれ
に置き換えた整数列を
とする.
すると, 問題は の隣接項の入れ替えにより
を昇順にするための入れ替えの最小回数を求めよ.
この問題は に対するバブルソートでの入れ替えの回数と一致する. そして, このような回数は転倒数といわれており, 以下で定義される.
転倒数
長さが の整数列
の転倒数
を以下で定義する.
- 以下を満たす整数の組
の個数:
かつ
このとき, 定義通りに転倒数を計算すると である. 今回の問題では
なので, 定義通りの愚直計算で十分高速である.