数列ゲーム [Kyoto University Programming Contest 2020 Spring E]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#KUPC2020Spring/problems/E

前提知識

• grundy数

解説

ゲーム問題は実験せよと古事記に書いてあるのでやる。 正確には勝ち負けだけ分かればいいので、grundy数が0になる規則性を探してくる。 ひたすら実験して見てみると、以下のルールが得られる。

• Nが奇数
  • grundy数は配列Aの総和%2となるので、それをみてやる
• Nが偶数
  • grundy数の計算は複雑そうなので、0となるルールだけ探す
  • 総和%2=0である、かつ、最小の数が偶数である

これを使って勝ち負けを答えよう。

int grundy[10][10][10][10][10];
void labo() {
    rep(a, 0, 10) rep(b, 0, 10) rep(c, 0, 10) rep(d, 0, 10) rep(e, 0, 10) {
        set<int> gr;
        if (0 < a) gr.insert(grundy[a - 1][b][c][d][e]);
        if (0 < b) gr.insert(grundy[a][b - 1][c][d][e]);
        if (0 < c) gr.insert(grundy[a][b][c - 1][d][e]);
        if (0 < d) gr.insert(grundy[a][b][c][d - 1][e]);
        if (0 < e) gr.insert(grundy[a][b][c][d][e - 1]);
        if (0 < a && 0 < b && 0 < c && 0 < d && 0 < e) gr.insert(grundy[a - 1][b - 1][c - 1][d - 1][e - 1]);

        while (gr.count(grundy[a][b][c][d][e])) grundy[a][b][c][d][e]++;

        printf("g[%d][%d][%d][%d][%d] = %d (%d)\n", a, b, c, d, e, grundy[a][b][c][d][e], a + b + c + d + e);
    }
}
void labo2() {
    rep(a, 0, 10) rep(b, 0, 10) rep(c, 0, 10) rep(d, 0, 10) {
        set<int> gr;
        if (0 < a) gr.insert(grundy[0][a - 1][b][c][d]);
        if (0 < b) gr.insert(grundy[0][a][b - 1][c][d]);
        if (0 < c) gr.insert(grundy[0][a][b][c - 1][d]);
        if (0 < d) gr.insert(grundy[0][a][b][c][d - 1]);
        if (0 < a && 0 < b && 0 < c && 0 < d) gr.insert(grundy[0][a - 1][b - 1][c - 1][d - 1]);

        while (gr.count(grundy[0][a][b][c][d])) grundy[0][a][b][c][d]++;

        printf("g[%d][%d][%d][%d] = %d (%d)\n", a, b, c, d, grundy[0][a][b][c][d], a + b + c + d);
    }
}
void labo3() {
    rep(a, 0, 10) rep(b, 0, 10) rep(c, 0, 10) {
        set<int> gr;
        if (0 < a) gr.insert(grundy[0][0][a - 1][b][c]);
        if (0 < b) gr.insert(grundy[0][0][a][b - 1][c]);
        if (0 < c) gr.insert(grundy[0][0][a][b][c - 1]);
        if (0 < a && 0 < b && 0 < c) gr.insert(grundy[0][0][a - 1][b - 1][c - 1]);

        while (gr.count(grundy[0][0][a][b][c])) grundy[0][0][a][b][c]++;

        printf("g[%d][%d][%d] = %d (%d)\n", a, b, c, grundy[0][0][a][b][c], a + b + c);
    }
}

void labo4() {
    rep(a, 0, 10) rep(b, 0, 10) {
        set<int> gr;
        if (0 < a) gr.insert(grundy[0][0][0][a - 1][b]);
        if (0 < b) gr.insert(grundy[0][0][0][a][b - 1]);
        if (0 < a && 0 < b) gr.insert(grundy[0][0][0][a - 1][b - 1]);

        while (gr.count(grundy[0][0][0][a][b])) grundy[0][0][0][a][b]++;

        printf("g[%d][%d] = %d (%d)\n", a, b, grundy[0][0][0][a][b], a + b);
    }
}







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

    if (N % 2 == 1) {
        int tot = 0;
        rep(i, 0, N) tot = (tot + A[i]) % 2;

        if (tot % 2 == 0) cout << "Second" << endl;
        else cout << "First" << endl;
    }
    else {
        int tot = 0;
        rep(i, 0, N) tot = (tot + A[i]) % 2;

        int mi = inf;
        rep(i, 0, N) chmin(mi, A[i]);

        if (tot % 2 == 0 && mi % 2 == 0) cout << "Second" << endl;
        else cout << "First" << endl;
    }
}