問題一覧 > 通常問題

No.3258 Xor Division Game

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 20
作問者 : Iroha_3856 / テスター : lif4635 champignon tikuwa_
ProblemId : 11958 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-09-05 21:17:25

問題文

整数列の多重集合 $S$ があります。

始め、$S = \{(F_1, F_2, \ldots, F_N)\}$ です。ここで、$F$ に $0$ は含まれないことが保証されます。

$A \in S$ なる整数列 $A = (A_1, A_2, \ldots, A_K)$ について、$A$ を位置 $i\ (1 \leq i \leq K)$ で分割することを以下の操作を順番に行うことと定義します

  • $i \neq 1$ ならば、$S$ に $(A_1 \oplus A_i, A_2 \oplus A_i, \ldots, A_{i-1} \oplus A_i)$ を追加する
  • $i \neq K$ ならば、$S$ に $(A_{i+1} \oplus A_i, A_{i+2} \oplus A_i, \ldots, A_K \oplus A_i)$ を追加する
  • $S$ から $A$ を $1$ つ削除する

ただし、$\oplus$ はビットごとの排他的論理和を表します。

Alice と Bob が $S$ を使って以下のゲームを行います。

    Alice から始めて、各プレイヤーが交互に以下の操作を行う
    • 好きな $A \in S$ なる整数列 $A$ と $1 \leq i \leq |A|$ となる $i$ を選んで、 $A$ を位置 $i$ で分割する
    • ただし、操作したあとの $S$ に $0$ が含まれる数列が存在するような操作はしてはならない
操作が行えなくなった方が負け、そうでない方が勝ちです。

両者が最適に行動した時、どちらが勝つかを判定してください。

入力

$N$
$F_1\ F_2\ \ldots\ F_N$

入力は全て以下の制約を満たす

  • $1 \leq N \leq 2 \times 10^5$
  • $1 \leq F_i < 2^{30}$
  • 入力はすべて整数

出力

両者が最適に行動した時、Alice が勝つなら Alice、Bobが勝つなら Bob と出力し、 最後に改行してください。

サンプル

サンプル1
入力
6
1 2 2 1 5 7
出力
Bob

例えば、以下のような進行が考えられます:

始め、$S = \{(1, 2, 2, 1, 5, 7)\}$ です。

Aliceが数列 $A = (1, 2, 2, 1, 5, 7) \in S$ を選び、$A$ を位置 $5$ で分割します。

このあと、$S = \{(1 \oplus 5, 2 \oplus 5, 2 \oplus 5, 1 \oplus 5), (7 \oplus 5)\} = \{(4, 7, 7, 4), (2)\}$ となります。

Bobが数列 $A = (2) \in S$ を選び、$A$ を位置 $1$ で分割します。

このあと、$S = \{(4, 7, 7, 4)\}$ となります。

$0$ を発生させる操作は行えないことから、Aliceはこのとき、操作を行えなくなるので、Aliceの負け、Bobの勝ちです。

Aliceがどのように行動してもBobが適切に操作を行えばBobが勝つので、Bobと出力します。

サンプル2
入力
1
1
出力
Alice

始め、$S = \{(1)\}$ です。

Aliceが数列 $A = (1) \in S$ を選び、$A$ を位置 $1$ で分割します。

このあと、$S = \{\}$ となります。

Bobはこのあと操作は行えないので、Bobの負け、Aliceの勝ちです。

よって、Aliceと出力します。

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