TopCoder, SRM 638, Division 2, Level 2 : NarrowPassage2Easy

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13520&rd=16081

問題概要

　狭い通路に、何匹かの狼がいる。 番目の狼の大きさは である。
　通路はとても狭いので、いくつかの狼のペアは互いにすれ違うことができない。 番の狼と 番の狼がすれ違うことが可能なのは、 を満たす場合に限られる。
　狼たちが上記制約を満たす限りに於いて自由に移動できるとき、狼たちの並び順（順列）として有り得るものの数を求めよ。
　

解法

　 と書きます。
　狼の数が少ないので、狼の順列を全て生成することができます。各順列についてその妥当性を判定できれば、そのような順列の数を愚直に数え上げることで問題を解くことができます。
　ある順列が妥当でない場合というのは、二匹の狼の相対位置が逆転しているペアであって、かつ二匹の大きさの和が を超えるようなものが存在するときです。従って、順列一つあたり かけて二匹の組み合わせを全て試すことで、妥当性を判定できます。
　順列の数は なので、全体では で問題を解けます。

コード

using VI = vector<int>; using VVI = vector<VI>;

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

class NarrowPassage2Easy
{
public:
	int count( vector <int> size, int maxSizeSum )
	{
		const int N = size.size();

		VI indices( N );
		iota( ALL( indices ), 0 );

		int res = 0;
		do
		{
			bool ok = true;
			REP( i, 0, N )
			{
				REP( j, 0, i )
				{
					ok &= indices[j] < indices[i] || size[ indices[i] ] + size[ indices[j] ] <= maxSizeSum;
				}
			}
			res += ok;
		}
		while ( next_permutation( ALL( indices ) ) );

		return res;
	}
};