Codeforces Round #334 (Div. 1) C. Lieges of Legendre

問題

codeforces.com

解法

ゲームの構造的に, 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;
}