torus711 のアレ

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

TopCoder SRM 612, Division 2, Level 1 : LeftAndRightHandedDiv2

問題概要

 人が横一列に並んでいる。人は右利きか左利きのいずれかであり、左から i 番目の人は、文字列 S の i 番目の文字が 'R' であれば右利き、'L' であれば左利きである。これらの人が一斉にノートをとろうとするとき、右利きの人の右側に左利きの人が座っていると肘がぶつかってしまう。そのような衝突が何箇所で発生するか求めよ。

解法

 有効な i に関して、S[ i ] == 'R' && S[ i + 1 ] == 'L' を満たす i の数が答えになります。文字列長は高々 50 なので、i を全て試して条件を満たすものを数え上げることができます。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

class LeftAndRightHandedDiv2
{
public:
	int count( string S )
	{
		const int N = S.size();

		int res = 0;
		REP( i, 0, N - 1 )
		{
			res += S[i] == 'R' && S[ i + 1 ] == 'L';
		}
		return res;
	}
};