TopCoder SRM 589, Division 2, Level 2 : GearsDiv2

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12732&rd=15701

概要

歯車が円状に並んでいて、隣り合う歯車は噛み合っている。
噛み合っている歯車同士は違う方向にしか回転できない。
また、必要があれば歯車を取り外して空きにすることができる。
（取り外した歯車の両隣の歯車は噛み合わない）

各歯車について、どちら向きに回したいかの情報が与えられる。
そのように歯車を回せるようにするためには、最小でいくつの歯車を取り除く必要があるか求めよ。

解法

少なくとも一つの歯車は回すことができます。
その「一つ」を仮定すると、次のようして回す（取り除かない）歯車を決めていくことができます。

• 隣の歯車の回転方向が逆の場合、次の歯車も回せる
• そうでないとき、次の歯車を回すことができないので一つ飛ばす（撤去する）

必ず回す一つを全探索して、内側で上記のような方法でそのときの最適解を求めると解けます。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define DRANGE( c, p ) (c).begin(), (c).begin() + p, (c).end()

class GearsDiv2
{
public:
	int getmin( string Directions )
	{
		const int N = Directions.size();

		int res = INT_MAX;

		REP( iteration, 0, N )
		{
			rotate( DRANGE( Directions, 1 ) );

			int cnt = 0;
			char prev = Directions[0];
			REP( i, 1, N )
			{
				if ( prev == Directions[i] )
				{					
					prev = i + 1 < N ? Directions[ i + 1 ] : ' ';
					cnt ++;
					i ++;
				}
				else
				{
					prev = prev == 'L' ? 'R' : 'L';
				}
			}

			res = min( res, cnt + ( prev == Directions[0] ));
		}

		return res;
	}
}