読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

JAG夏合宿2015 2日目 ツインリバース

@sugim48さんがwriterの問題です.
未だに公式の解説が無いのですが,転倒数についての面白い知見が得られた問題だったので備忘録として解説を書こうと思います.

問題概要

素数Nで,1,...,Nの順列が与えられる
整数i(1 \le i \le N)を選び,\left[1,i-1\right],\left[i+1,N\right]の区間をそれぞれ反転する
という操作を10000回以下の回数行い,ソートを行え
という問題です.

操作の例
(5,1,2,3,4,6) に対してi=3として操作を行う
→(1,5,2,6,4,3)

解説

このままでは操作しづらいので要素一つではく二つを選んだ場合について考えてみます.
ある数列をSとしたとき,S^{-1}Sを反転させた数列と表記することにします.
数列がAxByCだったとします.A,B,Cは数列,x,yは要素です.

  1. xを選んで操作を行います.その結果,数列はA^{-1}xC^{-1}yB^{-1}になります.
  2. yを選んで操作を行います.その結果,数列はCxAyBになります.
  3. xを選んで操作を行います.その結果,数列はC^{-1}xB^{-1}yA^{-1}になります.

実はこの3回の操作を行ったあとの数列は(AyBxC)^{-1}になっていて,xとyをスワップさせたあと数列全体を反転させていることになります.
すなわち,この一連の操作を選択ソート風に繰り返し行うと,
昇順ソート列をSとしたとき,SorS^{-1}のいずれかが
が3N回で構成できます.

ここで,SorS^{-1}のどちらかになるかは数列の転倒数によって決まります
転倒数とは,N要素の数列Aにおいて,i < j かつA_i > A_jとなっている個数です.
Aがソート列となっているときは,転倒数は0になります.
証明は省きますが,一回の2要素のスワップによって変化する転倒数は奇数個になります.
したがって,スワップのみを用いてソートを行うときは交換回数の偶奇が転倒数の偶奇と一致します.

つまり,転倒数が偶数であれば偶数回のスワップを行うことになるのでSになり,
転倒数が奇数であれば奇数回のスワップを行うことになるのでS^{-1}になります.

このことから,入力で与えられた順列の転倒数が偶数であれば上記の方法でソートができることになります.

では転倒数のが奇数であればダメなのかというとそういうわけではないです
転倒数を奇数個変化させる方法が無いか考えてみます.

数列がAxBだったとします.A,Bは数列,xは要素です.
xを選んで操作することを考えます.変更後はA^{-1}xB^{-1}です.
ここで重要なのがA,B内の半順序の個数です.m=|A|とするとAの半順序の個数はt=\frac{m(m-1)}{2}となります.
AからA^{-1}にしたとき,tが奇数ならば転倒数の偶奇が入れ替わります.
すなわち|A|を4で割ったときの余りが0or1ならば偶奇が入れ替わることになります.
ABが同時に反転されるので,|A|,|B|のいずれかのみが奇数であればよいです.
これらを整理して計算すると,数列全体の長さを4で割ったときの余りが0,1,3のいずれかであれば一回の操作で転倒数の偶奇を変更することができます.
また,余りが2であれば転倒数の偶奇を変更することができません.
したがって,数列の転倒数が奇数かつ長さを4で割ったあまりが2であるときのみ昇順ソート列を構成できないことになります.(必ずスワップ回数が奇数となるため
初期の転倒数が奇数のときに転倒数を偶数にするためにどこを選ぶべきかは↑の証明を参考にして適当に求めてください(疲れた)

説明,証明が足りないところがあってもご容赦ください.
そのうち公式の解説がアップロードされると思うのでそれを待つのも手だと思います.

感想

mod4によって半順序の個数の偶奇が変わり,それを利用して問題が解けるというのはとても面白いと感じました
たまに出る性質みたいなので,忘れないようにしようと思いました.