https://onlinejudge.u-aizu.ac.jp/beta/room.html#KUPC2020Spring/problems/E
前提知識
解説
ゲーム問題は実験せよと古事記に書いてあるのでやる。 正確には勝ち負けだけ分かればいいので、grundy数が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; } }