Codeforces Round #334 (Div. 1) C. Lieges of Legendre
解法
ゲームの構造的に, grundy 数が使えます。
f(n) = (皿に石が n 個乗っている際の grundy 数) とすると, 皿に石が n 個乗っている状態からは,
(a)皿に石が n-1 個乗っている状態, または
(b)石が n/2 個乗っている皿が k 個ある状態 (n が偶数の時のみ)
のいずれかの状態に遷移できるので,
f(n-1), f(n/2) のみを気にすれば良いことになります。また, k が偶数の時は f(n/2) がどんな値であろうと, (b) の状態は 0 になるので, 簡単に grundy 数が求まります。具体的には,
f(0) = 0, f(1) = 1, f(2) = 2 となり, 以降は f(2n) = 1, f(2n-1) = 0 となります。
k が奇数の場合は少し面倒です。まず
f(0) = 0, f(1) = 1, f(2) = 0, f(3) = 1, f(4) = 2 と求まります。これ以降は, f(2n-1) = 0 です。
すると, f(2n) はどうなるかというと, f(2n-1) には遷移できるので, grundy 数が 1 以上になるのは確定です。次の値がどうなるかは, f(n) がどのような値だったかによりますが, f(n) = 1 の場合は f(2n) = 2, f(n) = 2 の場合は f(2n) = 1 です。f(n) の値が 2 より大きくなることは無いので, f(n) は, n の値が 2 倍されるごとに 1 と 2 の値を交互に取ることに気づきます。これを上手く使って grundy 数を求めましょう。
const int MAXN = 100100; int a[MAXN]; int main() { cin.tie(0); ios::sync_with_stdio(false); int n, k; cin >> n >> k; for (int i = 0; i < n; i++) { cin >> a[i]; } if (k%2 == 0) { int x = 0; for (int i = 0; i < n; i++) { if (a[i] <= 2) x ^= a[i]; else x ^= (a[i]%2)^1; } if (x != 0) cout << "Kevin" << endl; else cout << "Nicky" << endl; } else { int x = 0; vector<int> memo = {0, 1, 0, 1, 2}; for (int i = 0; i < n; i++) { if (a[i] <= 4) { x ^= memo[a[i]]; } else { int tmp = a[i]; int cnt = 1; if (tmp%2) continue; while (tmp > 4 && tmp%2 == 0) { tmp /= 2; cnt++; } if (tmp <= 4) cnt += memo[tmp]; x ^= (cnt%2) + 1; } } if (x != 0) cout << "Kevin" << endl; else cout << "Nicky" << endl; } return 0; }