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"; } };