AtCoder Beginner Contest 126 F - XOR Matching
解法
結論を書いてしまうと、以下のような数列がもし作れれば答えになります。
アイデアとしては、まず を挟んで 以外の数字を鏡写しに並べます。こうすることで 以外のどの数字を選んでも、2つの位置の間(両端を含む)にあるものは「 1個と、同じ数字の2個ペアたち」となり、同じ数字のペアはXORで打ち消し合うので必ずXORの値が になります。
あとは 同士のXORも にならないといけませんが… の場合は もう1つの を端に置くことで間にある値のXORが必ず になります。これは、
- を非負整数として、 のXORを取ると必ず0になる
という性質によるものです。この性質は以前のABCにも登場しましたね。
であれば は上記のような4つ組のグループに分けられるので、そのXORは0になります。今回 と の間(両端を含む)にある値はこれらの値1つずつと 1個だけが余っているので、そのXORは になります。
ということで、 かつ のときは答えを求めることができました。あとは残りのケースを考慮します。
もし である場合には、 の最上位ビットは の位以上になり、 の値をどうXORで組み合わせてもこのビットを作ることはできません。つまり、この場合は構成不可能です。
の場合は入出力例に示されている通りなので、これをそのまま埋め込んでしまえばよいです。 も実は制約に含まれていますが、この場合は 0 0
しか作れないので の場合だけ答えが存在します(考慮していなくても と同じ実装で正しく処理できることが多いでしょう)。