SRM522 Div1 Easy(250), Div2 Medium(550) RowAndCoins

TopCoder

RowAndCoins

どちらかの端がAならばAliceが勝てる。

それ以外の場合はBobの勝ち。Aliceがどちらかの端を取るなら、Bobは他方の端１個を残せる。Aliceがどちらかの端を１個だけ残すならば、Bobはその１個を残せる。AliceがB…B○○○B…B、B…B○○○A…B、B…A○○○B……Bの形にすれば、BobはB…Bを残すことで、数学帰納法的にBobが勝てる。B…A○○○A…Bの形ならば、B…A○○○Bの形にして返せばよい。Aliceの手によらずB…A○○○Bもしくは、B…B○○Bの形にはできて、いつかは勝てる。

#include <string>
using namespace std;

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