torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder SRM 574, Division 1, Level 1 : TheNumberGame

概要

数字を使ったゲームをする。
最初、各プレイヤーはそれぞれ一つの数字を持っている。
ゲームはターン制で進み、各ターンでは自分の数字に対して次のいずれかの変換を行える。

  • 数字を反転する
  • 10で割る(余り切り捨て)

いずれかの移動が終わったときに両者の数字が一致すれば先攻の勝ちである。
1000 回(先攻 500、後攻 500 )以内に先攻が勝つかどうか判定せよ

解法

先攻の数字かそれを逆順にしたものに、後攻の数字が部分文字列として含まれていれば先攻が勝ちます。

コード

typedef ostringstream OSS;

#define ALL( c ) (c).begin(), (c).end()

class TheNumberGame
{
public:
	string determineOutcome( int A, int B )
	{
		OSS oss_a, oss_b;
		oss_a << A;
		oss_b << B;
		string a = oss_a.str(), b = oss_b.str(), rev;
		reverse_copy( ALL( a ), back_inserter( rev ) );
		return match( a, b ) || match( rev, b ) ? "Manao wins" : "Manao loses";
	}

	bool match( const string &a, const string &b )
	{
		return a.find( b ) != string::npos;
	}
};