はまやんはまやんはまやん

hamayanhamayan's blog

XORのXOR [yukicoder 1082]

https://yukicoder.me/problems/no/1082

解説

https://yukicoder.me/submissions/499879

配列Aが固定されている場面でまずは考えてみよう。
すると、
Xは
B1 xor B2 xor B3 xor ... xor BN-1
(A1 xor A2) xor (A2 xor A3) xor (A3 xor A4) xor ... xor (AN-1 xor AN)
A1 xor A2 xor A2 xor A3 xor A3 xor A4 xor ... xor AN-1 xor AN
A1 xor (A2 xor A2) xor (A3 xor A3) xor (A4 xor ... xor AN-1) xor AN
A1 xor AN
となる。
x xor x = 0がなりたつため、最初と最後のxorだけが残る。
なので、最終的な結果はA[i] xor A[j]の値になる。
これは配列Aから2つを抜き出しているので、制約を見ると全探索できる。

int N, A[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    int ans = -1;
    rep(a, 0, N) rep(b, a + 1, N) chmax(ans, A[a] ^ A[b]);
    cout << ans << endl;
}