Codeforces Global Round 9 E. Inversion SwapSort
問題概要
長さ の数列
が与えられる。この数列についてインデックスのペア
が
かつ
を満たすとき、このペアは転倒していると呼ぶ。
与えられた について転倒している全てのペアを並べた列であって、「列に並んでいる順に、ペアが示すインデックスの要素をスワップさせる」という操作によって
を昇順ソートできるものが存在すればその一例を求め、存在しなければ
-1 を出力せよ。
制約
解法
まずは簡単のため、 が全て異なる場合を考えます。
末尾から順番に、正しい値になるように操作していきます。操作順番を上手く選ぶことで以下のような操作をすることが可能です。
- 末尾のインデックス
が関わる転倒ペアについてのスワップ操作を全て消化する。
- 操作後、末尾に全ての要素の中で最大の値が置かれている。
- 末尾以外の要素同士のスワップは一切行わず、それらの大小関係も変化しない。
具体的には、末尾と転倒ペアをなしている（つまり末尾より要素の値が大きい）インデックス全てについて、要素の値が小さいものから順番に末尾とスワップしていけば良いです。
この操作によって末尾以外の場所では転倒ペアの使用状況も要素同士の大小関係も変化しないので、これを後ろから順番に繰り返し適用していくことで必ず数列をソートすることができます。
もし値が同じ要素が複数存在するときには、それらの間には転倒ペアがないので、「初期状態で前にある要素ほど値として小さい」と順序を付けてしまうことで同じように解くことができます。
