TopCoder SRM 592, Division 2, Level 2 : LittleElephantAndPermutationDiv2

概要

サイズ N の順列とは、1 〜 N の整数がちょうど一つずつ含まれる列と定める。
サイズ N の二つの順列 A, B について、magic( A, B ) の値を次のように定める。
　

二つの整数 N ( N <= 10 ), K が与えられる。
サイズ N の二つの順列であって、K <= magic( A, B )　を満たす組の数を求めよ。

解法

A[ i ] から B[ i ] へのマッピングのみが重要なので、A の並びは固定して考えることができます。
B の順列は N が小さいので全通り試すことができるので、それぞれの順列について magic の値を計算し、条件を満たすものを数え上げればよいです。
最後に、A の順列の個数である N! を乗じることで答えが得られます。

コード

typedef long long LL;
typedef vector<int> VI;

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

class LittleElephantAndPermutationDiv2
{
public:
	long long getNumber( int N, int K )
	{
		VI ary( N );
		iota( ALL( ary ), 1 );
		
		LL res = 0;
		do
		{
			int sum = 0;
			REP( i, 0, N )
			{
				sum += max( i + 1, ary[i] );
			}
			res += K <= sum;
		}
		while ( next_permutation( ALL( ary ) ) );

		REP( i, 1, N + 1 )
		{
			res *= i;
		}

		return res;
	}
};