TopCoder SRM 574 Div1 Medium PolygonTraversal、Div2 Hard PolygonTraversal2

さてDiv1 Medium。Div2 Hardと問題が同じで、Div2の方が若干計算空間が小さい。
http://community.topcoder.com/stat?c=problem_statement&pm=12477
http://community.topcoder.com/stat?c=problem_statement&pm=12478

問題

N個の点が正N角形を描くように並んでいる。
ここで、ある点から開始して隣接点を経由しないよういくつかの点を順に一筆書きで結んで行った軌跡が与えられる。
ここから、さらに残された点を１回ずつ通り、最後に一筆書きの始点に戻る組み合わせの数を答える。

なお、これから追加する辺は、過去の辺のいずれか１本以上と交差しなければならない。

解法

Div2 HardはN<=15であり、題意の通り地道に他の辺と交差できる辺を列挙していけばよい。
ただ、この処理はO(N!)程度かかるのでN=18だと間に合わない。
実際、自分も本番この手順でN=18の計算量が落とせず失敗した。

実際には、この「他の辺と交差」の条件はもっと緩めることができる。
今いる一筆書きの終点から見て、未使用の隣接点だけを通ってたどれる点は他の辺と交差せず辿りつける。
よって、未使用の隣接点で辿りつけない点を選択していけばよい。

前者の処理は、そこまでの一筆書きの軌跡を覚える必要があるため、O(N!)もかかった。
一方、後者は今までの使用状況をbitmapで管理すればよく、一筆書きの終点の位置と合わせて高々O(N*2^N)の状態に持ち込める。
よってあとはDPを使って処理すればよい。

ll dp[1<<18][20];

class PolygonTraversal {
	int N;
	public:
	
	ll dpdp(int mask, int cur) {
		int grp[20],i,j;
		
		if(mask==(1<<N)-1) {
			if(cur==1 || cur==N-1) return 0;
			return 1;
		}
		if(dp[mask][cur]>=0) return dp[mask][cur];
		
		j=0;
		FOR(i,N) {
			if(mask & (1<<i)) j++;
			grp[i]=j;
		}
		
		ll npat=0;
		FOR(i,N) {
			if(mask & (1<<i)) continue;
			if(grp[i]!=grp[cur]-1 && grp[i]!=grp[cur]) npat += dpdp(mask | (1<<i),i);
		}
		
		return dp[mask][cur]=npat;
		
	}
	
	long long count(int N_, vector <int> P) {
		int i,x,y,mask=0;
		int M=P.size();
		N=N_;
		
		//rotate;
		FOR(i,M) P[i]--;
		for(i=M-1;i>=0;i--){
			P[i]=(P[i]+N-P[0])%N;
			mask |= 1<<P[i];
		}
		
		FOR(x,20) FOR(y,1<<18) { dp[y][x]=-1;}
		
		return dpdp(mask,P[M-1]);
	}
};

まとめ

終わってみると、確かにこれは450pt程度の問題だ。
うーん、途中の状態が「軌跡すべてでなく、未使用点の状態だけで決まる」ことにもっと早く気が付けば…。