First of all, if at least one end is marked with an 'A', then Alice wins. Without loss of generality, suppose the board is of the form "A??...?"('?' means empty cells marked with 'A' or 'B' arbitrarily). Alice can obtain "ACC...C"('C' means covered by a coin) in one step and win.

Then what if the board is of the form "B??...?B"?

If Alice covered either end with a coin, again without loss of generality, the board becomes "CC...CB" or "CC...C??..?B". Bob wins immediately for the former, by covering all other empty cells except the rightmost 'B' for the latter. So Alice would have to choose "B??...?CC...C??...?B" if she wanted to win.

Now let's consider a simpler situation, "B??...?CC...CB".

**(I)**If it is now Bob's turn, he only needs to cover all the empty cells on the left and wins.

**(II)**If it is now Alice's turn, she has up to four choices. If she choose to cover the rightmost 'B' or either end of the empty cells on the left, Bob can obviously win. Then again she has to choose to make the board of the form "B??...?CC...C??...?CC...CB". If Bob covers all empty cells of the second interval, then we reach the same configuration except that the number of empty cells decreases. So we can prove by

**that no matter whose turn is it, the winner would be Bob if the board is of the form "B??...?CC...CB".**

*induction*So let's return to "B??...?CC...C??...?B". If the second interval is empty, the it corresponds to (I). Otherwise, Bob could cover all empty cells on the right except the rightmost 'B', and now it corresponds to (II). Either way, Bob wins.

So all we have to do is to check the two cells on both ends.

I code a bit mask DP during the contest. Finding patterns and proving them is still a hard task for me. Need more exercise.

## No comments:

## Post a Comment