Universal Cup 2023 - Ukraine - K問題の証明
問題
$ N頂点の強連結な有向グラフと、長さ$ Nの順列$ S,Tが与えられる。
辺$ u \to vについて操作すると、$ S_u \gt S_vのとき$ S_u,S_vがswapされる。
$ Sを$ Tに並び替えよ。
解法
任意の順列を任意の順列に並び替えられる。
↓
↓
↓
$ S_u \lt S_vのときに$ S_u,S_vをswapする手順を示す。
辺$ u \to vを含む任意のサイクルを取る
サイクルサイズが$ mとする
サイクル内の最小値を$ m-1回移動させるとサイクルに沿ってshiftができる
サイクル内の値を$ S_u,S_vとの大小で$ 1,2,3,4,5の5種類の値に分類する
$ S_u = 2, S_v = 4
$ 1,3,5は複数ずつありうるが、同じ値どうしはswapしないものとする
$ 2,4,1,5,3,3,1,5,1,1,3みたいなのを$ 4,2,1,5,3,3,1,5,1,1,3みたいにしたい
$ 1と$ 3,5 をswapして分離
$ 2,4,1,1,1,1,5,3,3,5,3
$ 2,4まわりでswapして、$ 1,3,5 を $ 2,4 の中に入れる
$ 3,1,1,1,1,4,2,5,3,3,5
shiftして$ 4,2,5,3,3,5,3,1,1,1,1
$ 1と$ 3,5 を元の順に戻す
$ 4,2,1,5,3,3,1,5,1,1,3
$ 1,3,5の中でも元の順は保たれている
あとは無向グラフ版が解ければ良い。
全域木を取って、葉から合わせていけば良い。
解法2
サイクルの場合が解ければ、後はどうとでもなる。
$ Sに操作、$ Tに逆操作をしていき、$ S=Tに出来れば良い
逆操作は、辺の向きを逆にしたグラフで操作をすることに対応する
$ Sを$ 1,2,...,nにする
バブルソートの要領で
$ Tを $ n,...,2,1にする
$ Sを$ n,...,2,1にする
$ n=6を例にする
$ 1,2,3,4,5,6
$ 6,2,1,3,4,5($ 1を$ n-2回移動)
$ 4,5,6,3,2,1($ 2,1をそれぞれ$ n-3回移動)
$ 4,3,2,1,5,6($ 3,2,1をそれぞれ$ n-4回移動)
$ 3,2,1,6,5,4($ 4,3,2,1をそれぞれ$ n-5回移動)
$ 6,5,4,3,2,1 shift