kmjp's blog

競技プログラミング参加記です

TopCoder SRM 636 Div1 Hard Sortish

なかなか時間制限が厳しい問題。
http://community.topcoder.com/stat?c=problem_statement&pm=13477

問題

基本的な設定はDiv2 Hardと同じ。
Nの上限が2000である点と、不明な要素の数が最大14である点が異なる。

解法

不明な要素数をMとする。
まず、判明している要素同士の昇順性は不明な要素の埋め方に影響しないので、最初に求めておく。
この処理はO(N^2)。

次に不明な要素M個について、それらがそれぞれM個のいずれかの位置に入った場合、判明している要素との間で加算される昇順性を求めておく。
この処理はO(N*M^2)。

あとはM個の要素をどの順で不明な位置に埋めるかによって、それらM個によって昇順性がどう加算されるかを求めていきたい。
Mが小さいときはDiv2 Hard同様next_permutationで総当たりすればよい。
しかし最大ケースM=14ではTLEする。

よって半分全列挙する。
M個の要素を前半7個と後半(M-7)個でそれぞれ総当たりし、(前半7個の中の昇順性)+(前半7個と判明している要素の昇順性)+(後半(M-7)個の中の昇順性)+(後半(M-7)個と判明している要素の昇順性)+(前半7個と後半(M-7)個の間の昇順性)+(判明している要素同士の昇順性)==sortednessとなる数を求める。

このうち

  • (判明している要素同士の昇順性) は最初に求めている。
  • (前半7個と後半(M-7)個の間の昇順性) は前半7個と後半(M-7)個分けた段階で計算できる。
  • (前半7個の中の昇順性)+(前半7個と判明している要素の昇順性) は前半7個の並びを総当たりして求める。
  • (後半(M-7)個の中の昇順性)+(後半(M-7)個と判明している要素の昇順性) は後半(M-7)個の並びを総当たりして求める。

なお、「(前半7個の中の昇順性)+(前半7個と判明している要素の昇順性)」の数え上げと「(後半(M-7)個の中の昇順性)+(後半(M-7)個と判明している要素の昇順性)」の数え上げにmapを使うとギリギリTLEする。
昇順性の上限は高々(N^2)/2なので、mapでなく配列を使った方が良い。

int resid[2][5000001];
int res[2][5000001];

class Sortish {
	public:
	int mat[20][20],E;
	int cid;
	int calcsort(vector <int>& seq,int shift) {
		int x,y,s=0;
		FOR(x,seq.size()) for(y=x+1;y<seq.size();y++) s+=seq[x]<seq[y];
		FOR(x,seq.size()) s+=mat[seq[x]][x+shift];
		return s;
	}
	
	vector<int> enumall(vector<int>& V,int shift,int id) {
		int ret=0,x;
		vector<int> r;
		do {
			x=calcsort(V,shift);
			if(resid[id&1][x]!=id) {
				resid[id&1][x]=id;
				res[id&1][x]=0;
				r.push_back(x);
			}
			res[id&1][x]++;
		} while(next_permutation(V.begin(),V.end()));
		return r;
	}
	
	long long ways(int sortedness, vector <int> seq) {
		int N=seq.size(),i,j,x,y;
		int vis[2001];
		vector<int> emp,V;
		
		E=0;
		emp.clear();
		V.clear();
		ZERO(vis);
		FOR(i,N) if(seq[i]==0) emp.push_back(i), E++;
		FOR(i,N) vis[seq[i]]++;
		FOR(i,N) if(vis[i+1]==0) V.push_back(i+1);
		FOR(i,N) for(j=i+1;j<N;j++) if(seq[i] && seq[j] && seq[i]<seq[j]) sortedness--;
		
		FOR(i,E) FOR(j,E) {
			mat[i][j]=0;
			FOR(x,N) if(seq[x]) mat[i][j]+=!((x<emp[j])^(seq[x]<V[i]));
		}
		FOR(i,E) V[i]=i;
		if(sortedness>N*N) return 0;
		
		MINUS(resid);
		if(E<=7) {
			enumall(V,0,0);
			return (resid[0][sortedness]==0)?res[0][sortedness]:0;
		}
		ll ret=0;
		for(int mask=0;mask<1<<E;mask++) if(__builtin_popcount(mask)==7) {
			vector<int> V[2];
			vector<int> M[2];
			FOR(i,E) V[(mask>>i)&1].push_back(i);
			
			M[1]=enumall(V[1],0,mask*2+1);
			M[0]=enumall(V[0],7,mask*2);
			int s=0;
			FOR(x,V[1].size()) FOR(y,V[0].size()) s+=(V[1][x]<V[0][y]);
			ITR(it,M[1]) {
				x=sortedness-s-*it;
				if(x>=0 && resid[0][x]==mask*2) ret+=1LL*res[1][*it]*res[0][x];
			}
		}
		
		return ret;
		
	}
}

まとめ

半分全列挙、ということがわかれば後はトリッキーな内容はないかもな。