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のゲーム系問題はやたら簡単なのばっかだな