AOJ 3057 First Kiss (RUPC 2019 day2-G)

面白かった

問題へのリンク

問題概要

Nim の「石が 個しかとれないバージョン」を考える。

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

制約

• 

考えたこと

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

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

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

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

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

• 最初に各山の石の個数を 1 減らす
• 周期 で Grundy 数を求める
• 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");
}