ABC121-D "XOR World"

提出コード

考察

着目したのは以下の性質です．

任意の偶数 $n$ に対して， $n \oplus (n+1) = 1$

大雑把な証明をしておきます．

任意の偶数 $n$ に対して， $n$ の最下位ビットは $0$ です．

一方で $n+1$ を考えると，最下位ビットが $1$ で，その他のビットは $n$ と等しいです．

よって， $n$ と $n+1$ のXORをとると $1$ になることがわかります．

上の性質を用いると， $A$ から $B$ の中に偶数から奇数に切り替わるタイミングが何回あるか(numとおきます)を考えることで計算量を大幅に小さくできます．

また，num回の $1$ のXORについて，numが奇数であれば $1$ になり，numが偶数であれば $0$ になります．

私は $A$ が偶数か奇数か， $B$ が偶数か奇数かの $4$ 通りの場合分けをしました．

(i) $A$ が奇数で， $B$ が奇数

$A+1$ から $B$ までが繰り返し部分で，num $=\frac{B-A}{2}$ です．

つまり，num回だけ $1$ をXORした後，余った $A$ をXORすればOK．

(ii) $A$ が奇数で， $B$ が偶数

$A+1$ から $B-1$ までが繰り返し部分で，num $=\frac{B-A-1}{2}$ です．

つまり，num回だけ $1$ をXORした後，余った $A$ と $B$ をXORすればOK．

(iii) $A$ が偶数で， $B$ が奇数

$A$ から $B$ までが繰り返し部分で，num $=\frac{B-A+1}{2}$ です．

つまり，num回だけ $1$ をXORするだけでいいです．

(iv) $A$ が偶数で， $B$ が偶数

$A$ から $B-1$ までが繰り返し部分で，num $=\frac{B-A+1}{2}$ です．

つまり，num回だけ $1$ をXORした後，余った $B$ をXORすればOK．

以上により， $O(1)$ で解けました．

久しぶりの精進ツイートです．新生活でバタバタしていました．

この問題のdiffは $1164$ ですが，今この問題が出たら $800$ ぐらいな気がしますね．

模範解答がきれいすぎて感動しました笑