けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 3057 First Kiss (RUPC 2019 day2-G)

面白かった

問題へのリンク

問題概要

Nim の「石が  1, 2, \dots, D 個しかとれないバージョン」を考える。

ただし勝敗の決まり方が、「先に石を取れなくなった方が負け」ではなく「先にいずれかの山の石の個数を 0 にした方が負け」である。

制約

  •  1 \le N \le 3 × 10^{5}

考えたこと

一瞬逆形かと思った。逆形とは、「最後に手を打った方が負け (通常は勝ち)」なゲームのことを指す。

が、今回は単に「石の個数をそれぞれ 1 減らした Nim」になる。最後  (1, 1, 1, ..., 1) になってここからどれか 1 つでも 0 にしたら終わりなので。実質的に「石の個数が 1 ずつ減った山」を扱うのと同じである。

次に今回は「 D 個までしか取れない」という制約があって、Grundy 数を考察する必要がある。ちょっと実験してみると例えば  D = 3 として、

  • 0 個: 0
  • 1 個: 1
  • 2 個: 2
  • 3 個: 3
  • 4 個: 0
  • 5 個: 1
  • 6 個: 2
  • 7 個: 3
  • 8 個: 0
  • 9 個: 1
  • ...

という感じに周期 4 になっていることがわかる。一般に周期  D+1 になる。よってまとめると

  • 最初に各山の石の個数を 1 減らす
  • 周期  D+1Grundy 数を求める
  • XOR をとって 0 かどうか判定する

で解くことができる。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, D; cin >> N >> D;
    vector<int> a(N), b(N);
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
        --a[i];
        b[i] = a[i] % (D + 1);
    }

    long long sum = 0;
    for (int i = 0; i < N; ++i) sum ^= b[i];
    if (!sum) puts("Second");
    else puts("First");
}