TopCoder, SRM 636, Division 2, Level 1 : GameOfStones

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13480&rd=16079

問題概要

　石がいくつかの山に分けて積まれている。山に関する情報は数列 によって与えられ、 番目の山に積まれている石の数は である。
　一つの山から別の山へ、2 つの石を動かす操作ができる。このとき、ある山にある石を全て取り除くことはできない。
　全ての山にある石の数を同じにするために必要な操作回数の最小値を求めよ。達成不可能な場合は -1 で示せ。

解法

　山の総数を と書きます。
　石は必ず 2 個ずつ動かすので、それぞれの山について、石の総数の奇偶が変わることはありません。従って、操作前の状態で全ての山について奇偶が一致していない場合は、目標を達成することができないので -1 を return しておきます。
　次に、奇偶性が一致しているという条件下でのことについて考えます。石は必ず 2 個セットで動かされ、また山には必ず 1 個以上の石が残っていなければならないので、 を 2 で整数除算しておくことで、石を 2 個セットで動かしているのと同じことになります。
　さて、全ての山にある石の数を等しくしたとき、それぞれの山にある石の数と、山ごとの石の数の平均値は等しくなっているはずです。平均は石の総数を で除することによって与えられ、石の移動が起こっても不変なので、平均値が整数ではないとき達成不可能であることが分かります。そうでないならば適当な操作によって目標を達成できます。
　目標を達成できるとき、必要な操作回数は、各山に対して施さなければならない操作回数の和を 2 で割った値になります。これは、一回の操作で 2 つの山に作用できるためです。この値を適当な方法で計算すれば答えが求まります。

コード

#define ALL( c ) (c).begin(), (c).end()

class GameOfStones
{
public:
	int count( vector <int> stones )
	{
		const int N = stones.size();

		auto odd = bind( modulus< int >(), _1, 2 );
		if ( !( all_of( ALL( stones ), odd ) || none_of( ALL( stones ), odd ) ) )
		{
			return -1;
		}

		transform( ALL( stones ), stones.begin(), bind( divides< int >(), _1, 2 ) );
		const int sum = accumulate( ALL( stones ), 0 );
		if ( sum % N )
		{
			return -1;
		}

		const int average = sum / N;
		transform( ALL( stones ), stones.begin(), [=]( const int a ){ return abs( a - average ); } );
		return accumulate( ALL( stones ), 0 ) / 2;
	}
};