phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

ABC126 F. XOR Matching

問題

以下の条件を満たす長さ2^{M+1}の数列aが存在するなら1つ構築せよ。

  • 数列aには、0以上2^M未満の整数がちょうど2つずつ含まれる
  • a_i == a_jになるi,jについて、a_i xor ... xor a_j == Kとなっている

制約

  • 0 <= M <= 17
  • 0 <= K <= 10^9

解法

明確にわかる条件から抑えていく。

M=0のときは、K=0しかだめで、そのときの答えは「0 0」。
M=1のときは、同じくK=0しかだめで、答えは「0 0 1 1」か「1 1 0 0」。「0 1 0 1」のようなものは、0で挟まれる部分が1で、1で挟まれる部分が0になってしまう。

M=2の場合を考える。
まず、Kは2^M以上の場合、XORを取ってKが作れないので、構築できない。したがって、「K < 2^M」である必要がある。

M=2のときに現れる数字は、0 0 1 1 2 2 3 3の8つ。
実験として、これをnext_permutationで全通り試して、条件を満たすものを出力して観察すると、「Kを作って、それを両側から挟んでいるような形」が多く見受けられる。
具体的には、「X Y 0 K Y X」や「X Y K Y X」のような形ができている。

ここから、あるKについて、その両側を挟んでいくような形で考えると、同じ数字はxorを取ると0になるので、満たすことがわかる。
なので、Kを置いてその両側を挟むように他の数字を対象に置いていけばK以外の数字は条件を満たす。
ただ、Kが1つ余っており、これをどこかに置く必要があるが、すでに置いたKの両側には、0から2^M-1までの数字でKを除いた数字が並んでおり、このxorを考えるとKになっている。
(「0から2^M-1までの数字でKを除いた数字のxor」とKのxorが0にならないといけないため、Kであることがわかる)
したがって、「Kの両側に対称となるようにK以外の数字をならべ、最初か最後にKを置いたもの」は条件を満たすため、これを返せばよい。