面白かった。でも茶色ってことは流石になさそう......(コンテスト中は、全部の XOR 和が 0 かどうかを判定する、という嘘解法が AC になっていたらしい)

問題へのリンク

問題概要

$N$ 個の非負整数 $A_{1}, \dots, A_{N}$ が与えられる。これらを円環状に上手に並べることで、

「どの整数も両隣の整数の XOR 和に一致する」

という状態にできるかどうかを判定せよ。

制約

$3 \le N \le 10^{5}$

考えたこと

整数 $a, b, c, d$ をこの順に並べたとき

$b$ = $a$ XOR $c$
$c$ = $b$ XOR $d$

となることから、これらの両辺の XOR をとると

$a$ XOR $d$ = 0
⇔ $a = d$

となることが導かれる。つまり、円環状に数値を並べたとき、3 個置きに同じ値になることが必要ということになる。

よって、 $N$ が 3 の倍数でない場合には、 $N$ と 3 が互いに素であることから、結局すべての値が等しくなる必要があるということになる。その上、連続する 3 つの値 $a, b, c$ が $b$ = $a$ XOR $c$ という条件を満たすためには

$a = b = c = 0$

となる必要があることがわかる (逆にすべて 0 なら明らかに Yes)。以上から $N$ が 3 の倍数でない場合には、「すべて 0」であることが必要十分であることがわかった。

$N$ が 3 の倍数のとき

$N$ が 3 の倍数であれば、 $a$ XOR $b$ XOR $c$ = 0 を満たすような $a, b, c$ を用いて

$a, b, c, a, b, c, ...$

と円環状に並べたものが唯一の解となる。そのパターンは以下のものがありうる。

$a = b = c = 0$
$a = 0$ かつ $b = c (\neq 0)$
$a$ XOR $b$ XOR $c$ = 0 かつ $a, b, c \neq 0, a \neq b \neq c \neq a$

このようになっているかどうかは簡単な集計処理で調べられる。

コード

計算量は $O(N \log N)$ となる。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    map<int,int> ma;
    for (int i = 0; i < N; ++i) cin >> A[i], ++ma[A[i]];

    auto solve = [&]() -> bool {
        if (N % 3 != 0) return (ma[0] == N);
        vector<int> v;
        for (auto it : ma) v.push_back(it.first);
        if (v.size() == 1) return (ma[0] == N);
        else if (v.size() == 2) return (ma[0] == N/3);
        else if (v.size() == 3) {
            if ((v[0] ^ v[1] ^ v[2]) != 0) return false;
            return (ma[v[0]] == N/3 && ma[v[1]] == N/3 && ma[v[2]] == N/3);
        }
        else return false;
    };
    cout << (solve() ? "Yes" : "No") << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder AGC 035 A - XOR Circle (茶色, 300 点)

問題概要

制約

考えたこと

$N$ が 3 の倍数のとき

コード