集合と二人ゲーム [yukicoder No.715] - はまやんはまやんはまやん

前提知識

grundy数

考察過程

1. 与えられた数をソートした時に間が空いている数については独立して消されることになる
2. そして、連続している数については数自体というよりかは何個の数が連続しているかということだけ重要である
3. 言い換えると、いくつか連続している数のまとまりがあって独立に消していくときにどちらが必勝かを判定する
4. 独立に消せる場合はgrundy数を求めてxorを取ればいい
5. 今から求めるべきはx個数が連続している場合のgrundy数
6. 「解説見た」
7. 34を周期として計算できる（ただし、最初の方だけイレギュラー）
8. これに気づくのはきつい

解法

https://yukicoder.me/submissions/272894

問題を言い換えよう。
配列Aから、
1. 連続する数のグループに分割する
2. 各グループについて数の幅（最大-最小+1）を計算する
3. 幅についてgrundy数を計算する
を行い、全てのgrundy数のxorを取ることでどちらが必勝か判定する。
　
g(x) := x個の数が連続しているグループのgrundy数
これを計算していく。
端っこを消す場合と、中を消して2つのグループに分ける場合についてgrundy数を計算してmexを取っていく。
grundy数の基本は実験なので、実験してみる。
解説に34の周期になっているとあるが、気づかんかな…
　
ちなみに、xが小さい方は34の周期に沿っていない。
これは、分割が行えないことや、一気に全部消せることから来ているのだと思う。
根拠ないので注意。

int N, A[501010];
//---------------------------------------------------------------------------------------------------
int memo[1010];
int g(int x) {
    if (1010 <= x) return g(34 * 10 + x % 34);
    if (0 <= memo[x]) return memo[x];

    if (x == 0) return memo[x] = 0;
    if (x <= 2) return memo[x] = 1;

    set<int> gr;
    gr.insert(g(x - 2));
    gr.insert(g(x - 3));

    if (5 <= x) {
        rep(i, 1, x) {
            int j = x - i - 3;
            if (1 <= j) gr.insert(g(i) ^ g(j));
        }
    }

    int res = 0;
    while (gr.count(res)) res++;
    return memo[x] = res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    sort(A, A + N);

    rep(i, 0, 1010) memo[i] = -1;
    //rep(i, 0, 1010) printf("%d : %d\n", i, g(i));
    
    int L = 0;
    int gr = 0;
    while (L < N) {
        int i = L + 1;
        while (i < N and A[i] <= A[i - 1] + 1) i++;

        int len = A[i - 1] - A[L] + 1;
        gr ^= g(len);
        L = i;
    }

    if (gr == 0) printf("Second\n");
    else printf("First\n");
}