公式解説とは違うやり方で解いたので記しておきます。
問題の概要
順列 $p_{1},p_{2},...,p_{2N}$ が与えられるので、$N$ 回以下の隣接swapで以下の条件を満たすようにしなさい。
条件
$p_{1}<p_{2}>p_{3}<...>p_{2N-1}<p_{2N}$
解法
まず、一番大きい要素($2N$)の index は必ず偶数でなければいけません。
よって、もし奇数なら左右どちらか選んで swap させます。
これと同じようなことを繰り返します。
ちゃんと書くと、 $a=2N,2N-1,...,1$ の順に以下のことを繰り返します。
もし、今、 $a$ が存在するindex $i$ が奇数で、$p_{i-1}<a$ が成り立つなら $p_{i-1}$ と $p_{i}$ を swap する。 成り立たないとき、 $p_{i+1}<a$ が成り立つなら、$p_{i+1}$ と $p_{i}$ を swap する。 どちらも成り立たないなら swap をしない。
$i$ が偶数のときも何もしない。
各々の操作後に、 $a$ のindexが偶数なら、条件の式の中で、その両隣の符号は条件を満たします。 また、奇数のindexの要素の値が増えたり、偶数のindexの要素の値が減ったりすることはないので、この操作を行なった後の列は条件を満たします。
また、操作の回数もindexが偶数のもの以下、つまり $N$ 以下になります。
