torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder, SRM 636, Division 2, Level 2 : SortishDiv2

問題概要

 サイズ N の順列について考える。順列 S について、有効な 2 つのインデックス i, j ( 0 \leq i < j < |S| ) について、S_i < S_j である
ものの個数を S の sortedness と呼ぶ。
 サイズ N の順列からいくつかの要素を消去した列である seq 及び、正整数 sortedness が与えられる。seq に於いて、要素が 0 のとき、その位置の要素は元の順列から消去されたものであることを表す。要素が消去される前の seq であって、sortedness が与えられた値と等しくなるものの個数を求めよ。なお、元の順列から消去された要素の個数は 5 を超えない。

解法

 消去された要素が何であったかは、seq を走査することで判明します。消去された要素の個数が m であったとき、m 個の要素を m 箇所に入れる方法は m! 通りになります。制約より m \leq 5 なので、この値はあまり大きくありません。従って、入れ方を全て試して、復元した seq の sortedness を計算することで、条件を満たすものの個数を数え上げることができます。

コード

using VI = vector<int>; using VVI = vector<VI>;
template < typename T = int > using VT = vector<T>;

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

#define PB( n ) push_back( n )

class SortishDiv2
{
public:
	int ways( int sortedness, vector <int> seq )
	{
		const int N = seq.size();

		VI nums, indices;
		{
			VT< bool > used( N );
			REP( i, 0, N )
			{
				if ( !seq[i] )
				{
					indices.PB( i );
				}
				else
				{
					used[ seq[i] - 1 ] = true;
				}
			}

			REP( i, 0, N )
			{
				if ( !used[i] )
				{
					nums.PB( i + 1 );
				}
			}
		}

		int res = 0;
		do
		{
			VI tmp = seq;
			REP( i, 0, nums.size() )
			{
				tmp[ indices[i] ] = nums[i];
			}

			int rinv = 0;
			REP( i, 0, N )
			{
				REP( j, i + 1, N )
				{
					rinv += tmp[i] < tmp[j];
				}
			}

			res += rinv == sortedness;
		}
		while ( next_permutation( ALL( nums ) ) );

		return res;
	}
};