ARC087 - E問題: Prefix-free Game - 日々ｄｒｄｒする人のメモ

解いたので解法メモ
URL: E - Prefix-free Game

問題

0, 1から構成される文字列が ${N}$ 個含まれる、良い文字列集合である ${S}$ が与えられる。この良い文字列集合の要素では、長さ ${1 \le |s| \le L}$ が成り立ち、異なる要素s, tについてsがtのprefixではなく、tがsのprefixでない (この関係をprefix-freeという)。

AliceとBobが順番に、この集合 ${S}$ に良い文字列集合を保つように文字列を追加していき、追加できなくなった方が負けである。どっちが勝つか判定せよ。

制約

${1 \le N \le 10^5}$
${1 \le L \le 10^{18}}$
${\sum_{s_i \in S} |s_i| \le 10^5}$

解法

トライ木とGrundy数を使う。
集合 ${S}$ に含まれる ${N}$ 個の文字列sでトライ木を構築する。(このトライ木は深さLの完全二分木として考えられる)
すると、 ${2^L}$ 種類の文字列のうち、追加できる文字列候補は、いくつかの完全二分木に分かれる。
例えば ${L = 3, S = \{00, 100\}}$ である場合、以下のように高さ1の完全二分木2つと高さ0の完全二分木1つが得られる。
f:id:smijake3:20180503041926p:plain

ここからは、各高さ ${k}$ の完全二分木についてGrundy数を求めていく。
この高さ ${k}$ の木から文字列を取っていく場合、根から深さ0,1, 2, ..., k-1の要素を取ることが考えられ、それに伴い更にいくつかの完全二分木に分割される。
例えば、高さ3の木から根から深さ2の要素をとる場合、以下の図のように高さ2と高さ1の木が生成される。
f:id:smijake3:20180503035011p:plain

この時、深さdでとった時の各完全二分木のGrundy数のxor和を取る(上の例では、(高さ1のGrundy数) xor (高さ2のGrundy数) = 2 xor 1 = 3)。これを各深さで計算し、これらの中で出現しなかった最小の数を高さ ${k}$ のGrundy数とする。具体的に深さd (d > 0)でとる場合、高さk, k-1, ..., k+1-dの木のGrundy数のxor和になる。深さ0でとる場合は0になる。
この時、各Grundy数は高さ0から
1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2, 1, ...
となる。この結果を無限長の数列とみなし、4の倍数の番目のみを抜き出し、4で割ると同じ数列が得られる。
ここから、高さkのk+1について4の倍数である限り4で割り続け、1もしくは2を、4で割った回数だけ4倍にしたものがGrundy数となる。

解としては、集合 ${S}$ から生成された完全二分木らのGrundy数のxorを取り、これが0以外ならばAlice、0ならばBobを勝者として出力すればよい。

提出 (Python3): Submission #2448233 - AtCoder Regular Contest 087

N, L = map(int, input().split())

# トライ木構築
# 各nodeには0 or 1の値が付き、1は文字列sの終端を表す (それ以降の子ノードは取れない文字列になる)
make = lambda:[None, None, 0]
root = make()
def construct(s):
    n = root
    for i in s:
        if n[i] is None:
            n[i] = n = make()
        else:
            n = n[i]
    n[2] = 1

for i in range(N):
    s = map(int, input())
    construct(s)

# トライ木のdfs探索
caps = {}
st = [(root, 0, 0)]
while st:
    n, i, l = st.pop()
    if i:
        if n[1] is None:
            caps[L - l] = caps.get(L - l, 0) + 1
        else:
            if not n[1][2]:
                st.append((n[1], 0, l+1))
    else:
        st.append((n, 1, l))
        if n[0] is None:
            caps[L - l] = caps.get(L - l, 0) + 1
        else:
            if not n[0][2]:
                st.append((n[0], 0, l+1))

# 各高さの完全二分木についてGrundy数を計算
ans = 0
for v in caps:
    k = caps[v]
    if k % 2 == 0:
        continue
    v -= 1
    r = 1
    while v % 4 == 3:
        v //= 4
        r *= 4
    if v % 4 == 1:
        ans ^= r * 2
    else:
        ans ^= r
print('Alice' if ans else 'Bob')