AtCoder Beginner Contest

【pythonでABC121を解説】D - XOR World

問題概要

問題ページ

問題文

\(f(A, B)\) を \(A, A+1, ..., B\) の排他的論理和としたとき、\(f(A, B)\) を求めてください。

排他的論理和とは

整数 \(c_1, c_2, ..., c_n\) のビットごとの排他的論理和 \(y\) は、以下のように定義されます。

  • \(y\) を二進表記した際の \(2^k\) (\(k \geq 0\)) の位の数は、\(c_1, c_2, ..., c_n\) のうち、二進表記した際の \(2^k\) の位の数が \(1\) となるものが奇数個ならば \(1\)、偶数個ならば \(0\) である。

例えば、\(3\) と \(5\) の排他的論理和は \(6\) です(二進数表記すると: 011101 の排他的論理和は 110 です)。

制約

  • 入力は全て整数である。
  • \(0 \leq A \leq B \leq 10^{12}\)

問題の考察

排他的論理和の問題。

制約が\(0 \leq A \leq B \leq 10^{12}\)なのでfor文で計算すると明らかに間に合わない。

排他的論理和の問題は、その性質を上手く利用して計算する問題が多く出題されている。

今回の場合には次のような性質を利用する必要がある。

排他的論理和の性質

  • 偶数から始まる隣合う2数の排他的論理和は\(1\)

実際に数値を当てはめてみると次のようになります。

隣り合う排他的論理和

  • \(10(2) \oplus  11(3) = 1\)
  • \(100(4) \oplus 101(5) = 1\)
  • \(110(6) \oplus  111(7) = 1\)
  • \(1000(8) \oplus  1001(9) = 1\)
  • \(1010(10) \oplus 1010(11) = 1\)

\(()\)内は\(10\)進数表記、\(\oplus \)は排他的論理和だが、計算してみると「隣り合う\(2\)数の排他的論理和は\(1\)」であることが分かる。

Bit表記した時に、偶数の最下位桁は\(1\)になり(最下位桁以外は\(2\)の倍数から明らか)、偶数の最下位桁は\(1\)になる。

つまり偶数から始まる隣り合う\(2\)数の差は\(1\)かつ最下位桁以外は一致しているという性質がある。

実際には、開始と終了の文字の偶奇はバラバラであり、次の\(4\)パターンが考えられる。

赤枠で囲まれた部分の排他的論理和は先ほどの説明通り\(1\)であるので、この赤枠が奇数個なら排他的論理和は\(1\)、偶数個なら\(0\)になる。

問題文の通り\(a\)から始まり\(b\)で終わるとすると次のようにまとめられる。

偶奇パターンまとめ

  • 偶数から始まり偶数で終わる
    • 赤枠が偶数個なら\(0 \oplus  b\)
    • 赤枠が奇数個なら\(1 \oplus  b\)
  • 偶数から始まり奇数で終わる
    • 赤枠が偶数個なら\(0\)
    • 赤枠が奇数個なら\(1\)
  • 奇数から始まり偶数で終わる
    • 赤枠が偶数個なら\(0 \oplus  a \oplus b\)
    • 赤枠が奇数個なら\(1 \oplus  a \oplus b\)
  • 奇数から始まり奇数で終わる
    • 赤枠が偶数個なら\(0 \oplus  a\)
    • 赤枠が奇数個なら\(1 \oplus  a\)

これをif文などを使ってコーディングしていくことになる。

コーディングの難易度は高くないが、条件分岐を間違えないように気を付ければ問題ない。

なお、pythonで排他的論理和は^演算子を使う。

たびすけ
日常生活では排他的論理和は使わないので問題を通して、その性質を理解していきましょう!

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    a, b = list(map(int, input().rstrip('\n').split()))
    cnt = b - a + 1
    if a % 2 == 0 and b % 2 == 0:
        print(b ^ (cnt - 1) // 2 % 2)
    elif a % 2 != 0 and b % 2 != 0:
        print(a ^ (cnt - 1) // 2 % 2)
    elif a % 2 != 0 and b % 2 == 0:
        print(a ^ b ^ (cnt - 2) // 2 % 2)
    else:
        print(cnt // 2 % 2)


if __name__ == '__main__':
    solve()

プログラミング

-AtCoder Beginner Contest
-,