TopCoder SRM 582 Div2 Hard ColorTheCells

Div1 Mediumがまだ解けてないので先にDiv2 Hardでも。
http://community.topcoder.com/stat?c=problem_statement&pm=12581

問題

以下の条件において、１列に並んだ0～(N-1)番のNマスのセルにペンキを塗りたい。

• 初期状態で塗る人は0番のマスにいる。
• 1マス移動すると1の時間がかかる。
• 今立っているマスの隣のマスに1の時間をかけてペンキを塗ることができる。
• 各マスについて、ペンキを塗り始めてから乾くまでの時間が与えられる。乾くまではそのマスの上は歩けない。

全部のマスが塗り終わるまでの最短時間を求めよ(乾き終わるのは待たなくて良い)。

解法

N<=7とNが小さい。
よって例によって塗る順番をN!パターン全部試せばよい。
また、各マスを左と右どちらから塗るかでパターンが変わるけど、両端を除く(N-2)マスについて両側試せばよい。
計算量はO(N! * 2^N)程度だけどN<=7なので余裕。

class ColorTheCells {
	
	vector<int> D;
	int N;
	public:
	
	int dodo2(vector<int>& V, int mask) {
		int i;
		int pt[10];
		int ret=0,ret2;
		
		FOR(i,N) pt[i]=-1;
		int cur=0;
		FOR(i,N) {
			int tar=V[i] + ((mask&(1<<V[i]))?-1:1);
			
			while(cur<tar) {
				cur++;
				ret=max(ret+1,pt[cur]+1);
			}
			while(cur>tar) {
				cur--;
				ret=max(ret+1,pt[cur]+1);
			}
			
			cur=tar;
			ret++;
			pt[V[i]]=ret+D[V[i]];
		}
		return ret;
	}
	
	int dodo(vector<int>& V) {
		int mask;
		int mi=1000000000;
		FOR(mask,1<<N) {
			if(mask&1) continue;
			if((mask&(1<<(N-1)))==0) continue;
			mi=min(mi,dodo2(V,mask));
		}
		return mi;
	}
	
	int minimalTime(vector <int> dryingTime) {
		int i;
		vector<int> V;
		
		D=dryingTime;
		N=D.size();
		FOR(i,N) V.push_back(i);
		int mi=1000000000;
		do {
			mi=min(mi,dodo(V));
		} while(next_permutation(V.begin(),V.end()));
		
		return mi;
	}
};

まとめ

next_permutation便利だね。使い方に慣れなかったけど、ようやくそらで書けるようになった。
なんか最近TreeUnionDiv2といいMarblePositioningといいDiv2 Hardで全探索系多くない？
あとDiv2 hardは最近難易度が若干低下している気がする。数回前のSRMとかかなりきつかったのに、最近は自分でもすぐ解法が思いつく。