Codeforces #215, Division 1, A ( Division 2, C ) : Sereja and Algorithm

問題文

http://codeforces.com/contest/367/problem/A

概要

文字列を入力として受け取る、次のようなアルゴリズムがある。

1. 入力文字列の長さ 3 の部分文字列であって、"zyx", "xzy", "yxz" のいずれにも一致しないものを探す。存在しない場合は終了する
2. 1. で見つけた部分文字列をランダムに並び替える

文字列 s と m 個のクエリ ( l, r ) が与えられる。
各クエリについて、s の位置 l から 位置 r までの部分文字列を上記アルゴリズムの入力として与えたとき、停止するかどうかを判定せよ。

解法

アルゴリズムが停止するのは、入力された文字列の全体が、"zyx" を無限に連結したものの部分文字列になったときです。
どのような変形を施してもそのような文字列を作れないとき、アルゴリズムは停止しません。
変形自体の自由度はかなり高く、目標状態になっていない部分の文字を任意の場所にもっていくことができます。
従って、各文字の数さえ合っていれば目標を達成できます。

目標となる文字列は "zyx" の連結なので、左端の文字を 'z', 'y', 'x' の三通り試して、数が合うものがあればよいということになります。
正しい文字数は長さを 3 で除したものと、3 の剰余を使うと計算できます。
また、文字列中に各文字がいくつ含まれているかはいもす法により O( 1 ) で数えられます。

コード

typedef vector<int> VI;
typedef vector<VI> VVI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )
#define ALL( c ) (c).begin(), (c).end()
#define DRANGE( c, p ) (c).begin(), (c).begin() + p, (c).end()

#define fst first
#define snd second

string zyx = "zyx";

struct Solver
{
	const string s;
	const int L;
	
	VVI csums;

	Solver( const string &s ) : s( s ), L( s.size() ), csums( 3, VI( 1, 0 ) )
	{
		VVI counts( 3, VI( L, 0 ) );
		REP( i, 0, L )
		{
			counts[ s[i] - 'x' ][i]++;
		}

		REP( i, 0, 3 )
		{
			partial_sum( ALL( counts[i] ), back_inserter( csums[i] ) );
		}

		return;
	}

	bool solve( const int l, const int r )
	{
		const int n = r - l;
		if ( n < 3 )
		{
			return true;
		}

		REP( iteration, 0, 3 )
		{
			map<char,int> nums;
			REP( i, 0, 3 )
			{
				nums[ zyx[i] ] = n / 3 + ( i < n % 3 );
			}

			bool ok = true;
			FOR( p, nums )
			{
				ok &= csums[ p.fst - 'x' ][r] - csums[ p.fst - 'x' ][l] == p.snd;
			}
			if ( ok )
			{
				return true;
			}

			rotate( DRANGE( zyx, 1 ) );
		}

		return false;
	}
};

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	string s;
	cin >> s;

	Solver solver( s );
	
	int m;
	cin >> m;
	REP( i, 0, m )
	{
		int l, r;
		cin >> l >> r;
		cout << ( solver.solve( l - 1, r ) ? "YES" : "NO" ) << endl;
	}

	return 0;
}