現在の進捗
満点解法以外全てを和訳済み。
他の問題はこちらから。
https://qiita.com/clara775/items/57dbe85edcad1f4483c8
問題
日本語問題文はこちら。
小課題1 N=2
この小課題では家の数が2であるため、あり得る順列の入力は0,1か1,0です。
0,1の場合、転居は行われないので、W=0を出力して終えれば良いです。
1,0の場合、二つの像の状態を入れ替える必要があります。$b_{i,j}$を$i$回目の歩行における像$j$の状態とした時、これは以下の通り3回の歩行で実現することができます。
1回目の歩行：$b_{1,0}=b_{0,0}$, $b_{1,1}=b_{0,0} \oplus b_{0,1}$
2回目の歩行：$b_{2,1}=b_{1,1}$, $b_{2,0}=b_{1,0}\oplus b_{1,1}=b_{0,0}\oplus b_{0,0}\oplus b_{0,1}$
3回目の歩行：$b_{3,0}=b_{2,0}=b_{0,1}$, $b_{3,1}=b_{2,0}\oplus b_{2,1} = b_{0,1} \oplus b_{0,0} \oplus b_{0,1}$
言い換えると、それぞれの歩行において1番目にみる像はそのままに、2番目にみる像は元の二つの像のxorを取るとスワップが完了します。
小課題2 Nが15以下
全ての順列は、右端から要素を確定させるように入れ替え操作をすることで、最大でも$N-1$回の入れ替え操作で作ることができます。
それぞれの入れ替え操作には、3回の歩行と、左から右への歩行に戻るための追加の1回で、4回の歩行が必要です。つまり、$W=4(N-1)\leq 56$で問題を解くことができます。
さらに、左から右へ進むのに一旦戻る操作は実は必要なく、右から左へ入れ替え操作を始めても同じ結果が得られます。これで、$W=3(N-1)\leq 42$で問題を解くことができました。
小課題3 逆順
この小課題では、与えられる順列が降順になっています（n-1,n-2,n-3...2,1,0）。
nが偶数の場合、0とn-1、1とn-2など、一般に$i$と$n-1-i$をペアにして、小課題1と同様に入れ替えの操作を行えば良いです。それぞれの入れ替え操作は独立しているため、全てを同時に行うことができます。よって、W=3を達成できました。
nが奇数の場合も同様に、$\frac{n-1}{2}$はそのままに、それ以外の要素を全てペアにして同様の操作を行うことができます。
小課題4 1,2,...n-1,0
この小課題では、一つ右にシフトさせることが目標です。
1回目の歩行では、以下のようにxorの累積和を取ります。
- $b_{1,0}=b_{0,0}$
- $b_{1,1}=b_{0,0}\oplus b_{0,1}$
- $b_{1,2}=b_{0,0}\oplus b_{0,1}\oplus b_{0,2}$
- ...
- $b_{1,n-1}=b_{0,0}\oplus b_{0,1}\oplus ... \oplus b_{0,n-1}$
2回目の歩行では、隣り合う二要素のxor和を取ることで、ほとんどの要素が相殺し、この時点ですでに正しい結果を得ることができます。
- $b_{2,n-1}=b_{1,n-1}=b_{0,0}\oplus b_{0,1}\oplus ... \oplus b_{0,n-1}$
- $b_{2,n-2}=b_{1,n-1}\oplus b_{1,n-2} = b_{0,n-1}$
- $b_{2,n-3}=b_{1,n-2}\oplus b_{1,n-3} = b_{0,n-2}$
- ...
- $b_{2,1}=b_{1,2}\oplus b_{1,1} = b_{0,2}$
- $b_{2,0}=b_{1,1}\oplus b_{1,0} = b_{0,1}$
3回目の歩行では、最後$n-1$番目の要素の値のみ、$b_{0,0}$に直す必要があります。そのため最後の要素以外は変更せず、
$b_{3,n-1}=b_{2,0}\oplus b_{2,1}\oplus ... \oplus b_{2,n-1}=b_{0,0}$
として、W=3で解くことができました。
小課題5 n-1,0,1,...n-2
この小課題では、左へのシフトが目標です。
1回目の歩行では、最初の要素はそのままに、それ以外の要素は一つ前の要素とのxor和を取ります。
- $b_{1,0}=b_{0,0}$
- $b_{1,1}=b_{0,0}\oplus b_{0,1}$
- $b_{1,2}=b_{0,1}\oplus b_{0,2}$
- ...
- $b_{1,n-1}=b_{0,n-2}\oplus b_{0,n-1}$
2回目の歩行では、xorの累積和を右から取っていくことで、ほとんどの項が相殺されます。
- $b_{2,n-1}=b_{1,n-1}=b_{0,n-2}\oplus b_{0,n-1}$
- $b_{2,n-2}=b_{1,n-1}\oplus b_{1,n-2} = b_{0,n-2}\oplus b_{0,n-1}\oplus b_{0,n-3}\oplus b_{0,n-2} = b_{0,n-1}\oplus b_{0,n-3}$
- $b_{2,n-3}= b_{1,n-1}\oplus b_{1,n-2}\oplus b_{1,n-3} = b_{0,n-1}\oplus b_{0,n-4}$
- ...
- $b_{2,1}=b_{1,n-1}\oplus ... \oplus b_{1,1}=b_{0,n-1}\oplus b_{0,0}$
- $b_{2,0}=b_{1,n-1}\oplus ... \oplus b_{1,0}=b_{0,n-1}$
3回目の歩行では、初めの要素とのxor和を取ることで、W=3でこの小課題を解くことができます。
- $b_{3,0}=b_{2,0}=b_{0,n-1}$
- $b_{3,1}=b_{2,1}\oplus b_{2,0}=b_{0,0}$
- $b_{3,2}=b_{2,2}\oplus b_{2,0}=b_{0,1}$
- ...
- $b_{3,n-1}=b_{0,n-2}$
W=6 90点解法
この小課題は、小課題3 逆順の場合の解法を応用することで解くことができます。
小課題3では、独立な入れ替え操作を同時に行うことで、W=3を実現しました。これは、$i$番目の要素から$a_i$番目の要素への有向辺を張ったグラフを考えた時、全てのサイクルの長さが２つ以下であるからです。このような順列は逆順以外にも様々存在し、これらをオーダー２の順列と呼ぶことにしましょう。
ではもっと長いサイクルを含む順列ではどうでしょうか。実は、全てのサイクルはオーダー２の順列を2回適用することによって構築可能なことを証明できます。
証明
まず、偶数長のサイクルの構築について考えます。以下のようにして、2回の順列操作によって、偶数長のサイクルの構築例を一つ作ることができます。
開始：$(0,1...2k-1)$
↓ 隣り合う二要素のペア、$(0,1), (2,3), ... (2k-2,2k-1)$をそれぞれ入れ替える
$(1,0,3,2,...2k-1,2k-2)$
↓ 0_indexedで1番目の要素から始めて、同様に隣り合う二要素のペア、$(0,3), (2,5), ... (2k-4,2k-1)$をそれぞれ入れ替える
$(1,3,0,5,2,...2k-1,2k-4,2k-2)$
このサイクルは、0番目→1番目→3番目→（全ての奇数番目）→$2k-1$番目→$2k-2$番目→（全ての偶数番目）→0番目と辿ることができるので、長さは$2k$です。
実は、一つサイクルの構築例を示せたので、これで全てのサイクルを構築できることがわかります。まず全ての$2k$長のサイクルは、上の操作の逆、つまり
- サイクルを辿る順番上で、0番目の要素の一つ前と一つ後、二つ前と二つ後、一般に$i$番前と$i$番後を入れ替える
（上の場合、0番目の要素である1の1つ前は2番目の0、1つ後は3、2つ前は2、2つ後は5なので、$(0,3),(2,5)$などを入れ替えます） - $i$番目と$a_i$番目の要素を入れ替える
（上の場合、$(0,1),(3,2),(2k-1,2k-2)$などを入れ替えます）
ことで全てのサイクルを$0,1,2,...2k$に戻すことができます。これを逆から行うことで、$0,1,2,...2k$から全てのサイクルを作ることができます。
奇数長のサイクルも、ほぼ同様に行うことができます。
これをそれぞれのサイクルに適用することによって、W=3のアルゴリズムの適用2回で全ての順列を作ることができるとわかります。
W=5 95点解法
W=6の解法では、オーダー2の順列操作を2回行いました。実は、1度目の順列操作の3回目の歩行と、2度目の順列操作の1回目の歩行は両方とも左から右のため一気に行うことができます。