AtCoder精選良問「E - Red Scarf」Diff 778
この記事はAtCoderの精選良問集マガジンの中の記事です。
私が良問だと思った問題を解説付きでまとめています。
問題リンク
問題概要
猫のすぬけくんが偶数でN匹いる。
すぬけくんたちは首に赤いスカーフを巻いており、スカーフにはそのすぬけくんが一番好きな非負整数が1つ書き込まれている。
各すぬけくんは、自分のスカーフに書かれた整数以外のすべてのすぬけくんのスカーフに書かれた整数のxorを計算した。各すぬけくんが計算した結果がN個の数列で与えられる。
各すぬけくんのスカーフに書かれている整数を特定する、という問題。
考え方
最初はエスパーを働かせて解いた。
結論から言うと入力例の全ての数字のxor和を取ったのちに、各数字のxor和をとれば答えになる。
ぱっと閃いた解法が正解だったという珍しいパターン。
それだけだとあまりにもあれなので、簡単に証明をしてみる。
前提としてxorの以下の性質を使う。
a ^ a = 0
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)になる。
ここで一番目の性質を使うと、2回同じものをxorすると0になるので…
0 ^ w ^ 0 ^ x ^ 0 ^ y ^ 0 ^ z = a ^ b ^ c ^ d
ここで、二番目の性質を使うと、0と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系の問題を解く時には必ず見るようにしている。
a ^ a = 0
a ^ 0 = a
aが偶数ならば a^a+1 = 1
a ^ b = c ならば a ^ c = b および b ^ c = a
(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();
}
この記事が気に入ったらサポートをしてみませんか?