SRM522 Div1 Easy - RowAndCoins

問題

各マスにAかBと書かれた1列のボードがある
AliceとBobが順番に「まだコインが置かれていない任意の連続する区間にコインを置く」という操作を繰り返す
ただしこの操作で全マスをコインで埋めてはいけない
コインが置かれていないマスが1マスだけ残った状態でゲーム終了
その残ったマスにAと書かれていればAliceの勝ち、BならBobの勝ち
二人とも自分が勝つために最善の動きをするときどちらが勝つか判定

解法

ボードの両端のマスの少なくとも一方がAなら、初手でそれ以外のマスを全て埋めることでAliceが勝つ
そうじゃない(∴ 両端ともBの)場合は↓によりBobが勝つ

Aliceがどちらかの端を含む区間を選ぶと、返しのターンでもう片方の端以外を埋められて負ける
端を含まない区間を選んだ場合、例えば
　BAAA○○○AAB (○:Aliceがコインを置いたマス)
とすると、返しのターンに
　B●●●○○○AAB
　BAAA○○○●●B
このどちらかに変えられ、その後も同様にして2つの区間しか存在しないような状態を強制させられ、最終的には両端の2マスだけが残る

class RowAndCoins {
	public:
		string getWinner(string s) {
			return (s[0]=='A' || s[s.size()-1]=='A' ? "Alice" : "Bob");
		}
};