mayoko’s diary

プロコンとかいろいろ。

SRM 522 div1 easy: RowAndCoins

今日から忙しくなるので解ける問題が少なくなりそうです。

解法

ソースコードを見ればわかりますが, 実は s[0] == 'A' または s[n-1] == 'A' なら Alice が勝ち, それ以外は Bob が勝ちます。

Alice が勝つ場合は明らかでしょう。端っこにある A 以外全部取れば勝ちです。
s[0] と s[n-1] が両方とも B の場合を考えましょう。この場合, Alice がどのように行動しても, 残ったカードは区間が 2 つ以下になります。例えば,

BAAAAAAAB

という文字列を考えた場合, [0, 3] を取れば残る区間は右側の AAAAB となり, 残ったカードがなす区間は [4, 8] の一つのみです。
また, [2, 4] の区間のカードを取れば残る区間は [0, 2] の BAA, [5, 8] の AAAB になります。

上で述べたことにより, Alice がカードを取った後の A が存在する区間は 2 つ以下になります。
Alice がカードを取った後の A が存在する区間が 0 の場合は当然 Bob の勝ちです。
Alice がカードを取った後の A が存在する区間が 1 の場合は, A が存在する区間のカードの A をすべて取り除くようにカードを取れば Bob の勝ちです。
Alice がカードを取った後の A が存在する区間が 2 の場合は, まず Bob は左側の区間の左端のカード(このカードには B と書かれている)を除きすべてのカードを取り除きます。例えば

BAAAAAAAB
という文字列で Alice が最初に [2, 4] の区間のカードを取れば
BAA AAAB
となりますが, Bob は
B AAAB
となるようにカードを取ります。
後は Alice がカードを取ったら Bob は取られたカードの区間が連続するようにカードを取っていけば勝ちです。例えば Alice がこの後
B A AB
となるようにカードを取った場合, 真ん中の A を取れば
B AB
となり, 取り除かれているカードの区間が連続するようになります。こんな感じで続けると, 最後には B しか残りません。
また, Alice が左端の B を取り除いた場合は 右側の区間から右端の B だけを残すようにカードを取り除けばやはり B しか残りませんので Bob の勝ちです(例えば上の例で AAAB となったら AAA を取り除いて B にすれば良い)。

class RowAndCoins {
public:
    string getWinner(string cells) {
        int n = cells.size();
        if (cells[0] == 'A' || cells[n-1] == 'A') return "Alice";
        else return "Bob";
    }
};