torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

TopCoder, Single Round Match 666, Division 2, Level 2 : GoodString

問題概要

 文字列に対して,以下の操作を考える

  • 文字列のどこか(先頭,末尾も許容)に,文字列 "ab" を挿入する

 空文字列から始めてこの操作を複数回適用することで,文字列 $S$ を作ることができるか?

  • $1 \leq |S| \leq 50$
  • $S_i \in \{ \mathrm{ `a', `b' } \}$

解法

 構成された文字列に於いて,同時に挿入された 'a', 'b' の組について考えてみると,'a', 'b' の位置関係(前後)は変わらず,間に 0 文字以上が挿入されている状態になっていることが分かります.空文字列から構成可能な文字列を valid な文字列と呼ぶことにすると,この間に入っている文字列もまた valid です(間の部分には始め空文字列があって,そこに操作を加えていると考える).また,先頭や末尾に挿入することは,valid な文字列を連結していると考えられます.ここから valid な文字列の条件を考えてみると,

  • 空文字列は valid
  • 文字列 $x$ が valid なとき,$\mathrm{ ``a'' } + x + \mathrm{ ``b''}$ は valid
  • 文字列 $x, y$ が valid なとき,$x + y$ は valid

となります.これは,'a' を '(' に,'b' を ')' に置き換えて考えると「括弧がバランスしていること」の定義そのものです.従って,同じアルゴリズムで解くことができます.
 括弧がバランスしていることのチェックは,文字列を先頭から舐めながら

  • '(' がきたら深さを +1
  • ')' がきたら深さを -1

として,深さ 0 から始めて途中で負にならず,終了時 0 ならばバランスしていることが分かります(スタックを用いる方法と同じことです).
 このアルゴリズムは,文字列を走査して文字ごとに定数時間の処理をしているので $O( |S| )$ 時間で実行できます.

コード

#define FOR( e, c ) for ( auto &e : c )

const char *MSG[] = { "Bad", "Good" };

class GoodString
{
public:
	string isGood( string s )
	{
		int depth = 0;
		FOR( c, s )
		{
			if ( c == 'a' )
			{
				++depth;
			}
			else
			{
				--depth;
			}

			if ( depth < 0 )
			{
				return *MSG;
			}
		}
		return MSG[ depth == 0 ];
	}
};