[ARC087E] Prefix-free Game
题意翻译
对于两个字符串 $s, t$ , 如果 $s$ 不是 $t$ 的前缀且 $t$ 不是 $s$ 的前缀,则称他们是 prefix-free 的。
给定一个正整数 $L$,如果一个字符串集合 $S$ 符合下列条件,则我们称他为 good string set:
- $S$ 中的每个字符串的长度都在 $1$ 和 $L$ 之间(包括),并且之包含字符 $'0'$ 和 $'1'$
- $S$ 中的每两个的字符串都是 prefix-free 的
我们有一个 good string set $S = {s_1, s_2 ... , s_n}$,Alice 和 Bob 在玩一个游戏,他们轮流做下列操作:
- 向 $S$ 中添加一个新字符串,并使 $S$ 仍是 good string set
无法进行这个操作的人输掉游戏。假设二人都按最优策略进行游戏,求谁会赢。
## 数据范围
$1 \leq N \leq 10^5$
$1 \leq L \leq 10^{18}$
$s_1, s_2, ..., s_n$ 是不同的
${s_1, s_2, ..., s_n}$ 是 good string set
$|s_1| + |s_2| + ... + |s_n| \leq 10^5$
翻译者:魔塔哈奇
题目描述
[problemUrl]: https://atcoder.jp/contests/arc087/tasks/arc087_c
文字列 $ s $, $ t $ について、$ s $ が $ t $ の prefix でなく、$ t $ が $ s $ の prefix でないとき、$ s $, $ t $ は prefix-free であると言います。
$ L $ を正の整数とします。 文字列集合 $ S $ が **良い文字列集合** であるとは、次の条件が成り立つことです。
- $ S $ の各文字列は、長さ $ 1 $ 以上 $ L $ 以下であり、文字 `0`, `1` のみからなる。
- $ S $ の相異なる $ 2 $ つの文字列のペアはいずれも prefix-free である。
良い文字列集合 $ S\ =\ \{\ s_1,\ s_2,\ ...,\ s_N\ \} $ があります。 Alice と Bob が次のゲームで勝負します。 二人は交互に次の操作を行います。 Alice が先手です。
- $ S $ に新しい文字列をひとつ追加する。 ただし、追加後の $ S $ は良い文字列集合のままでなければならない。
先に操作を行えなくなった方が負けです。 二人が最適に行動するとき、どちらが勝つか判定してください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ L $ $ s_1 $ $ s_2 $ $ : $ $ s_N $
输出格式
Alice が勝つならば `Alice` を、Bob が勝つならば `Bob` を出力せよ。
输入输出样例
输入样例 #1
2 2
00
01
输出样例 #1
Alice
输入样例 #2
2 2
00
11
输出样例 #2
Bob
输入样例 #3
3 3
0
10
110
输出样例 #3
Alice
输入样例 #4
2 1
0
1
输出样例 #4
Bob
输入样例 #5
1 2
11
输出样例 #5
Alice
输入样例 #6
2 3
101
11
输出样例 #6
Bob
说明
### 制約
- $ 1\ \leq\ N\ \leq\ 10^5 $
- $ 1\ \leq\ L\ \leq\ 10^{18} $
- $ s_1 $, $ s_2 $, ..., $ s_N $ はすべて相異なる。
- $ \{\ s_1,\ s_2,\ ...,\ s_N\ \} $ は良い文字列集合である。
- $ |s_1|\ +\ |s_2|\ +\ ...\ +\ |s_N|\ \leq\ 10^5 $
### Sample Explanation 1
Alice が `1` を追加すると、Bob は新たに文字列を追加できなくなります。
### Sample Explanation 2
初手で Alice が追加できる文字列は `01`, `10` の $ 2 $ 通りです。 初手で Alice が `01` を追加した場合は、Bob が `10` を追加すると、Alice は新たに文字列を追加できなくなります。 初手で Alice が `10` を追加した場合も、Bob が `01` を追加すると、Alice は新たに文字列を追加できなくなります。
### Sample Explanation 3
Alice が `111` を追加すると、Bob は新たに文字列を追加できなくなります。
### Sample Explanation 4
初手で Alice は新たに文字列を追加できません。