TopCoder, Single Round Match 647, Division 2, Level 1 : PeacefulLine

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13632&rd=16279

問題概要

　何人かの生徒を直線状に並べたい．生徒を並べたとき，隣り合う生徒の年齢が同じ場合，お喋りを初めてしまって迷惑になることが知られている．
　今，並べたい生徒たちの年齢に関する情報が，配列 により与えられる． は 番の生徒の年齢を表す．
　隣り合う生徒のペア全てについて，2 人の年齢が異なるような並べ方は存在するか？

解法

　 と書きます．また，問題設定からは離れて，列の並べ替えであって，隣り合う要素が全て相異なるようなものを探す問題として書きます．
　そのような並べ替えを考えたとき，ボトルネックになりそうなのは列に多く含まれる値だろうという予想が付きます．そこで， に最も多く含まれる要素に着目して，そのような要素の数を と置きます．最も多く含まれる値の配置はいくつか考えられますが，同じ長さの列に対してできるだけ多く詰め込んでしまいたいので，1 個おきに（奇数番目のみ or 偶数番目のみ）配置していく方がよさそうです． が奇数のとき，偶数番目の要素は奇数番目のそれより数が少ないので，最も多く含まれる値は，奇数番目に配置するのが最適です．そう考えると，奇数番目の要素の数が 以上ならば条件を満たす並べ替えが存在することになります．すなわち， または辺々 2 倍して ならば可能です．

コード

using VI = vector< int >;

#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) ( c ).begin(), ( c ).end()

#define SZ( v ) ( (int)( v ).size() )

class PeacefulLine
{
public:
	string makeLine( vector <int> x )
	{
		VI counts( 25 );
		FOR( a, x )
		{
			++counts[ a - 1 ];
		}
		const int m = *max_element( ALL( counts ) );
		return m * 2 <= SZ( x ) + 1 ? "possible" : "impossible";
	}
};