問題一覧 > 通常問題

No.3342 AAB Game

レベル : / AI推定難易度 : 1675 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 28
作問者 : hir355 / テスター : Nzt3 jupiter_68 noya2
お気に入りにしたユーザー ProblemId : 4412 / 自分の提出
問題文最終更新日: 2025-11-11 08:15:58
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 作問ハッカソンコンテスト 003 Day1 (順位表) の他の問題:

Problem Statement

A string consisting of $0$ or more As followed by $1$ B, in this order, is called an AAB string.

For example, AAB and B are AAB strings. AABB and A are not AAB strings.

You are given a string $S$ of length $N$ consisting of A and B. Let $S[i,j]$ denote the substring of $S$ from the $i$-th character through the $j$-th character.

Alice and Bob play the following game using this string.
  • Starting with Alice, the two players take turns alternately.
  • On each turn, the player chooses $i,j \ (1 \leq i \leq j \leq N)$ such that $S[i,j]$ is an AAB string, and for each character in $S[i,j]$, replaces it with B if it is A, and with A if it is B.
The player who can no longer perform an operation loses, and the player who did not lose wins.
It can be proved that this game always ends in a finite number of turns. Determine which player wins when both players play optimally.

Constraints

  • $1 \leq N \leq 2 \times 10^5$
  • $S$ is a string of length $N$ consisting of A and B
  • $N$ is an integer

Input

The input is given from standard input in the following format.

$N$
$S$

Output

Print Alice if Alice wins when both players play optimally, and Bob if Bob wins.

Sample

Sample 1
Input
2
AB
Output
Alice

On the first turn, Alice can change $S$ to BA or AA.

Sample 2
Input
3
ABB
Output
Bob

Sample 3
Input
5
BABAB
Output
Bob

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。