ABC 098 D - Xor Sum 2

最近しゃくとり方を実装していなかったので解き直しました.

問題

D - Xor Sum 2

解法

問題を見るに, いかにもなしゃくとり法です.
この問題を解くうえで, xor演算の重要な性質を用います.
xor演算において以下の性質が成り立ちます.

  1. A \space xor \space A = 0
  2. A \space xor \space B = B \space xor \space A
  3. (A \space xor \space B) \space xor \space C = A \space xor \space (B \space xor \space C)

1の性質は, この演算においては自身が逆元となることを示しています. (自明に0が単位元となっています.)
2の性質は, 可換な演算であることを示しています.
3の性質は, 結合法則が成り立つことを示しています.
これを利用すると, しゃくとり法を実装することができます.
具体的には, 以下のアルゴリズムを適用することができます.
入力の配列をA, サイズをNとします.

  1. 初期化 : l:=0 , r:=0 , res := 0, now = 0
  2. r > Nならばresを出力して終了する.
  3. (A[r] + now) == (A[r] \space xor \space now) ならば4へ, そうでなければ5へ
  4. now := now \space xor \space A[r] , r := r + 1 , res := res + r - l , 2へ
  5. now := now \space xor \space A[l] , l := l + 1 , 2へ

しゃくとりの右端を右に進めるときに答えを加算するようにしています.
計算量はO(n)で済みます.

提出

Submission #3184217 - AtCoder Beginner Contest 098

感想

しゃくとり法は本番でバグらせやすいので演習を積んでいきたいです.