考察に時間をかけすぎた
問題概要
文字 'A' と 'B' のみからなる長さ の文字列
が与えられる (先頭の文字を 0 文字目とする)。各
について、次の問に答えよ。
Alice と Bob が交互に、以下の操作を合計 回行う。Alice が先手である。なお、最初は集合
は空集合であるとする。
「好きな非負整数 を選び、集合
を
に置き換える」
回の操作が終了した状態で
として、
= 'A' ならば Alice の勝ち、
= 'B' ならば Bob の勝ちとする。
双方最善を尽くした場合に、どちらが勝つかを求めよ。
制約
考えたこと
最初に思ったことは、最後の手を打てる方がかなり有利だということ。というのも、その場にとどまるか、前へ進ませるかを選べるからだ。
しかし、ラストターンの直前の mex が m だったとして、m + 1, m + 2 などを仕込んでおくことで、ラストターンの人が m を入れたとしても、入れなかったとしても、ラストターンでない人が勝てる場合もあることに気がついた。
そして単純に、
- Alice は、毎ターン、
= 'B' であるような
を集合
に入れていくのがいい
- Bob は、毎ターン、
ということがわかった。どんな順番で を入れていくのがいいのか、最初はよくわからなかったけど、結局添字が小さい方から
に入れていけばよいとなった。
あとはシミュレーションしていけば OK
