First Kiss [Ritsumeikan University Competitive Programming Camp 2019 Day 2 G]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp19Day2/problems/G

前提知識

• Grundy数

解説

https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp19Day2/3419060

Grundy数が分からない場合は、そちらを先に勉強しよう。
逆にそれがわかっていれば、この問題は難しくない。
Grundy数の問題はまずは実験することが大切なので、実験用コードを書いてみる。
　

g(1,1) = 0
g(2,1) = 1
g(3,1) = 0
g(4,1) = 1
g(5,1) = 0
g(6,1) = 1
g(7,1) = 0
g(8,1) = 1
g(9,1) = 0

g(1,2) = 0
g(2,2) = 1
g(3,2) = 2
g(4,2) = 0
g(5,2) = 1
g(6,2) = 2
g(7,2) = 0
g(8,2) = 1
g(9,2) = 2

0,1,...,Dの連続なのでは？という仮説が立つので、それを実装するとAC。
未証明AC

int N, D, A[301010];
//---------------------------------------------------------------------------------------------------
int zikken(int n, int d) {
    if (n == 1) return 0;

    set<int> gg;
    rep(i, 1, n) if (n - i <= d) gg.insert(zikken(i, d));

    int ng = 0;
    while (gg.count(ng)) ng++;
    return ng;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> D;
    rep(i, 0, N) cin >> A[i];

    //rep(i, 1, 20) rep(d, 1, 2) printf("g(%d,%d) = %d\n", i, d, zikken(i, d));

    int g = 0;
    rep(i, 0, N) g ^= (A[i] - 1) % (D + 1);

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