TopCoder SRM 606, Division 1, Level 2 : EllysPairing

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=11036&rd=15839

問題概要

　いくつか（ ≦ 50,000,000 ）の数が与えられる。この数の内、値が異なるものを二つ選んで取り除く操作を複数回できる。最大で何回取り除くことができるか、求めよ。なお、Memory Limit は 16 MB である。

解法

　要素の数がそれなりに多い上に ML が厳しいので要素を列挙して云々、のようなことはできません。パパっと最適な戦略をシミュレートできるか考える必要があります。とりあえず思い付くのは、要素数が多い値から二つを選んでペアにする操作を繰り返す方法です。この方法であれば一手ずつシミュレートする必要はありません。過半数を占める要素が存在しない場合、この方法で全て（要素数が奇数ならば一つ余る）の数をペアとして取り出すことができます。過半数を占める値が存在するとき、明らかにその値が余るので、それ以外の値を全て使い切るまで過半数を占める値とペアにして取り出すことで、( 全体数 - 最大の要素数 ) だけ取り出すことができます。
　以上のロジックを実装するためには、過半数を占める要素が存在するか（するとすればそれは何個か）を高速かつ省メモリで求められる必要があります。これは Boyer-Moore Majority Vote Algorithm により線形時間でできます。全体の要素数は count の総和をとれば求まるので、これで上記のロジックを実装することができます。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()

class EllysPairing
{
public:
	int getMax( int M, vector <int> count, vector <int> first, vector <int> mult, vector <int> add )
	{
		const int N = count.size();

		unsigned major = -1, cnt = 0;
		REP( i, 0, N )
		{
			unsigned cur = first[i];
			REP( j, 0, count[i] )
			{
				if ( major == cur )
				{
					cnt++;
				}
				else
				{
					if ( cnt == 0 )
					{
						major = cur;
						cnt++;
					}
					else
					{
						cnt--;
					}
				}

				cur = cur * mult[i] + add[i];
				cur &= M - 1;
			}
		}

		int nummajor = 0;
		REP( i, 0, N )
		{
			unsigned cur = first[i];
			REP( j, 0, count[i] )
			{
				nummajor += cur == major;

				cur = cur * mult[i] + add[i];
				cur &= M - 1;
			}
		}

		const int whole = accumulate( ALL( count ), 0 );
		return whole / 2 < nummajor ? whole - nummajor : whole / 2;
	}
};