CodeChef Floor Division Game

問題

Contest Page | CodeChef

A 君と B 君が数の集合 S1, S1, ..., Sn を使ってゲームをする。ゲームは A 君と B 君が交互に以下の行動をすることで進む。

• まだ残っている数から一つ選び, その数を Si/div に変更して再び集合にもどす。ただし, 2 <= div <= 6 であり, 割り算は小数点以下切り捨てである。また, 計算結果が 0 になった場合は 集合には戻さない。

集合に数がない状態でターンが回ってきたほうが負けである。どちらも最適に動いた場合勝つのはどちらか。

解法

見るからに grundy 数です。ですが素直に実装すると 数が大きすぎるので間に合いません(割り算する数が O(log N) 回なので間に合うのではと思うかもしれませんが, 場合分けが各状態で 複数あるので結局探索する状態数は O(N) 個)。

ということで規則性を探すのですが, 数を 6 未満になるまで 12 で割り算し続けたときの grundy 数と一致していることが実験するとわかります。なのでこれを実装しましょう。下の実装ではちょっとよくわからないことをやってますがやってることは同じです。

int grundy(ll x) {
    if (x == 0) return 0;
    if (x == 1) return 1;
    if (2 <= x && x <= 3) return 2;
    if (4 <= x && x <= 5) return 3;
    ll now = 72;
    while (1) {
        if (x < now) break;
        now *= 12;
    }
    ll unit = now/12;
    if (unit <= x && x < 2*unit) return 0;
    if (2*unit <= x && x < 4*unit) return 1;
    if (4*unit <= x && x < 8*unit) return 2;
    return 3;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        vector<ll> A(N);
        for (int i = 0; i < N; i++)
            cin >> A[i];
        int x = 0;
        for (int i = 0; i < N; i++) {
            int g = grundy(A[i]);
            x ^= g;
        }
        if (x) cout << "Henry" << endl;
        else cout << "Derek" << endl;
    }
    return 0;
}