ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

AtCoder Beginner Contest 126 F - XOR Matching

F - XOR Matching

解法

結論を書いてしまうと、以下のような数列がもし作れれば答えになります。

f:id:betrue12:20190520210750p:plain

イデアとしては、まず  K を挟んで  K 以外の数字を鏡写しに並べます。こうすることで  K 以外のどの数字を選んでも、2つの位置の間(両端を含む)にあるものは「 K 1個と、同じ数字の2個ペアたち」となり、同じ数字のペアはXORで打ち消し合うので必ずXORの値が  K になります。

あとは  K 同士のXORも  K にならないといけませんが…  M \ge 2 の場合は もう1つの  K を端に置くことで間にある値のXORが必ず  K になります。これは、

  •  a を非負整数として、 4a, 4a+1, 4a+2, 4a+3 のXORを取ると必ず0になる

という性質によるものです。この性質は以前のABCにも登場しましたね。

 M \ge 2 であれば  0, 1, ..., 2^{M}-1 は上記のような4つ組のグループに分けられるので、そのXORは0になります。今回  K K の間(両端を含む)にある値はこれらの値1つずつと  K 1個だけが余っているので、そのXORは  K になります。

ということで、 K \le 2^{M}-1 かつ  M \ge 2 のときは答えを求めることができました。あとは残りのケースを考慮します。

もし  K \ge 2^{M} である場合には、 K の最上位ビットは  2^{M} の位以上になり、 0, 1, ..., 2^{M}-1 の値をどうXORで組み合わせてもこのビットを作ることはできません。つまり、この場合は構成不可能です。

 M = 1 の場合は入出力例に示されている通りなので、これをそのまま埋め込んでしまえばよいです。 M = 0 も実は制約に含まれていますが、この場合は 0 0 しか作れないので  K=0 の場合だけ答えが存在します(考慮していなくても  M \ge 2 と同じ実装で正しく処理できることが多いでしょう)。

ACコード

Submission #5462845 - AtCoder Beginner Contest 126