TopCoder SRM 574 Div1 Medium: PolygonTraversal

問題

TopCoder Statistics - Problem Statement

解法

bitDP。intersectするかどうかはfromとtoの間（内回りと外回り）にある点について訪問済みかどうか考えるだけで良い。

コード

import java.util.Arrays;

public class PolygonTraversal {
    private long[][] dp;
    private int N;

    public long count(int N, int[] points) {
	this.N = N;
	dp = new long[N][1 << N];
	int bit = 0;
	for (int i = 0; i < points.length; i++) {
	    points[i]--;
	    bit |= 1 << (points[i]);
	}

	for (long[] a : dp) {
	    Arrays.fill(a, -1);
	}

	return dpdp(points[points.length - 1], points[0], bit);
    }

    private long dpdp(int cur, int first, int mask) {
	if (dp[cur][mask] != -1) {
	    return dp[cur][mask];
	}

	dp[cur][mask] = 0;

	// 最後にfirstに帰るときに交差するかどうか
	if (mask == (1 << N) - 1) {
	    if (intersect(cur, first, mask)) {
		dp[cur][mask] = 1;
	    }
	}

	for (int next = 0; next < N; next++) {
	    if ((mask >> next & 1) != 0 || !intersect(cur, next, mask)) {
		continue;
	    }
	    int nextmask = mask | (1 << next);
	    dp[cur][mask] += dpdp(next, first, nextmask);
	}
	return dp[cur][mask];
    }

    private boolean intersect(int from, int to, int mask) {
	// swap
	if (from > to) {
	    int temp = from;
	    from = to;
	    to = temp;
	}

	// to>from
	boolean inner = false;
	boolean outer = false;
	for (int v = 0; v < N; v++) {
	    // visitedじゃなければスルー
	    if ((mask >> v & 1) == 0) {
		continue;
	    }

	    /*
	     * fromとtoの間（内回りと外回り）にそれぞれvisitedの点があれば、 from-toは必ずどこかで交差する
	     */
	    if (v < from || v > to) {
		outer = true;
	    } else if (from < v && v < to) {
		inner = true;
	    }
	}
	return outer && inner;
    }
}