TopCoder, Single Round Match 649, Division 2, Level 3 : XorSequenceEasy

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13657&rd=16313

問題概要

　Division 1, Level 2 とほぼ同一．
　 が直接与えられ， である点が異なる．

解法

　Division 1, Level 2 の制約を小さくした問題で，当然同じ解法で解くことができます．解くために必要なアイデアは Division 1, Level 2 と同一で， の（ 2　進表記での）各桁の値を上から決定していき，大小関係が確定したものを別のグループへと分割していきます．詳しくは Division 1, Level 2 の記事をご覧ください．
　制約lが小さいことを利用して簡略化できる点として，ある桁を決定したときに転倒しない要素のペアを数える部分があります．こちらの制約だと，インデックスの対を全て試して愚直に数えることができます．

コード

using VI = vector< int >;
using VVI = vector< vector< int > >;

#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 FOR( e, c ) for ( auto &e : c )
#define ALL( c ) ( c ).begin(), ( c ).end()

#define SZ( v ) ( (int)( v ).size() )
#define PB push_back
#define BI back_inserter

class XorSequenceEasy
{
public:
	int getmax( vector <int> A, int N )
	{
		int res = 0;
		VVI cur( 1, A ), next;
		for ( ; N; N >>= 1 )
		{
			int id = 0, rev = 0;
			FOR( ary, cur )
			{
				VI a, b;
				transform( ALL( ary ), BI( a ), [=]( const int tmp ){ return !!( tmp & N ); } );
				transform( ALL( a ), BI( b ), bind( minus< int >(), 1, _1 ) );
				
				id += notinv( a );
				rev += notinv( b );
			}
			res += max( id, rev );

			FOR( ary, cur )
			{
				VI zeros, ones;
				FOR( a, ary )
				{
					( a & N ? ones : zeros ).PB( a );
				}

				next.PB( zeros );
				next.PB( ones );
			}
			next.erase( remove_if( ALL( next ), bind( &VI::empty, _1 ) ), next.end() );
			swap( cur, next );
			next.clear();
		}

		return res;
	}

	int notinv( const VI &as )
	{
		const int N = SZ( as );

		int res = 0;
		REP( i, N )
		{
			REP( j, i + 1, N )
			{
				res += as[i] < as[j];
			}
		}
		return res;
	}
};