AT_agc063_a [AGC063A] Mex Game

给定一个由 `A` 和 `B` 组成、长度为 $N+1$ 的字符串 $S = S_0 S_1 \cdots S_N$。对于每个 $k=1,2,\ldots,N$，请解决以下问题： > Alice 和 Bob 使用集合 $X$ 进行游戏。$X$ 初始为空集，接下来按照 $t=1,2,\ldots,k$ 的顺序进行如下操作： > > - 当 $t$ 为奇数时，Alice 选择一个非负整数 $x$，并将 $X$ 替换为 $X \cup \{x\}$。 > - 当 $t$ 为偶数时，Bob 选择一个非负整数 $x$，并将 $X$ 替换为 $X \cup \{x\}$。 > > 当 $k$ 次操作全部结束后，记 $x = \mathrm{mex}(X)$，如果 $S_x$ 是 `A`，则 Alice 获胜；如果 $S_x$ 是 `B`，则 Bob 获胜。注意，由于 $X$ 的元素个数不超过 $k$，所以 $x = \mathrm{mex}(X) \leq k$ 恒成立（因此 $S_x$ 一定存在）。 > > 请输出在双方都采取最优策略的情况下，最终的胜者名字。 $\mathrm{mex}(X)$ 是什么？对于一个由非负整数组成的有限集合 $X$，$\mathrm{mex}(X)$ 定义为不属于 $X$ 的最小非负整数 $x$。

输入通过标准输入给出，格式如下： > $N$ $S$

输出 $N$ 行。第 $i$ 行输出当 $k=i$ 时，双方都采取最优策略时的胜者名字（`Alice` 或 `Bob`）。

### 限制条件 - $1 \leq N \leq 2 \times 10^5$ - $S$ 是由 `A` 和 `B` 组成的长度为 $N+1$ 的字符串。 ### 样例解释 1 以下是 $k=1$ 时游戏的一个进行示例： - Alice 选择 $x=10$。 - $\mathrm{mex}(X) = \mathrm{mex}(\{10\}) = 0$，$S_0$ 是 `A`，所以 Alice 获胜。 以下是 $k=2$ 时游戏的一个进行示例： - Alice 选择 $x=2$。 - Bob 选择 $x=0$。 - $\mathrm{mex}(X) = \mathrm{mex}(\{0,2\}) = 1$，$S_1$ 是 `B`，所以 Bob 获胜。 由 ChatGPT 4.1 翻译