TopCoder, SRM 624, Division 1, Level 1 : BuildingHeights

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13211&rd=15857

問題概要

　Division 2, Level 2 と設定は同じ。ただしこちらは 1 以上 N 以下の全ての M について答えを求めて、全ての xor を return せよ。
　

解法

　|heights| を N と書きます。
　基本的には、Division 2, Level 2 と同様に、heights をソートすると操作対象が連続する区間内に入ることを利用します。ただし、全く同一にやると M のとり方が O( N ) 個で、クエリ毎に N に関する二重ループが回るので、全体で になってしまいます。
　ある M に対する解をより高速に計算する方法を考えます。ある長さ M の区間を等しくするコストが分かっているとき、端点を同じ方向に一つずつずらした区間内を等しくするコストを知りたいとします。このとき、区間内の値で前と変わるのは片方の端点が消えて、反対側に新しい値が入ってくるだけです。変更点が少ないので、全部を一から計算しなうくても何とかなりそう、ということでそのような方法を考えます。
　区間を右に（大きい方に）動かしていくと考えます。動かす前の区間内の最大値を t 、動かした後の最大値を t' と置きます。つまり、動かす前の区間を全て t にしたコストが分かっていて、その状態から区間を一つ右に動かしたとき、区間内を全て t' にするコストを高速に計算することを試みます。まず、区間の左端の要素が区間の外に出るため、その値を l とすれば、t - l のコストが無かったことになります。次に、区間の右端に値が入ってきますが、これは t' に等しいので変更する必要はりません。この時点で、区間で右端以外の M - 1 個の値を t にするコストが分かっています。ということは、M - 1 個の値を t から t' に変更するコスト ( M - 1 ) * ( t' - t ) を新たに加えれば、移動後の区間内を等しくするコストが求まります。後は、可能な区間を全て試すまで区間をスライドさせていけば、一つの M に対する答えを計算できます。この方法ならば、左端の区間に対する解の計算に O( M ) 時間、区間のとり方が O( N ) 、区間の更新は O( 1 ) になるので、クエリあたり O( N ) 時間程度で答えを計算できます。
　後は、全ての M について答えを計算して XOR を計算すれば、問題を解くことができます。

コード

using VI = vector<int>;

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

class BuildingHeights
{
public:
	int minimum( vector <int> heights )
	{
		const int N = heights.size();
		
		sort( ALL( heights ) );

		VI res( N );
		REP( i, 0, N )
		{
			res[i] = solve( heights, i + 1 );
		}
		return accumulate( ALL( res ), 0, []( const int a, const int b ){ return a ^ b; } );
	}

	int solve( const VI &heights, const int M )
	{
		const int N = heights.size();

		int cur = 0;
		REP( i, 0, M )
		{
			cur += heights[ M - 1 ] - heights[i];
		}
		int tallest = heights[ M - 1 ];

		int res = cur;
		REP( i, 0, N - M )
		{
			cur -= tallest - heights[i];
			tallest = heights[ M + i ];
			cur += ( tallest - heights[ M + i - 1 ] ) * ( M - 1 );
			tallest = heights[ M + i ];

			res = min( res, cur );
		}

		return res;
	}
};