Problem:


Score : 700 points

Problem Statement

For strings s and t, we will say that s and t are prefix-free when neither is a prefix of the other.

Let L be a positive integer. A set of strings S is a good string set when the following conditions hold true:

Each string in S has a length between 1 and L (inclusive) and consists of the characters 0 and 1.

Any two distinct strings in S are prefix-free.

We have a good string set S = \{ s_1, s_2, ..., s_N \}. Alice and Bob will play a game against each other. They will alternately perform the following operation, starting from Alice:

Add a new string to S. After addition, S must still be a good string set.

The first player who becomes unable to perform the operation loses the game. Determine the winner of the game when both players play optimally.

Constraints

1 \leq N \leq 10^5

1 \leq L \leq 10^{18}

s_1, s_2, ..., s_N are all distinct.

{ s_1, s_2, ..., s_N } is a good string set.

|s_1| + |s_2| + ... + |s_N| \leq 10^5

Input

Input is given from Standard Input in the following format:

N L
s_1
s_2
:
s_N

Output

If Alice will win, print Alice; if Bob will win, print Bob.

Sample Input 1

2 2
00
01

Sample Output 1

Alice

If Alice adds 1, Bob will be unable to add a new string.

Sample Input 2

2 2
00
11

Sample Output 2

Bob

There are two strings that Alice can add on the first turn: 01 and 10.
In case she adds 01, if Bob add 10, she will be unable to add a new string.
Also, in case she adds 10, if Bob add 01, she will be unable to add a new string.

Sample Input 3

3 3
0
10
110

Sample Output 3

Alice

If Alice adds 111, Bob will be unable to add a new string.

Sample Input 4

2 1
0
1

Sample Output 4

Bob

Alice is unable to add a new string on the first turn.

Sample Input 5

1 2
11

Sample Output 5

Alice

Sample Input 6

2 3
101
11

Sample Output 6

Bob



Sample input:
2 2
00
01


Sample output:
Alice

Submission status: Wrong Answer

Solution code:
n,l = map(int, input().split())
s = [input() for i in range(n)]
s.sort()

inputs = []
if s[0][0] != '0':
    inputs.append('0')
if s[-1][0] != '1':
    inputs.append('1')

for i in range(n):
    if s[i][-1] == '0':
        if (i==n-1 or s[i+1] != s[i][:-1]+'1'):
            inputs.append(s[i][:-1]+'1')
    elif s[i][-1] == '1':
        if (i==0 or s[i-1] != s[i][:-1]+'0'):
            inputs.append(s[i][:-1]+'0')
inputs.sort()
lt = len(inputs)
trees = []
for i in range(lt):
    if i==lt-1 or inputs[i] != inputs[i+1][:len(inputs[i])]:
        trees.append(inputs[i])
lt = len(trees)
if lt == 0:
    print('Bob')
    exit()
elif lt == 1:
    print('Alice')
    exit()


g = 0
for t in trees:
    g = g ^ (l - len(t)-1)
if g%2 == 0:
    print('Bob')
    exit()
else:
    print('Alice')
    exit()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

N, L = map(int, readline().split())
node = set([1])
for _ in range(N):
    S = list(map(int, readline().strip()))
    pre = 1
    for s in S:
        vn = 2*pre + s
        if vn not in node:
            node.add(vn)
        pre = vn
cnt = 0
for d in node:
    if (2*d in node) ^ (2*d + 1 in node):
        depth = L-d.bit_length()+1
        cnt ^= (-depth&depth)

print('Alice' if cnt else 'Bob')

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

N, L = map(int, readline().split())
node = set([1])
for _ in range(N):
    S = list(map(int, readline().strip()))
    ls = len(S)
    pre = 1
    for s in S:
        vn = 2*pre + s
        if vn not in node:
            node.add(vn)
        pre = vn
cnt = 0
for d in node:
    h = 0
    if 2*d in node:
        h += 1
    if 2*d+1 in node:
        h += 1
    if h == 1:
        depth = L-d.bit_length()+1
        cnt ^= (-depth&depth)

print('Alice' if cnt else 'Bob')

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

    N, L = map(int, input().split())
    dic = defaultdict(int)
    for _ in range(N):
        s = input().rstrip('\n')
        for i in range(len(s)):
            dic[s[:i+1]] = 1

    g = 0
    key = list(dic.keys())
    for s in key:
        t = [si for si in s]
        t[-1] = '0' if t[-1] == '1' else '1'
        t = ''.join(t)
        if not dic[t]:
            tmp = L - len(s) + 1
            cnt = 0
            while tmp % 2 == 0:
                tmp //= 2
                cnt += 1
            g ^= (2**cnt)

    if g:
        print('Alice')
    else:
        print('Bob')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

    N, L = map(int, input().split())
    dic = defaultdict(int)
    for _ in range(N):
        s = input().rstrip('\n')
        s = [si for si in s]
        for i in range(len(s)):
            dic[''.join(s)] = 1
            s.pop()

    g = 0
    key = list(dic.keys())
    for s in key:
        t = [si for si in s]
        t[-1] = '0' if t[-1] == '1' else '1'
        t = ''.join(t)
        if not dic[t]:
            tmp = L - len(s) + 1
            cnt = 0
            while tmp % 2 == 0:
                tmp //= 2
                cnt += 1
            g ^= (2**cnt)

    if g:
        print('Alice')
    else:
        print('Bob')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

    N, L = map(int, input().split())
    dic = defaultdict(int)
    for _ in range(N):
        s = input().rstrip('\n')
        s = [si for si in s]
        for i in range(len(s)):
            dic[''.join(s[:i+1])] = 1

    g = 0
    key = list(dic.keys())
    for s in key:
        t = [si for si in s]
        t[-1] = '0' if t[-1] == '1' else '1'
        t = ''.join(t)
        if not dic[t]:
            tmp = L - len(s) + 1
            cnt = 0
            while tmp % 2 == 0:
                tmp //= 2
                cnt += 1
            g ^= (2**cnt)

    if g:
        print('Alice')
    else:
        print('Bob')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    
    N, L = map(int, input().split())
    dic = {}
    for _ in range(N):
        s = input().rstrip('\n')
        for i in range(len(s)):
            dic[s[:i+1]] = 1
    
    g = 0
    for s in dic.keys():
        t = [si for si in s]
        t[-1] = '0' if t[-1] == '1' else '1'
        t = ''.join(t)
        if t not in dic:
            tmp = L - len(s) + 1
            cnt = 0
            while tmp % 2 == 0:
                tmp //= 2
                cnt += 1
            g ^= (2**cnt)
    
    if g:
        print('Alice')
    else:
        print('Bob')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

N, L = map(int, input().split())
dic = {}
for _ in range(N):
    s = input().rstrip('\n')
    for i in range(len(s)):
        dic[s[:i+1]] = 1

g = 0
for s in dic.keys():
    t = [si for si in s]
    t[-1] = '0' if t[-1] == '1' else '1'
    t = ''.join(t)
    if t not in dic:
        tmp = L - len(s) + 1
        cnt = 0
        while tmp % 2 == 0:
            tmp //= 2
            cnt += 1
        g ^= (2**cnt)

if g:
    print('Alice')
else:
    print('Bob')

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

N, L = map(int, input().split())
dic = {}
for _ in range(N):
    s = input().rstrip('\n')
    for i in range(len(s)):
        dic[s[:i+1]] = 1

g = 0
for s in dic.keys():
    t = s[:-1] + str(int(s[-1] == '0'))
    if t not in dic:
        tmp = L - len(s) + 1
        cnt = 0
        while tmp % 2 == 0:
            tmp //= 2
            cnt += 1
        g ^= (2**cnt)

if g:
    print('Alice')
else:
    print('Bob')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(level=0, u=0):
        if len(to[(level, u)]) == 1:
            cnt_tree[l - level] += 1
        for kl, ku in to[(level, u)]:
            dfs(kl, ku)

    to = defaultdict(set)
    n, l = map(int, input().split())
    ss = [input()[:-1] for _ in range(n)]

    # 各sをパスと見て、辺を張っていく
    for s in ss:
        now_l = 0
        now_u = 0
        for c in s:
            nxt_l = now_l + 1
            nxt_u = (now_u << 1) + int(c)
            to[(now_l, now_u)].add((nxt_l, nxt_u))
            now_l, now_u = nxt_l, nxt_u
    # print(to)

    # パスで分離された木のレベルと個数を数える
    cnt_tree = defaultdict(int)
    dfs()
    #print(cnt_tree)

    # Grundy数をlv & -lvで求め、xorをとる
    sum_xor = 0
    for lv, cnt in cnt_tree.items():
        if cnt % 2 == 0: continue
        sum_xor ^= lv & -lv

    if sum_xor == 0:
        print("Bob")
    else:
        print("Alice")

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
#from collections import defaultdict
sys.setrecursionlimit(10**6)

def input():
	return sys.stdin.readline()[:-1]
n, l = map(int, input().split())
ss = [input() for _ in range(n)]

def addTree(tree, sentence):
	if not sentence[0:]:
		return None   

	if sentence[0] not in tree:
		tree[sentence[0]] = {}

	tree[sentence[0]] = addTree(tree[sentence[0]], sentence[1:])

	return tree

def createTree(sentences):    
	tree = {}
	for sentence in sentences:
		tree = addTree(tree, sentence)

	return tree

tree = createTree(ss)
#print(tree)

grundy = 0
def dfs(cur, level):
	global grundy
	if cur is None:
		return
	elif len(cur) == 1:
		grundy ^= (l-level) & (-l+level)
	for k in cur.keys():
		dfs(cur[k], level+1)
	return
	
dfs(tree, 0)

if grundy == 0:
	print("Bob")
else:
	print("Alice")

Submission status: Time Limit Exceeded

Solution code:
import sys
#from collections import defaultdict
sys.setrecursionlimit(10**6)

def input():
	return sys.stdin.readline()[:-1]
n, l = map(int, input().split())
ss = [input() for _ in range(n)]

def addTree(tree, sentence):
	if not sentence[0:]:
		return None   

	if sentence[0] not in tree:
		tree[sentence[0]] = {}

	tree[sentence[0]] = addTree(tree[sentence[0]], sentence[1:])

	return tree

def createTree(sentences):    
	tree = {}
	for sentence in sentences:
		tree = addTree(tree, sentence)

	return tree

tree = createTree(ss)
#print(tree)

grundy = 0
def dfs(cur, level):
	global grundy
	if cur is None:
		return
	elif len(cur) == 1:
		grundy ^= (l-level) & (-l+level)
	for k in cur.keys():
		dfs(cur[k], level+1)
	return
	
dfs(tree, 0)

if grundy == 0:
	print("Bob")
else:
	print("Alice")

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
def input():
	return sys.stdin.readline()[:-1]
n, l = map(int, input().split())
ss = [input() for _ in range(n)]
#prefix = set()
#out = dict()
child = defaultdict(int)
for s in ss:
	u = ""
	for i in range(len(s)):
		child[u] |= int(s[i]) + 1
		u += s[i]

grundy = 0
for k, v in child.items():
	#print(k, v)
	le = len(k)
	if v == 1 or v == 2:
		grundy ^= (l-le) & (-l+le)

if grundy == 0:
	print("Bob")
else:
	print("Alice")

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
def input():
	return sys.stdin.readline()[:-1]
n, l = map(int, input().split())
ss = [input() for _ in range(n)]
child = defaultdict(int)
for s in ss:
	u = ""
	for i in range(len(s)):
		child[u] |= int(s[i]) + 1
		u += s[i]

grundy = 0
for k, v in child.items():
	#print(k, v)
	le = len(k)
	if v == 1 or v == 2:
		grundy ^= (l-le) & (-l+le)

if grundy == 0:
	print("Bob")
else:
	print("Alice")

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]
n, l = map(int, input().split())
ss = [input() for _ in range(n)]
prefix = set()
#out = dict()
for s in ss:
	u = ""
	for i in range(len(s)):
		u += s[i]
		prefix.add(u)
		#out[u] = 1
grundy = 0
for p in prefix:
	le = len(p)
	if p[le-1] == "0":
		t = p[:le-1] + "1"
	else:
		t = p[:le-1] + "0"
	if t not in prefix:
		grundy ^= (l-le+1) & (-l+le-1)

if grundy == 0:
	print("Bob")
else:
	print("Alice")

Submission status: Time Limit Exceeded

Solution code:
n, l = map(int, input().split())
ss = [input() for _ in range(n)]
prefix = set()
for s in ss:
	u = ""
	for i in range(len(s)):
		u += s[i]
		prefix.add(u)
grundy = 0
for p in prefix:
	le = len(p)
	if p[le-1] == "0":
		t = p[:le-1] + "1"
	else:
		t = p[:le-1] + "0"
	if t not in prefix:
		grundy ^= (l-le+1) & (-l+le-1)

if grundy == 0:
	print("Bob")
else:
	print("Alice")

Submission status: Time Limit Exceeded

Solution code:
n, l = map(int, input().split())
ss = [input() for _ in range(n)]
prefix = set()
out = dict()
for s in ss:
	u = ""
	for i in range(len(s)):
		u += s[i]
		prefix.add(u)
		out[u] = 1
grundy = 0
for p in list(prefix):
	le = len(p)
	if p[le-1] == "0":
		t = p[:le-1] + "1"
	else:
		t = p[:le-1] + "0"
	if t not in out:
		grundy ^= (l-le+1) & (-l+le-1)

if grundy == 0:
	print("Bob")
else:
	print("Alice")

Submission status: Time Limit Exceeded

Solution code:
n, l = map(int, input().split())
ss = [input() for _ in range(n)]
prefix = set()
for s in ss:
	u = ""
	for i in range(len(s)):
		u += s[i]
		prefix.add(u)
grundy = 0
for p in list(prefix):
	le = len(p)
	if p[le-1] == "0":
		t = p[:le-1] + "1"
	else:
		t = p[:le-1] + "0"
	if t not in prefix:
		grundy ^= (l-le+1) & (-l+le-1)

if grundy == 0:
	print("Bob")
else:
	print("Alice")

Submission status: Time Limit Exceeded

Solution code:
n, l = map(int, input().split())
ss = [input() for _ in range(n)]
prefix = set()
for s in ss:
	for i in range(len(s)):
		prefix.add(s[:i+1])
grundy = 0
for p in list(prefix):
	if p[-1] == "0":
		t = p[:-1] + "1"
	else:
		t = p[:-1] + "0"
	if t not in prefix:
		grundy ^= (l-len(t)+1) & (-l+len(t)-1)

if grundy == 0:
	print("Bob")
else:
	print("Alice")

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]
n, l = map(int, input().split())
ss = [input() for _ in range(n)]
prefix = set()
for s in ss:
	for i in range(len(s)):
		prefix.add(s[:i+1])
grundy = 0
for p in list(prefix):
	le = len(p)
	if p[le-1] == "0":
		t = p[:le-1] + "1"
	else:
		t = p[:le-1] + "0"
	if t not in prefix:
		grundy ^= (l-le+1) & (-l+le-1)

if grundy == 0:
	print("Bob")
else:
	print("Alice")

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]
n, l = map(int, input().split())
ss = [input() for _ in range(n)]
prefix = set()
for s in ss:
	for i in range(len(s)):
		prefix.add(s[:i+1])
grundy = 0
for p in list(prefix):
	if p[-1] == "0":
		t = p[:-1] + "1"
	else:
		t = p[:-1] + "0"
	if t not in prefix:
		grundy ^= (l-len(t)+1) & (-l+len(t)-1)

if grundy == 0:
	print("Bob")
else:
	print("Alice")

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10000)
INF = float('inf')

N, L = list(map(int, input().split()))
S = set()
for _ in range(N):
    S.add(input())


# 追加できるのが 01... だけで
# L が 4 とすると
# 01: 次はない
# 010: 011 がある
# 011: 010 がある
# 0100: 011, 0101 がある
# 0101: 011, 0100
# 0110: 010, 0111
# 0111: 010, 0110
# 候補の長さと L だけによって次の候補の長さと数が決まる
def grundy(size):
    """
    :param int size: 候補の長さ
    :return:
    """
    # gs = {0}
    # g = 0
    # for sz in range(size + 1, L + 1):
    #     g ^= grundy(sz)
    #     gs.add(g)
    #
    # i = 0
    # while i in gs:
    #     i += 1
    # return i
    i = 1
    while (L - size + 1) % i == 0:
        i *= 2
    return i // 2


prefixes = set()
for s in S:
    for i in range(len(s)):
        prefixes.add(s[:i + 1])

ok_set = set()
ng_set = deque()
ng_set.append('')
while len(ng_set) > 0:
    ng = ng_set.popleft()
    if len(ng) >= L:
        continue
    for c in '01':
        if ng + c not in prefixes:
            ok_set.add(ng + c)
        elif ng + c not in S:
            ng_set.append(ng + c)

g = 0
for ok in ok_set:
    g ^= grundy(len(ok))
if g != 0:
    print('Alice')
else:
    print('Bob')

Submission status: Time Limit Exceeded

Solution code:
N, L = map(int, input().split())
S = [input() for _ in range(N)]

bits = dict()
for s in S:
    part = ''
    for i in range(len(s)):
        if not bits.get(part):
            bits[part] = {s[i]}
        else:
            bits[part].add(s[i])
        part += s[i]
eo = [True, True]


def walk(current):
    ne = bits.get(current)
    if ne == {'0', '1'}:
        walk(current + '0')
        walk(current + '1')
    elif ne == {'0'}:
        eo[(L - len(current)) & 1] = not(eo[(L - len(current)) & 1])
        walk(current + '0')
    elif ne == {'1'}:
        eo[(L - len(current)) & 1] = not(eo[(L - len(current)) & 1])
        walk(current + '1')

walk('')
print('Bob' if eo == [True, True] else 'Alice')

Submission status: Time Limit Exceeded

Solution code:
def main():
    N,L = map(int,input().split())
    keys = []
    grundy_num=0
    for i in range(N):
        s = input()
        #merge node:
        while len(s)>0:
            if s[-1]=='1' and s[:-1]+'0' in keys:
                keys.remove(s[:-1]+'0')
                s = s[:-1]
            elif s[-1]=='0' and s[:-1]+'1' in keys:
                keys.remove(s[:-1]+'1')
                s = s[:-1]
            else:
                if s!="":
                    keys.append(s)
                break
    if len(keys):
        keys = sorted(keys,key=len,reverse=True)
        grundy_list = []
        while len(keys):
            j = keys[0]
            keys.remove(j)
            temp_s = list(reversed(bin(L-len(j)+1)))
            grundy_list.append(1 << temp_s.index('1'))
            if j[:-1]!="":
                keys.append(j[:-1])
            j = j[:-1]
            #merge node
            while len(j)>0:
                if j[-1]=='1' and j[:-1]+'0' in keys:
                    keys.remove(j[:-1]+'0')
                    keys.remove(j)
                    j = j[:-1]
                    if j!="":
                        keys.append(j)
                elif j[-1]=='0' and j[:-1]+'1' in keys:
                    keys.remove(j[:-1]+'1')
                    keys.remove(j)
                    j = j[:-1]
                    if j!="":
                        keys.append(j)
                else:
                    break
            keys = sorted(keys,key=len,reverse=True)
        grundy_num = grundy_list[0]
        for i in range(1,len(grundy_list)):
            grundy_num = grundy_num^grundy_list[i]
    print("Bob" if grundy_num==0 else "Alice")


if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n, l = map(int, input().split())
nums = defaultdict(set)
for s in (input() for _ in range(n)):
    nums[l - len(s) + 1].add(int(s, 2) + (1 << len(s)))

xor = 0
for i in range(min(nums), l + 1):
    ni = nums[i]
    for k in ni:
        if k ^ 1 not in ni:
            xor ^= i & -i
        nums[i + 1].add(k // 2)
    del nums[i]

print('Alice' if xor else 'Bob')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n, l = map(int, input().split())
nums = defaultdict(set)
for s in (input() for _ in range(n)):
    nums[l - len(s) + 1].add(int(s, 2) + (1 << len(s)))

xor = 0
for i in range(min(nums), l + 1):
    ni = nums[i]
    for k in ni:
        if k ^ 1 not in ni:
            xor ^= i & -i
        nums[i + 1].add(k // 2)

print('Alice' if xor else 'Bob')

Submission status: Time Limit Exceeded

Solution code:
n, l = map(int, input().split())
ss = [input() for _ in range(n)]

ds = set()
bs = set()
for s in ss:
    i = int(s, 2) + (1 << len(s))
    while i >= 1:
        if i in ds:
            bs.add(i << 1)
            bs.add((i << 1) + 1)
            break
        ds.add(i)
        i >>= 1
# print(ds)
# print(bs)
ds.discard(1)
xor = 0
ofs = l + 2
for r in ds - bs:
    level = ofs - r.bit_length()
    xor ^= level & -level

print('Alice' if xor else 'Bob')

Submission status: Accepted

Solution code:
class Node():
    def __init__(self):
        self.lt = None
        self.rt = None
        self.dep = None

class Trie():
    def __init__(self):
        self.root = Node()
        self.root.dep = 0

    def add(self, string):
        node = self.root
        for s in string:
            if s == '0':
                if node.lt is None:
                    node.lt = Node()
                    node.lt.dep = node.dep + 1
                node = node.lt
            else:
                if node.rt is None:
                    node.rt = Node()
                    node.rt.dep = node.dep + 1
                node = node.rt

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

trie = Trie()

for _ in range(N):
    s = input()
    trie.add(s)

subgame = []
stack = [trie.root]

while stack:
    node = stack.pop()
    if node.lt is None and node.rt is None:
        continue
    elif node.rt is None:
        stack.append(node.lt)
        subgame.append(L - node.dep)
    elif node.lt is None:
        stack.append(node.rt)
        subgame.append(L - node.dep)
    else:
        stack.append(node.lt)
        stack.append(node.rt)

def grundy(n):
    if n == 0: return 0
    if n % 2 == 1: return 1
    if n == 2**(n.bit_length() - 1):
        return n
    return grundy(n - 2**(n.bit_length() - 1))

g = 0

for l in subgame:
    g ^= grundy(l)

print('Alice' if g != 0 else 'Bob')

Submission status: Accepted

Solution code:
from functools import cmp_to_key


def f(s, t):
    m = min(len(s), len(t))
    if s[:m] > t[:m]:
        return 1
    elif s[:m] < t[:m]:
        return -1
    else:
        if len(s) > len(t):
            return -1
        else:
            return 1


def ms(s, t):
    i = 0
    for c1, c2 in zip(s, t):
        if c1 != c2:
            return i
        i += 1
    return i


def xxor(x):
    if x & 3 == 0:
        return x
    if x & 3 == 1:
        return 1
    if x & 3 == 2:
        return x + 1
    if x & 3 == 3:
        return 0


def gray(x):
    return x ^ (x // 2)


n, l = map(int, input().split())
s = [input() for _ in range(n)]
s.sort(key=cmp_to_key(f))
g = gray(l) ^ gray(l - len(s[0]))
for i in range(n - 1):
    b = ms(s[i], s[i + 1]) + 1
    g ^= gray(l - b + 1) ^ gray(l - b)
    t = len(s[i + 1]) - b
    g ^= gray(l - b) ^ gray(l - b - t)
if g == 0:
    print('Bob')
else:
    print('Alice')

Submission status: Accepted

Solution code:
n,l = map(int,input().split())
ls = [input() for i in range(n)]
sm = sum([len(s) for s in ls])
ls.sort()
num = [0]*(sm+1)
for i in range(n):
  if i == 0:
    for j in range(len(ls[i])):
      num[j+1] = 1
  else:
    x = ls[i]
    p = ls[i-1]
    cnt = 0
    while cnt < min(len(x),len(p)):
      if x[cnt] == p[cnt]:
        cnt += 1
      else:
        break
    num[cnt+1] -= 1
    for j in range(cnt+2,len(x)+1):
      num[j] += 1
ans = 0
def d2(x):
  if x == 0:
    return 0
  cnt = 0
  while x%2 == 0:
    cnt += 1
    x //= 2
  return 2**cnt
for i in range(sm+1):
  ans ^= d2(l+1-i)*(num[i]%2)
if ans:
  print("Alice")
else:
  print("Bob")

Submission status: Accepted

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc087/tasks/arc087_c

初期状態で出ている数字を木としてあらわす
数字でふさがっている所はもう追加できない
まだおけるのは、空いている部分だけ

Lがでかいので、深さを考えていては死ぬ

そのままふさぐと、置ける場所は1減る
伸ばしておけば、Lまで増やして置ける

置ける場所の偶奇か？
置ける場所が0で来たら負け→初手が奇数なら先手勝ち・そうでないなら後手勝ち？
伸ばせる奴は偶奇反転に使える

部分で考えてみるか→

Grundy数計算
深さ1の部分木のGrundy → 1
深さ2の部分木のGrundy → 2
深さ3　　　　　　　　 → 1 ?
深さ4

Grundyで行ける = xorが全体のGrundyになるという仮定
なので、深さxを試すときは、深さxで1回で行ける状態のxorのmexがGrundyとなる

深さ1なら、問答無用で1
深さ2なら、0 or 1 になるので 2
深さ3なら, 0 or 2 になるので 1
深さ4なら, 0 or 1 or 3 or 2 なので 4
深さ5なら, 0 or 4 or 5 or 7 or 6 で 1
深さ6なら, 0 or 1 or 5 or 4 or 6 or 7 で 2
深さ7なら, 0 or 2 or 3 or 7 or 6 or 4 or 5 で 1
深さ8なら, 0 or 1 or 3 or 2 or 6 or 7 or 5 or 4 で 8

→どうやら、その数字を割り切れる最大の2の階乗数がGrundy数になるみたいだ
つまり、空きポイントを探索して、対応する深さのGrundy数を計算 & xorをとればよい

あとは実装だ
prefix treeを作りたいな？
適当にノードを追加して作ってあげればいいか
保持するデータは、0の子index,1の子index,深さがあれば十分かな
計算量がちょっと気になるところ(再帰はなるべく避けたいところ)

"""

def tp_z(now , nd):

    if z_child[now] == None:
        ret = len(z_child)
        z_child[now] = ret
        z_child.append(None)
        o_child.append(None)
        dep.append(nd + 1)
    else:
        ret = z_child[now]

    return ret

def tp_o(now , nd):

    if o_child[now] == None:
        ret = len(z_child)
        o_child[now] = ret
        z_child.append(None)
        o_child.append(None)
        dep.append(nd + 1)
    else:
        ret = o_child[now]

    return ret

def grundy(nd):

    if nd == 0:
        return 0

    for i in range(64):
        if nd % (2**i) != 0:
            return 2**(i-1)
        

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

z_child = [None]
o_child = [None]
dep = [0]

for loop in range(N):

    now = 0
    s = input()

    for i in s:
        if i == "0":
            now = tp_z(now , dep[now])
        else:
            now = tp_o(now , dep[now])

#print (z_child)
#print (o_child)
#print (dep)

ans = 0
for i in range(len(z_child)):

    if z_child[i] == None:
        ans ^= grundy(L - dep[i])
    if o_child[i] == None:
        ans ^= grundy(L - dep[i])

if ans == 0:
    print ("Bob")
else:
    print ("Alice")

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    class TreiNode:
        def __init__(self, char_num, depth):
            self.end = False
            self.child = [None] * char_num
            self.depth = depth

        def __setitem__(self, i, x):
            self.child[i] = x

        def __getitem__(self, i):
            return self.child[i]

    class Trei:
        def __init__(self, char_num):
            self.root = TreiNode(char_num, 0)
            self.char_num = char_num

        def add(self, S):
            v = self.root
            for s in S:
                if v[s] is None:
                    v[s] = TreiNode(self.char_num, v.depth + 1)
                v = v[s]
            v.end = True

        def exist(self, S):
            v = self.root
            for s in S:
                if v[s] is None:
                    return False
                v = v[s]
            if v.end:
                return True
            else:
                return False

    N, L = map(int, input().split())
    T = Trei(2)
    for _ in range(N):
        S = input().rstrip('\n')
        S = [int(s) for s in S]
        T.add(S)

    g = 0
    st = [T.root]
    while st:
        v = st.pop()
        for i in range(2):
            if v[i] is None:
                d = L - v.depth
                g ^= d & -d
            else:
                st.append(v[i])
    if g:
        print('Alice')
    else:
        print('Bob')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353
def make_trie(str_set):
    """
    :param collections.Iterable[str] str_set:
    :rtype: dict of dict
    """
    trie = {}
    for s in str_set:
        node = trie
        for c in s:
            if c not in node:
                node[c] = {}
            node = node[c]
    return trie


N, L = list(map(int, sys.stdin.buffer.readline().split()))
S = [sys.stdin.buffer.readline().decode().rstrip() for _ in range(N)]

trie = make_trie(S)


# # grundy[i]: 深さ L - i の grundy 数
# grundy = [0] * L
# grundy[0] = 1
# for i in range(1, L):
#     gs = [0]
#     for j in range(i):
#         g = 0
#         for k in range(j, i):
#             g ^= grundy[k]
#         gs.append(g)
#     g = 0
#     while g in gs:
#         g += 1
#     grundy[i] = g
# print(grundy) # lsb
# [1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 32]

# @debug
def grundy(i):
    # 深さ i の grundy 数
    # L - i の最下位ビット
    ret = 1
    while (L - i + 1) & ret == 0:
        ret <<= 1
    return ret


g = 0
stack = [(trie, 0)]
while stack:
    nodes, depth = stack.pop()
    if depth < L and len(nodes) == 1:
        g ^= grundy(depth + 1)
    for children in nodes.values():
        stack.append((children, depth + 1))

if g == 0:
    print('Bob')
else:
    print('Alice')

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

class Node:
    def __init__(self, sigma, depth):
        self.end = False
        self.child = [None] * sigma
        self.depth = depth
    def __setitem__(self, i, x):
        self.child[i] = x
    def __getitem__(self, i):
        return self.child[i]

class Trie():
    def __init__(self, sigma):
        self.sigma = sigma
        self.root = Node(sigma, 0)
    
    def add(self, S):
        vn = self.root
        for cs in S:
            if vn[cs] is None:
                vn[cs] = Node(self.sigma, vn.depth + 1)
            vn = vn[cs]
        vn.end = True

ans = 0

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

Tr = Trie(2)

for _ in range(N):
    S = list(map(int, readline().strip()))
    Tr.add(S)

cnt = 0
stack = [Tr.root]
while stack:
    vn = stack.pop()
    for i in range(2):
        if vn[i] is None:
            r = L - vn.depth
            cnt ^= -r&r
        else:
            stack.append(vn[i])

print('Alice' if cnt else 'Bob')

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

class Node:
    def __init__(self, sigma, depth):
        self.end = False
        self.child = [None] * sigma
        self.depth = depth
    def __setitem__(self, i, x):
        self.child[i] = x
    def __getitem__(self, i):
        return self.child[i]

sigma = 2
root = Node(sigma, 0)
def add_trie(S):
    vn = root
    for cs in S:
        if vn[cs] is None:
            vn[cs] = Node(sigma, vn.depth + 1)
        vn = vn[cs]
    vn.end = True

ans = 0

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

for _ in range(N):
    S = list(map(int, readline().strip()))
    add_trie(S)

cnt = 0
stack = [root]
while stack:
    vn = stack.pop()
    for i in range(2):
        if vn[i] is None:
            r = L - vn.depth
            cnt ^= -r&r
        else:
            stack.append(vn[i])

print('Alice' if cnt else 'Bob')