AtCoder精選良問「D - XOR World」Diff 1164

この記事はAtCoderの精選良問集マガジンの中の記事です。
私が良問だと思った問題を解説付きでまとめています。

AtCoder 精選良問集 Diff 茶後半～水前半｜Qlitre｜note

問題リンク

D - XOR World

問題概要

f(A,B) をA,A+1,...,B の排他的論理和としたとき、f(A,B) を求める。

考え方

排他的論理和（xor）の性質を学べる良い問題。

まず、排他的論理和を確認する。
二つの数字のbitを比較して違ってたら１を立てるという演算。
typescriptではa^bとして計算ができる。

問題ではAからBまで、順番にxor演算をして最後に答えを出力する、ということが求められている。

素朴に実装するとこういうコードになる。

function main() {
    const [a, b] = nextNums(2)
    let ans = 0
    for (let i = a; i < b + 1; i++) {
        ans = ans ^ i
    }
    log(ans)
}

これで正しい答えが出力されるが、A,Bの制約は10の12乗と大きいので、このまま提出するとTLEになる。なので、なんとか高速に計算する方法がある。

まずはXOR算の重要な性質として以下のようなものがある。
もうこれは、そういうものだと覚えておくようにする。少なくとも自分はそうする。

1. a ^ a = 0

2. a ^ 0 = a

3. aが偶数ならば a^a+1 = 1

4. a ^ b = c ならば a ^ c = b および b ^ c = a

5. (a ^ b) ^ c = a ^ (b ^ c)

この性質をうまく使って問題を解く。
間の数字を取るということは、Aまでの演算結果とBまでの演算結果で考えることができそう。

例えば入力がA = 3 B =8だとする。
そうすると、以下のような式が成り立つ

f(0,B)=f(0,A-1)^f(A^B)

とりあえず出力しなければいけないf(A,B)を式に出現させる。

これを4番の性質を使って変形すると…

f(0,B)^f(0^A-1)=f(A^B)

こうなる。
ということで、BとA-1までの数字のxor算を高速に計算することに言い換えられた。

ここで例えば8までの計算をしてみると…

0^1^2^3^4^5^6^7^8
=>
(0^1)^(2^3)^(4^5)^(6^7)^8
となるので、3番の性質(a^a+1 = 1)を使うと、
(1^1)^(1^1)^8
ここで1番の性質(a ^ a = 0)を使うと、
(0^0)^8
ここで2番の性質(a ^ 0 = a)を使うと8になる。

9までの数字だったら、8^9なので、3番の性質で必ず1
10までだったら、1^10は…最後のbitが反転するから11か。
11までだったら、11^11で0。
12までだったら、0^12で12。
…
一般化すると0からNまで順番に演算した結果は以下が成り立つ。

N % 4 = 0 => N
N % 4 = 1 => 1
N % 4 = 2 => N+1
N % 4 = 3 => 0

Nが４の倍数の場合、1のペアを偶数個作れるので、最後は必ず0^N = Nとなる。

実装

import { createInterface } from "readline";
import * as fs from "fs";
import { log } from "console";
import { exit } from "process";

function calcXorSum(n: bigint): bigint {
    if (n % 4n == 0n) {
        return n
    } else if (n % 4n == 1n) {
        return 1n
    } else if (n % 4n == 2n) {
        return n + 1n
    } else {
        return 0n
    }
}

function main() {
    const [a, b] = nextBigInts(2)
    const aXor = calcXorSum(a - 1n)
    const bXor = calcXorSum(b)
    log(String(aXor ^ bXor))
}

let inputs = "";
let inputArray: string[];
let currentIndex = 0;

function next() {
    return inputArray[currentIndex++];
}
function nextNum() {
    return +next();
}
function nextBigInt() {
    return BigInt(next());
}
function nexts(length: number) {
    const arr = [];
    for (let i = 0; i < length; ++i) arr[i] = next();
    return arr;
}
function nextNums(length: number) {
    const arr = [];
    for (let i = 0; i < length; ++i) arr[i] = nextNum();
    return arr;
}
function nextBigInts(length: number) {
    const arr = [];
    for (let i = 0; i < length; ++i) arr[i] = nextBigInt();
    return arr;
}


// デバッグ環境がWindowsであれば条件分岐する
if (process.env.OS == "Windows_NT") {
    const stream = createInterface({
        input: process.stdin,
        output: process.stdout,
    });
    stream.on("line", (line) => {
        inputs += line;
        inputs += "\n";
    });
    stream.on("close", () => {
        inputArray = inputs.split(/\s/);
        main();
    });
} else {
    inputs = fs.readFileSync("/dev/stdin", "utf8");
    inputArray = inputs.split(/\s/);
    main();
}