Atcoder Regular Contest 087 E. Prefix-free Game

E - Prefix-free Game

解法

まず文字列は $0$ と $1$ しか含まないので、完全二分木で考えました（この考え方は、一般的な文字列においても使えるらしく $Trie$木と呼ばれているらしいです）。

すると、木の頂点を順に塗りつぶしていく問題に変わります。ある頂点を選んだとき、その頂点を含む部分木全体と、その祖先すべてを塗ることになります。

よって各頂点を選んだときに、どのような部分木が残るのかに注意して $Grundy$ 数を求めればよさそうです。対称性に注意すると、現在の状況から遷移できる状態を考えて、高さ $k - 1$ の完全二分木の $Grundy$ 数 $g(k)$ は次のようになります。

$g(k) = mex\{0,\ g(k - 1),\ g(k - 1) \oplus g(k - 2),\ g(k - 1) \oplus g(k - 2) \oplus g(k - 3),\ ... \}$

このままだと効率よく求めることができませんが、実験をすると実は $k$ を割り切る最大の $2$ の冪であることがわかります（解説動画を見ると、$Grundy$ 数は、まず何も考えずに実験してくださいとおっしゃっていた）。

証明はよくわからないので、誰か教えてください。

$Trie$ 木を知らなくても普通に動的に木を作っていけばよいです。

ちなみによくあるテクニックですが、ある数 $x$ が $2$ で割り切れる回数は、__builtin_ctz(x)または__builtin_ctzll(x)で求められるので、今回の場合 $Grundy$ 数 $g(x)$ は1LL << __builtin_ctzll(x)です。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
#include <string>
#include <iostream>
#include <cassert>
#include <cmath>
#include <memory>
using namespace std;

struct node_t {
        shared_ptr<node_t> left, right;
        node_t(shared_ptr<node_t> l, shared_ptr<node_t> r) : left(l), right(r) {}
};

using node = shared_ptr<node_t>;

node new_node() {
        return node(new node_t(NULL, NULL));
}

int main() {
        int n;
        long long l;
        scanf("%d %lld", &n, &l);
        vector<string> s(n);
        for (int i = 0; i < n; i ++) {
                cin >> s[i];
        }
        node root = new_node();
        function<void (node, const string&, int)> dfs = [&](node u, const string &str, int depth) {
                if (depth >= (int) str.size()) {
                        return;
                }
                if (str[depth] == '0') {
                        if (u->left == NULL) {
                                u->left = new_node();
                        }
                        dfs(u->left, str, depth + 1);
                } else {
                        if (u->right == NULL) {
                                u->right = new_node();
                        }
                        dfs(u->right, str, depth + 1);
                }
        };
        for (int i = 0; i < n; i ++) {
                dfs(root, s[i], 0);
        }
        function<long long (long long)> get_grundy = [&](long long x) {
                return 1LL << __builtin_ctzll(x);
        };
        long long ans = 0;
        function<void (node, int)> dfs2 = [&](node u, int depth) {
                if ((u->left == NULL && u->right != NULL) || (u->left != NULL && u->right == NULL)) {
                        ans ^= get_grundy(l - depth);
                }
                if (u->left != NULL) {
                        dfs2(u->left, depth + 1);
                }
                if (u->right != NULL) {
                        dfs2(u->right, depth + 1);
                }
        };
        dfs2(root, 0);
        puts(ans ? "Alice" : "Bob");
        return 0;
}