TopCoder SRM 581, Division 2, Level 1 : BlackAndWhiteSolitaire

概要

片面が黒、他方が白に塗られたカードが N 枚ある。
今、この N 枚のカードが一列に並べられており、それぞれのカードの向きが与えられる。
いずれかのカードを選んで裏返す操作を繰り返し適用し、隣り合うどのカードも異なる色になるようにしたい。
裏返すカードの最小数を求めよ。

解法

まず、同じカードを複数回裏返す操作に意味はありません。
また、最終的な状態は、"BWBWBW..." か "WBWBWB..." のどちらかです。
従って、初期状態をこれら二つの状態に変える手数の内、小さい方が答えです。
初期状態から仮定された最終状態を作る手数は、二つのパターンで一致しない文字の数です。

コード

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

class BlackAndWhiteSolitaire
{
public:
	int minimumTurns( string cardFront )
	{
		string pat1 = "BW", pat2 = "WB";
		int res1 = 0, res2 = 0;

		REP( i, 0, cardFront.size() )
		{
			res1 += pat1[ i % 2 ] != cardFront[i];
			res2 += pat2[ i % 2 ] != cardFront[i];
		}

		return min( res1, res2 );
	}
};