ARC038 C問題

今回はgrundy数の問題。勉強したことがなかったので、蟻本を読んでから解きました。

grundy数は、今の状態から一手で行ける状態のgrundy数に含まれていない最小の非負整数です。
これは、grundy数がxの状態からはgrundy数が0〜x-1の状態へ移動できる、ということを保証するためにこうなっています。そうすればNimと全く同じようになりますよね。

ちなみに今回は豆の数が多いので、高速べき乗計算をxorに変えて使ってみたけど、実際には偶数奇数の場合分けだけでxorの累乗って計算できるんですよね。はい。

const int MAX = 100005;

int xor_ruijo(int x, int n){
    int res = 0;
    while(n > 0){
        if(n&1) res = res^x;
        x = x ^ x;
        n >>= 1;
    }
    return res;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int C[MAX], A[MAX];
    memset(C, 0, sizeof(C));
    memset(A, 0, sizeof(A));
    int N; cin >> N;
    for(int i=1; i<N; i++){
        cin >> C[i] >> A[i];
    }

    int grundy[N];
    memset(grundy, 0, sizeof(grundy));
    for(int i=1; i<N; i++){
        set<int> s;
        for(int j=1; j<=C[i]; j++){
            if(j <= i) s.insert(grundy[i-j]);
        }
        int g = 0;
        while(s.count(g) != 0) g++;
        grundy[i] = g;
    }
    int res = 0;
    for(int i=0; i<N; i++){
        if(A[i] != 0){
            res ^= xor_ruijo(grundy[i], A[i]);
        }
    }
    if(res != 0) cout << "First" << endl;
    else cout << "Second" << endl;
}