Educational Codeforces Round 99(Div.2) D. Sequence and Swaps 解説

初投稿なので丁寧目に書きました。たぶん今後は徐々にテキトーになります（苦笑）

問題リンク

codeforces.com

問題概要

$n$ 個の非負整数からなる数列 $a=\{a_1, a_2, ..., a_n\}$ と、非負整数 $x$ が与えられます。次の操作を好きな回数行えます。

操作: $x$ より大きい $a$ の要素 $a_i$ を選択し、 $a_i$ と $x$ を入れ替える。

数列 $a$ を広義単調増加にするために必要な操作回数の最小値を求めてください。ただし、不可能な場合は $-1$ と出力してください。

制約

$1 \leq t \leq 500$ , $1 \leq n \leq 500$ , $0 \leq x \leq 500$

ただし、 $n$ の和は500を超えない。 $t$ はクエリの個数。

解法

$x$ と交換する $a$ の要素は必ず $x$ より大きいので、スワップを繰り返すにつれて $x$ は(狭義)単調増加することと、ソート後の数列は左に行くほど小さくなることを考えると、直観的に $x$ とスワップできる要素の内、最も左の要素をスワップをしていきたくなります。証明します。

証明

　 $x(=x')$ と $a_i, a_j (i \lt j)$ がスワップできるとします。この時 $a_i, a_j \gt x$ が成り立ちます。ここで $a_j$ とスワップした場合、数列の並びは $a_i, x'$ となり、 $x=a_j$ です。 $a_i \gt x'$ でしたから、この2要素の並びはこのままではいけません。しかし、さらに $x(=a_j)$ を $a_i$ とスワップしても $a_j \gt x'$ なので大小関係が逆のままとなります。1回目あるいは2回目のスワップの直後に他から要素を貰ってくることもできますが、 $x$ は単調増加であり、 $x'$ よりも小さな $x$ を貰うことはできないため、 $i$ 番目の位置には $x'$ 以下の要素を置くことができません。よって、2つ以上スワップできる要素があった時、そのうち最も左の要素とスワップするべきであり、逆にその他の要素とスワップするとソートが完遂しません。従ってこれが唯一の手順となり、他の手順が存在しないため、当然最小の手順にもなります。