SRM534 Div1 Easy - EllysCheckers

問題

n個のマスがあり、いくつかのマスにチェッカーが置かれてある
各チェッカーに対しては
・1マス右に動かす (右のマスにチェッカーが置かれていない場合のみ)
・3マス右に動かす (右2マスにチェッカーが置かれていてかつ3マス先にはチェッカーが置かれていない場合のみ)
という操作ができ、一番右のマスに止まったチェッカーは消える
2人が交互に任意のチェッカーを動かし、先に動かせなくなった方が負け
2人とも最善を尽くすときどちらが勝つか判定せよ

1 <= n <= 20

解法

どちらの操作もチェッカーの移動距離は奇数だから、操作の組み合わせによってゲーム終了までのターン数の偶奇が変わることはない
∴ 初期状態の各チェッカーと右端のマスの距離の総和の偶奇で勝者が定まる

class EllysCheckers {
public:
	string getWinner(string s) {
		int n = s.size(), a = 0;
		rep(i,n-1) if (s[i]=='o') a += n-i-1;
		return (a%2 ? "YES" : "NO");
	}
};

div1easyのゲーム系問題はやたら簡単なのばっかだな