【精進5】AGC045-A

前の精進つながりで$\mathrm{xor}$の問題。後ろから考える。

問題

A - Xor Battle
人$0$と人$1$がゲームをする。変数$x=0$とし$i$回目のラウンドで人$S_i$はなにもしないか$x \gets x\oplus A_i$とするかを選択する。最終的に人$0$は$x=0$を、人$1$は$x\ne 0$を目指すとき達成するのはどちらか？

解法

たいていのケースで人$1$が有利なルールに見えるため人$0$が勝つのがどのようなケースなのかを考察する。後ろから考えていく。$i=N$で$S_i=1$ならばその時点での$x$に対し、$x,x\oplus A_i$の少なくとも一方が$0$でないため人$0$は負ける。$S_i=0$の場合、$x\in\lbrace 0,A_i\rbrace$なら人$0$は勝つ。同様にある$i+1$で$x\in U$ならば人$0$が勝つ場合、$i$での勝利条件がどうなるかを考える。 $S_i=1$の場合、条件は$A_i \in U$かつ$x\in U$である。$S_i=0$の場合条件は$x\in U \cup \lbrace y\oplus A_i | y\in U \rbrace$である。これらの考察から人$0$の勝利条件は次のようになることが分かる。

$\lbrace A_{i+1},\dots,A_N \rbrace$が張る空間に$A_i$が含まれないならば$S_i = 0$である。

この判定は前回の解説と同様の方法でできる。

#include "template.hpp"
void solve() {
    LL(n);
    vl a(n);
    input(a);
    STR(s);
    vl basis;
    auto in = [&basis](ll num) -> bool {
        for(auto e : basis)
            chmin(num, e ^ num);
        if(num) {
            basis.push_back(num);
            return true;
        }
        return false;
    };
    for(int i = n - 1; i >= 0; i--) {
        bool flag = in(a[i]);
        if(s[i] == '1' and flag) {
            print(1);
            return;
        }
    }
    print(0);
}

int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout << std::setprecision(16);
    int t = 1;
    cin >> t;
    rep(_, t) {
        solve();
    }
}