SRM574 Div1 Easy - TheNumberGame

問題

先手が数字a、後手がbを持っており、どちらも0の桁はない
各ターンで各プレイヤーは自分の数字を反転するか最後の桁を消すかを選ぶ
途中で両者の数字が一致したら先手の勝ちで、いつまでも一致しない場合は後手の勝ちになる
両者が最善を尽くすときどちらが勝つか判定せよ

1 <= a, b < 10^9

解法

aか反転したaの連続する部分列にbが存在すれば先手が勝ち、そうでなければ後手の勝ち
前者のときはaの両端を削ってbに近付ければいつかは必ず一致する
(bが逃げるには数字を削るしかなく、最終的に数字が空になって一致する)
後者のときは後手は毎ターン数字を反転させてればいい

class TheNumberGame {
public:
	string determineOutcome(int a, int b) {
		string x = to_string(a), y = to_string(b);
		int n = x.size(), m = y.size();
		if (n<m) return "Manao loses";
		rep(i,n-m+1) if (x.substr(i,m)==y) return "Manao wins";
		reverse(all(x));
		rep(i,n-m+1) if (x.substr(i,m)==y) return "Manao wins";
		return "Manao loses";
	}
};

https://community.topcoder.com/stat?c=problem_statement&pm=12474&rd=15494