TopCoder SRM 636 Div2 Medium SortishDiv2

こちらはまだ簡単。
http://community.topcoder.com/stat?c=problem_statement&pm=13500

問題

1～Nのpermutationとなる数列S[i]がある。
このS[i]の昇順性とは、i＜jかつS[i]＜S[j]となる(i,j)の数である。

ここで、S[i]が与えられるが、そのうち幾つかは中身が不明である。
S[i]の不明な箇所を埋めてS[i]を1～Nのpermutationにするとき、昇順性が入力値sortednessと一致するようなS[i]の組み合わせ数を答えよ。

解法

不明な要素は最大5個のため、その5個の中身をnext_permutatioonで総当たりして昇順性を求めればよい。
昇順性の計算はO(N^2)だがN≦100のため、5!回昇順性を求めても足りる。

class SortishDiv2 {
	public:
	
	int calcsort(vector <int>& seq) {
		int x,y,s=0;
		FOR(x,seq.size()) for(y=x+1;y<seq.size();y++) s+=seq[x]<seq[y];
		return s;
	}
		
	int ways(int sortedness, vector <int> seq) {
		int i,N=seq.size();
		int vis[200];
		vector<int> emp;
		ZERO(vis);
		
		FOR(i,N) {
			if(seq[i]==0) emp.push_back(i);
			else vis[seq[i]]=1;
		}
		
		vector<int> V;
		FOR(i,N) if(vis[i+1]==0) V.push_back(i+1);
		int ret=0;
		do {
			FOR(i,V.size()) seq[emp[i]]=V[i];
			ret += calcsort(seq)==sortedness;
		} while(next_permutation(V.begin(),V.end()));
		return ret;
		
	}
};

まとめ

面倒だけどやるだけな問題。