Codeforces Round #348 B. Little Artem and Dance

1..n が順に並んだ数列 A が与えられる。この数列に対して以下の 2 種類の操作を行う。

最終的な数列 A を求めよ。

数列を偶数番目と奇数番目で分離して考えてみる。

回転操作は以下のようになる。

f:id:pekempey:20160425185357p:plain

偶奇の交換は以下のようになる。

f:id:pekempey:20160425185403p:plain

どちらの操作も回転を無視すれば順序を維持している。

自分が考えた方法は「回転量の合計」を偶奇それぞれに対して求めておき、最後にまとめて回転するというもの。

結局 1 と 2 の位置の情報があれば最終的な数列が求まるので、1 と 2 だけシミュレートするという方法もある。

問題を理解するのにかなり時間を掛けてしまった。