SRM 574 Div1 450 PolygonTraversal

2013-03-26

14:07 |

円上に時計回りに N 個の点があって、点番号 P[0]→P[1]→...→P[M-1] と線が引いてある。
P[M-1] から使ってない点をすべて使って P[0] に戻りたい。その際、新しく引く線はかならずどれかの線と交差しないといけない。
そんな線の引き方は何通りあるか。
4≦N≦18, 2≦M≦N-1, 1≦P[i]≦N, P is distinct

ほげ〜

2**18 通り何かしらやるのだろう
使った頂点を状態とすると 2**18 になる
dp[使用済みノード集合] ... その状態での組み合わせ数？
交差してるか決めるには、とりあえず引こうとする線の始点と終点がないといけない
dp[最後に使ったノード][使用済みノード集合] ... その状態での組み合わせ数　　としてみる

交差は分からないけどなんとなく線の両側にノードが１コ以上ずつあればいい気がする

初期状態は P の線分を全部引いた状態が 1 通りあるので dp[Pの最後][Pに含まれるノード集合] = 1
更新式は、cur, next を決めて cur が使われてて next が使われてなくて交差するなら dp[next][bit|1<<next] += dp[cur][bit]

書いたけど合わない

（あとで）

Petr さんのを観察
骨格とか交差判定は良かったみたいだが、なんかそもそも更新の方向とか計算順序が逆。
あと全ノードを使ったあとに最初のノードに戻ってくる所の特殊処理が抜けてた。

Fastest の _Romka_ さんは 9 分 11 秒だそうです。ほげ〜〜〜

↓あとで(accepted in practice room)

// maximum 476ms in arena
int cross(int N, int bit, int cur, int nxt) {
	// cur, nxt を結んだ線の両サイドに少なくとも１コ以上使用済みノードがあれば交差する
	int side0 = 0;
	for(int i=(cur+1)%N; i!=nxt; i=(i+1)%N) if(bit & 1<<i) side0=1;
	int side1 = 0;
	for(int i=(nxt+1)%N; i!=cur; i=(i+1)%N) if(bit & 1<<i) side1=1;
	return side0 && side1;
}

class PolygonTraversal {
	public:
	long long count(int N, vector <int> P) {
		int M = P.size();
		REP(i, M) P[i]--;
		
		VVI dp(N, VI(1<<N));
		int init_bit = 0;
		FOR(e, P) init_bit |= 1<<*e;
		dp[P.back()][init_bit] = 1;
		
		REP(bit, 1<<N) {
			REP(cur, N) {
				if((bit & 1<<cur)==0) continue;
				if(dp[cur][bit]==0) continue;
				REP(nxt, N) {
					if(bit & 1<<nxt) continue;
					int ok = cross(N, bit, cur, nxt);
					if(ok) dp[nxt][bit|1<<nxt] += dp[cur][bit];
				}
			}
		}
		ll ans = 0;
		int bit = (1<<N)-1;
		REP(cur, N) {
			int nxt = P[0];
			int ok = cross(N, bit, cur, nxt);
			if(ok) ans += dp[cur][bit];
		}
		return ans;
	}
};

ちなみに　交差判定にビット演算を使った版も。時間はそんなに違わないような。

// maximum 117ms in arena
int crossB(int N, int bit, int cur, int nxt) {
	int a = min(cur, nxt);
	int b = max(cur, nxt);
	int mask0 = ((1<<b)-1) & ~((1<<(a+1))-1);   // 0 0 0 b 1 1 1 a 0 0 0
	int mask1 = ~((1<<(b+1))-1) |  ((1<<a)-1);  // 1 1 1 b 0 0 0 a 1 1 1
	
	int ret = bit & mask0 && bit & mask1;
	return ret;
}