NOMURA プログラミングコンテスト 2021(ARC121) C - Odd Even Sort
AtCoder公式の解説とは若干異なる手法で解いたので記事化。
問題
- 公式解説
Editorial - NOMURA Programming Contest 2021(AtCoder Regular Contest 121)
概要
$(1, 2, ...N)$の順列$p$がある(1-indexed)。
隣り合う要素$p_n$と$p_{n+1}$を入れ替えて昇順に並び替える。 ただし、奇数回目の操作では$n$は奇数、偶数回目の操作では$n$は偶数でなければならない。
$p$を昇順に並べ替える操作列であって、操作回数が$N^2$回以内であるものを1つ求めよ。
注記:
- 有限回の操作で任意の$p$をソートできることは証明可能である。
- 必ずしも最短の操作列を出力する必要はない。
解法
- 要素数が2の場合、個別に解を出力して終了する。
選択ソートを行う。具体的には, $i$回目の操作群で以下を行う。$(i=1,2,3,...,N-3)$
- 数値$i$の場所を探す。$i$のある場所を$j$番目とする。$(p_j=i)$
- $i\neq j$のとき、操作$(i, i+1, i+2, ... , j-2, j-1, j-2, ... ,i+1, i)$を行う。この操作では$p_i$と$p_j$以外の要素の位置が変わらず、$p_i$と$p_j$が交換される。
- $i$が奇数のとき、操作列は(奇偶奇偶...奇偶奇)となる
- $i$が偶数のとき、操作列は (偶奇偶奇...偶奇偶)となる
- $i==j$のとき、操作$(i+2)$を行う。この操作では$p_1 ... p_n$の値を変えずに操作回数を調整する。
- $i$が奇数のとき、操作列は(奇)となる
- $i$が偶数のとき、操作列は (偶)となる
- 全体を通した操作列は、(奇偶...奇)(偶奇...偶)(奇偶...奇) ... となるので問題文の条件を必ず満たす
この時点で末尾の3要素以外がソートされている。
- 末尾の3要素をソートする。これらは必ず5回以下の操作でソートできる(その時点で可能な操作を繰り返せばよい)。
- この時点で全ての要素がソートされているので、記録しておいた操作列を出力する。
操作回数の上限
要素数3のとき、操作回数は最大で5回です。 また、要素数$n$のときの最大操作回数を$f(n)$とすると、$f(n+1)=f(n)+2n+1$となります。 これを解くと$f(n)=n^2-9$となるので、制約である$n^2$回以下の条件を満たします。
writer解と比較した利点・欠点
利点
- 必要な場合分けが減り、実装が軽い(writer解では要素数4の時を場合分けしていました)
欠点
- 公式の解と比較して、操作回数が倍に増える(制約はかろうじて足りる)
ポイント
- 操作回数が最短でなくてよいので、多少冗長な解でも許容される
- $O(N^2)$のソートを活用する
- $N$が小さい場合は個別に対処できる
- 重実装で考察コストを下げるか、考察して実装を軽くするかのトレードオフ
解を出すまでの考察
構築系なので、とりあえず問題文に都合の良い性質があるかを見てみます。
使いやすい操作を考える
問題文の条件から、操作列は奇数と偶数が交互に並んでいる必要があります。 そして、ある数を別の場所に移動させる場合、操作列の数は必ず偶奇が交互に並びます。
例えば、6 4 2 7 3 1 5 の 1 を先頭に持っていくには、swap($p_5$,$p_6$)→swap($p_4$,$p_5$)→swap($p_3$,$p_4$)→swap($p_2$,$p_3$)→swap($p_1$,$p_2$)とすればよいです。 左側の要素の番号を並べた操作列は$(5,4,3,2,1)$となり、奇数と偶数が交互に並びます。
拡張して交換操作を作る
さらに、この操作を拡張することで2数の交換が可能になります。
例として、数列6 4 2 7 3 1 5 の4 と1を交換してみます。
まず、4を1のある位置に移動させるのに、操作列$(2,3,4,5)$を実行します(6 2 7 3 1 4 5になる)。
次に、1を元々4のあった位置に戻すのに、操作列$(4,3,2)$を実行します(6 1 2 7 3 4 5になる)。
このとき、1と4以外の要素は交換の前後で移動せず、全体の操作列は$(2,3,4,5,4,3,2)$となり偶奇が交互に並びます。
しかも、どの位置の数を交換したかによらず、操作列の先頭と末尾の偶奇が必ず一致します。
ソートへの応用
この交換操作を利用してソートができないかを考えてみます。
計算量$O(N^2)$のソートが許容されているので、使える手段が多いです(バブルソートや挿入ソート、選択ソートなど)。
離れた要素の交換を主体とするアルゴリズムを使いたいので、選択ソートについて考えます。
選択ソートは、$i=1,2,3,...N-1$の順に、左から$i$番目の要素と$i$番目に小さい要素を交換していくソートです。
これを先ほどの交換操作に当てはめると、左から$i$番目の要素と$i$番目に小さい要素を交換する操作列は$(i, i+1, i+2, ... i+1, i)$となります。 ここで、$i$が奇数のとき操作列の先頭と末尾は奇数となり、$i$が偶数のとき操作列の先頭と末尾は偶数となります。 つまり、これらの操作を繋げた操作列は、(奇偶奇偶奇偶....)となり必ず問題文の条件を満たすことになります。
例えば6 3 4 2 1 5の場合、1を先頭に持っていく操作列は$(1,2,3,4,3,2,1)$となります。その後に2を2番目に持っていく操作列は$(2,3,2)$、3を3番目に持っていく操作列は$(3)$となります。全体の操作列は$(1,2,3,4,3,2,1,2,3,2,3)$となり、確かに奇数から始まって偶奇が交互に並びます。
この手法は一見完璧に見えますが、実は交換操作が行われなかった場合に対応できません。 操作を行わなかった場合、交換操作の直前と直後の偶奇は等しいので、偶奇の等しい操作が2回連続してしまいます。
例えば6 2 4 3 1 5の場合、1を先頭に持って行くと1 2 4 3 5 6となりますが、2の交換先が自分自身なので、操作をせずにそのまま3を3番目に持っていく操作を行うことになります。この操作列は$(3)$なので、繋げると$(1,2,3,4,3,2,1,3)$となり、最後の2つで奇数が2つ連続してしまいます。
これを避けるには、それまでのソートに対して影響を及ぼさない操作を挟んで対応する必要があります。 具体的には、ソート済でない$i+2$番目と$i+3$番目を交換することで、ソートを壊さずに偶奇の問題に対応できます。 ただし、$i+3$番目の要素が存在していないといけないので、この方法でソートできるのは$1$から$N-3$までとなります。
例として6 2 4 3 1 5の場合、1を先頭に持って行くと1 2 4 3 5 6となります。
ここで2の2つ後と3つ後にある3 5を交換する操作列は$(4)$で、適用すると1 2 4 5 3 6となります。
3を3番目に持っていく操作列は$(3,4,3)$となり、適用すると1 2 3 5 4 6となります。
この時点で全体の操作列は$(1,2,3,4,3,2,1,4,3,4,3)$となり、問題文の条件を満たします。
この手法を実行した時点で、最後の3つの要素($N$と$N-1$と$N-2$)以外がソートされている状態になります。
残った要素のソート
残った3つの要素のソートについて考えてみましょう。 $N=3$のとき、ある状況でできる操作は一意に決まります($n$が奇数あるいは偶数になるペアは1つしかありません)。
それまでの操作回数が偶数回のときに1 2 3に対して操作を行うと、1 2 3→2 1 3→2 3 1→3 2 1→3 1 2→1 3 2→1 2 3→(繰り返し) となります。
同様に、それまでの操作回数が奇数回のときに1 2 3に対して操作を行うと、 1 2 3→1 3 2→3 1 2→3 2 1→2 3 1→2 1 3→1 2 3→(繰り返し) となります。
つまり、初期状態によらず5回以内の操作でソートされた状態に戻れるため、最後に残った部分は操作の繰り返しでソートできます。
以上の手順で数列の全ての要素をソートすることができました。
ハズレ解法
奇数番目と偶数番目の操作をペアにする
- それまでの操作回数によらず、2つ離れた要素のswapが3手で可能。
- 奇数番目の要素と偶数番目の要素を個別にソートすることができるが、ソートしたあと全体を綺麗に並べ替える方法が無さそうなので没
バブルソートの要領で、できる操作を貪欲に行う
1 3 2 4などの場合に詰むので没
