AGC052_A – Make it Zigzag

問題
感想
1. 1回目
  1. 提出

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

感想

1回目

解法分からず、解説を読んだ。
$P_x$と$P_{x+1}$を1つずつ見ていき、条件に合うように操作をしたらN回以内になるかなー、と思ったらWAになった。
$P_x,P_{x+1},P_{x+2}$を考慮する必要があるらしい。

解法はこうらしい。
例えば、$x$が奇数の時、$P_x<P_{x+1}$になる必要がある。
$P_x<P_{x+2}$だった場合、$P_{x+1}とP_{x+2}$を入れ替える。
$P_x>P_{x+2}$だった場合、$P_{x}とP_{x+1}$を入れ替える。
$x$が偶数の時も同様。

自分の考えた方法の良くなかった点を考えてみる。
単に条件を満たしていない$P_x$と$P_{x+1}$を交換する方法で、$P_x,P_{x+1}$を入れ替えると、$P_{x+1},P_{x},P_{x+2}$になる。
この時、条件を満たすことが保証されているのは$P_{x+1},P_{x}$である。
次に見るべきは$P_{x},P_{x+2}$になる。
これも交換が必要な場合はある。
そうすると、$x$ごとに交換が必要になる場合があるので最大で$2N-1$回交換が必要になる。

公式解説の方法だと、$P_x,P_{x+1},P_{x+2}$を見る。
交換後は$P_{x+1},P_x,P_{x+2}$または$P_x,P_{x+2},P_{x+1}$になる。
これらは1回の操作で、2つの条件を満たしている。
そうすると、$2N$個の数列は$N$回の操作を行えば条件を満たせる。

提出

なし