解法
あるボールを消せる場合は常に消してしまった方が得になります。
筒内部におけるそれぞれの端のボールの色と、今入れようとしているボールの色によって場合分けされます。
- どちらかの端が入れようとしている色と一致する -> 一致する側に入れて消す
- 入れようとしているボールと、次のボールの色が一致する -> 好きな方に入れる(次のターンで消される)
- それ以外 -> その次のボールの色と異なる色の方の端に入れる
(実は奇偶性だけでいけます)
コード
#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) const int INF = INT_MAX / 4; int main() { cin.tie( 0 ); ios::sync_with_stdio( false ); int n; cin >> n; string str; cin >> str; string cylinder; REP( i, 0, n ) { if ( cylinder.empty() ) { cylinder += str[i]; } else if ( str[i] == cylinder[0] ) { cylinder.erase( 0, 1 ); } else if ( str[i] == cylinder.back() ) { cylinder.erase( cylinder.size() - 1, 1 ); } else { if ( i + 1 < n ) { if ( str[i] == str[ i + 1 ] || str[ i + 1 ] == cylinder[0] ) { cylinder += str[i]; } else { cylinder = string( 1, str[i] ) + cylinder; } } else { cylinder += str[i]; } } } cout << cylinder.size() << endl; return 0; }