TopCoder SRM 627 Div1 Medium GraphInversions

珍しくあっさり解けたMedium。
http://community.topcoder.com/stat?c=problem_statement&pm=13275

問題

N頂点N辺からなるグラフがあり、各頂点には数値V[i]が与えられている。
このグラフ上で同じ点を２度通らないK個の頂点をたどるパスを考える。
そのようなパスがあれば、そのようなパス上の頂点における数値V[i]からなる数列を考えたとき、数列が昇順とならないinversionとなっている数の最小値を答えよ。

解法

N頂点N辺ということで、１つだけ閉路がある。
この場合、各頂点を始点としたパスをDFSで考える場合、各頂点はせいぜい２回（閉路をどちら周りで回るかの違いだけ）しか通らない。
よってDFSによりK頂点のパス列挙はO(N^2)である。

後はinversionカウントの定石としてBitIndexTreeを用いて、頂点をDFSする際に今いる頂点より大きな数値V[i]の数をカウントしていけばよい。
BITならV[i]の最大値MVに対しO(logMV)でカウントできるので、全体でO(N^2*logMV)で済む。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	BIT(){clear();};
	void clear() {ZERO(bit);};
	V total(int entry) {
		V s=0;
		entry++;
		while(entry>0) s+=bit[entry-1], entry -= entry & -entry;
		return s;
	}
	void update(int entry, V val) {
		entry++;
		while(entry <= (1<<ME)) bit[entry-1] += val, entry += entry & -entry;
	}
};

vector<int> E[1001];
int vis[1001];
BIT<int,11> bt;
class GraphInversions {
	public:
	int N;
	vector <int> V;
	ll dfs(int cur,int left,int num) {
		int cv=num-bt.total(V[cur]);
		int i;
		ll ret=10000000;
		if(left==1) return cv;
		vis[cur]=1;
		bt.update(V[cur],1);
		FOR(i,E[cur].size()) {
			int tar=E[cur][i];
			if(vis[tar]) continue;
			ret=min(ret,dfs(tar,left-1,num+1));
		}
		bt.update(V[cur],-1);
		vis[cur]=0;
		return ret+cv;
	}
	
	int getMinimumInversions(vector <int> A, vector <int> B, vector <int> V, int K) {
		int i,x;
		N=A.size();
		this->V=V;
		FOR(i,N) E[i].clear();
		FOR(i,N) E[A[i]].push_back(B[i]);
		FOR(i,N) E[B[i]].push_back(A[i]);
		ll ret=10000000;
		FOR(i,N) {
			ZERO(vis);
			bt.clear();
			ret=min(ret,dfs(i,K,0));
		}
		if(ret>=10000000) return -1;
		return ret;
	}

まとめ

V[i]の上限が小さすぎて最初DPかと思ってしまった。
幸いすぐBITが思いついて何とか解けた。