[AtCoder] ABC 121 D – XOR World

XOR World

https://atcoder.jp/contests/abc121/tasks/abc121_d

方針

排他的論理和の性質

\( \mathrm{XOR} \) を \(\oplus\) で表すとします。

まず排他的論理和の性質として次の二つがあります。

  1. \( 0 \oplus x \ = x \)
  2. \( x \oplus x = 0 \)

その他の性質については、下のサイトが役に立ちます。

https://qiita.com/kuuso1/items/778acaa7011d98a3ff3a

また、排他的論理和は順番を入れ替えて計算しても成り立ちます。

\( f(A, B) \) の式変形

\( f(A, B) = A \oplus (A + 1) \oplus \cdots \oplus B\)

ここで、\(f(0, B) \) を考えます。

\begin{eqnarray}
f(0, B) &=& 0 \oplus 1 \oplus \cdots \oplus(A – 1) \oplus A \oplus (A + 1) \oplus \cdots \oplus B \\
f(0, B) &=& f(0, A-1) \oplus f(A, B)
\end{eqnarray}

上式に左から \( f(0, A-1) \) の排他的論理和を作用させると、

\begin{eqnarray}
f(0, A-1) \oplus f(0, B) &=& f(0, A-1) \oplus f(A, B)\\
f(0, A-1) \oplus f(0, B) &=& f(0, A-1) \oplus f(0, A-1) \oplus f(A, B)\\
f(0, A-1) \oplus f(0, B) &=& 0 \oplus f(A, B)\\
f(A, B) &=& f(0, A-1) \oplus f(0, B)
\end{eqnarray}

となります。よって、\( f(0, n) \) の値が分かれば問題を解くことができます。

\( f(0, n) \) の値

\( f(A, B) = 0 \oplus 1 \oplus \cdots \oplus n\)

この値を求めるには代数的?に解くことができると思いますが、僕には思いつかなかったので、実験的に求めて見ます。

\begin{eqnarray}
f(0, 0) &=& 0 \\
f(0, 1) &=& 1 \\
f(0, 2) &=& 3 \\
f(0, 3) &=& 0 \\
f(0, 4) &=& 4 \\
f(0, 5) &=& 1 \\
f(0, 6) &=& 7 \\
f(0, 7) &=& 0 \\
f(0, 8) &=& 8 \\
f(0, 9) &=& 1 \\
f(0, 10) &=& 11 \\
\end{eqnarray}

上記より、\( m \) を整数として、

\begin{eqnarray}
f(0, 4m) &=& 4m\\
f(0, 4m + 1) &=&  1\\
f(0, 4m + 3) &=& 0
\end{eqnarray}
となっていることが分かります。\( f(0, 4m + 2) \) は、

\[f(0, 4m + 2) = f(0, 4m + 1) \oplus (4m + 2) = 1 \oplus (4m + 1)\]

として、求めることができます。よって、\(f(A, B)\) を求めることができます。

コード

感想

まあ、言われてみればそうなるかといった感じですね。

解けなかったので復習しないのといけないですね。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする