読者です 読者をやめる 読者になる 読者になる

torus711 のアレ

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

TopCoder SRM 681, Division 2, Level 1 : CoinFlipsDiv2

TopCoder

問題概要

 表裏を区別できる $N$ 枚のコインが一直線上に並んでいる.コインは左から右に $0$ から $N - 1$ で番号付けられている.コインの状態は長さ $N$ の配列 $\mathit{ state }$ で与えられる.$\mathit{ state }_i = H$ のとき,$i$ 番のコインが表を上にして置かれていて,$\mathit{ state }_i = T$ のとき,裏を上にして置かれている.
 各コインについて,異なる面を上にして置かれているコインと隣接しているとき,そのコインを interesting であるという.
 interesting なコインの枚数を求めよ.

  • $1 \leq N \leq 50$

解法

 コインが interesting かどうかは隣接するコインの状態によって決まるので,各 $i$ ( $0 \leq i < N - 1$ ) について,$\mathit{ state }_i$ と $\mathit{ state }_{ i + 1 }$ に着目します.気を付けることは,$\mathit{ state }_i \neq \mathit{ state }_{ i + 1 }$ なる $i$ の数と答えは一般には直接対応しないということです.例えば "HTHTT" と "HTTHT" はどちらも隣接する 2 コインが異なる箇所の数は同じ $3$ 箇所ですが,答えはそれぞれ $4$ と $5$ です.
 あるコインについて,両側ともそれとは異なる状態であるときに,着目コインを二回数えないようにする必要があります.答えは,$\mathit{ state }_i \neq \mathit{ state }_{ i + 1 }$ なる $i$ について $i$ と $i + 1$ を列挙した後,重複を除いて数え上げた個数と言えます.長さ $N$ の配列を用意しておいて,数えるべきところに 1 を代入してから総和をとればよいです.
 この解法は,$\mathit{ state }$ を一回走査しつつ各要素に関して定数時間の処理をしてから,長さ $N$ の配列を一回走査することになります.どちらの処理も $O( N )$ 時間で完了するので,全体でも $O( N )$ 時間となります.

コード

template < typename T = int > using VT = vector< T >;

#define REP2( i, n ) REP3( i, 0, n )
#define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define GET_REP( a, b, c, F, ... ) F
#define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ )
#define ALL( c ) begin( c ), end( c )

#define SZ( v ) ( (int)( v ).size() )

class CoinFlipsDiv2
{
public:
	int countCoins( string state )
	{
		const int L = SZ( state );

		VT< bool > is_interesting( L );
		REP( i, L - 1 )
		{
			if ( state[i] != state[ i + 1 ] )
			{
				is_interesting[i] = is_interesting[ i + 1 ] = true;
			}
		}
		return count( ALL( is_interesting ), true );
	}
};