AtCoder精選良問「E - Red Scarf」Diff 778

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

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

問題リンク

E - Red Scarf

問題概要

猫のすぬけくんが偶数でN匹いる。
すぬけくんたちは首に赤いスカーフを巻いており、スカーフにはそのすぬけくんが一番好きな非負整数が1つ書き込まれている。

各すぬけくんは、自分のスカーフに書かれた整数以外のすべてのすぬけくんのスカーフに書かれた整数のxorを計算した。各すぬけくんが計算した結果がN個の数列で与えられる。
各すぬけくんのスカーフに書かれている整数を特定する、という問題。

考え方

最初はエスパーを働かせて解いた。
結論から言うと入力例の全ての数字のxor和を取ったのちに、各数字のxor和をとれば答えになる。

ぱっと閃いた解法が正解だったという珍しいパターン。

それだけだとあまりにもあれなので、簡単に証明をしてみる。
前提としてxorの以下の性質を使う。

1. a ^ a = 0

2. a ^ 0 = a

仮に元々スカーフに書かれていた数字をw,x,y,zとして、入力で与えられる演算結果はa,b,c,dとする。

問題の前提から以下が成り立つ。

w x y z
a b c d
=>
x ^ y ^ z = a
w ^ y ^ z = b
w ^ x ^ z = c
w ^ x ^ y = d

ここで a ^ b ^ c ^ dをするとそれぞれ代入されて以下のような、xor和を取っていることと等しい。

w ^ w ^ w ^ x ^ x ^ x ^ y ^ y ^ y ^ z ^ z ^ z  = a ^ b ^ c ^ d

Nの要素数は偶数なので左辺のw x y zの数は必ず奇数（N-1）になる。
ここで一番目の性質を使うと、２回同じものをxorすると０になるので…

0 ^ w ^ 0 ^ x ^ 0 ^ y ^ 0 ^ z = a ^ b ^ c ^ d

ここで、二番目の性質を使うと、０とxorを取った数字は必ずその数字になるので…

w ^ x ^ y ^ z = a ^ b ^ c ^ d

が最終的に成り立つ。
ここで、そもそも　x ^ y ^ z = a だったので、代入をする。

w ^ a = a ^ b ^ c ^ d

両辺に a のxorをかける。

w ^ a ^ a = a ^ (a ^ b ^ c ^ d) 

a ^ aは必ず0になるし、0とのxor和は必ずその数字、つまり w になる。
つまり、a ^ b  ^ c ^ d に a のxor和を取ったものが w ということになる。
x, y, zも同様。

その他、xorの重要な性質として以下のようなものがある。
自分は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)

実装

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


function main() {
    const n = nextNum();
    const arr = nextNums(n);
    let xorSum = 0;
    for (const num of arr) {
        xorSum ^= num;
    }
    const ans: number[] = [];
    for (const num of arr) {
        ans.push(xorSum ^ num);
    }
    log(ans.join(" "))
}

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();
}