問題概要
表裏を区別できる $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 ); } };
