面白かった
問題概要
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"); }