torus711 のアレ

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

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

問題概要

 Division 1, Level 2 とほぼ同一.
 A が直接与えられ,|A| \leq 50 である点が異なる.

解法

 Division 1, Level 2 の制約を小さくした問題で,当然同じ解法で解くことができます.解くために必要なアイデアは Division 1, Level 2 と同一で,B の( 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;
	}
};