問題概要
サイズ の順列について考える。順列 について、有効な 2 つのインデックス について、 である
ものの個数を の sortedness と呼ぶ。
サイズ の順列からいくつかの要素を消去した列である 及び、正整数 が与えられる。 に於いて、要素が 0 のとき、その位置の要素は元の順列から消去されたものであることを表す。要素が消去される前の であって、sortedness が与えられた値と等しくなるものの個数を求めよ。なお、元の順列から消去された要素の個数は 5 を超えない。
解法
消去された要素が何であったかは、 を走査することで判明します。消去された要素の個数が であったとき、 個の要素を 箇所に入れる方法は 通りになります。制約より なので、この値はあまり大きくありません。従って、入れ方を全て試して、復元した の 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; } };