Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 264 D問題 "redocta".swap(i,i+1)

AtCoder ABC ABC264 D問題 400 pts

問題

提出解答

問題の概要

${\tt atcoder}$ の並び替え $S$ が与えられる. $S$ に対して隣接する文字の入れ替えを行い $S$ を ${\tt atcoder}$ にする場合, 最低でも何回入れ替えなければならないか.

制約

$S$ は ${\tt atcoder}$ の並び替え

解法

$S$ に対して, ${\tt a}, {\tt t}, {\tt c}, {\tt o}, {\tt d}, {\tt e}, {\tt r}$ をそれぞれ $1,2,3,4,5,6,7$ に置き換えた整数列を $T$ とする.

すると, 問題は $T$ の隣接項の入れ替えにより $T$ を昇順にするための入れ替えの最小回数を求めよ.

この問題は $T$ に対するバブルソートでの入れ替えの回数と一致する. そして, このような回数は転倒数といわれており, 以下で定義される.

転倒数

長さが $M$ の整数列 $B=(B_1, \dots, B_M)$ の転倒数 $\operatorname{Inv}(B)$ を以下で定義する.

以下を満たす整数の組 $(i,j)$ の個数: $1 \leq i \lt j \leq M$ かつ $B_i \lt B_j$

このとき, 定義通りに転倒数を計算すると $O(M^2)$ である. 今回の問題では $M=7$ なので, 定義通りの愚直計算で十分高速である.