TopCoder SRM 574 Div1 Meidum PolygonTraversal

問題

正n多角形がある。
この多角形の頂点を折れ線で結んでいく。

いま、pointsで示される頂点を結んで、pointsの最後の頂点にいる。
残りまだ訪問してない頂点を、次の条件を満たすように結ぶ。

• 次の頂点への線分を描くとき、今までの折れ線に交差する。
• 最後の頂点から、pointsの一番最初の頂点への線分が、今までの折れ線に交差する

このとき、頂点の訪問の順番は何通りあるか、求めよ。

制約条件

N≦18

方針

bitDP.
dp[今までに訪問した頂点の番号][最後の頂点の番号]として、
これを更新していく。

最後の頂点から次に訪問できる頂点は、まず隣り合うところはダメ。
で、今までに訪問した頂点を一つでも超えたなら、交差をする。
逆に今までに訪問した頂点を超えないなら、交差しない。

なので、超えたところだけDPの更新をする。
それだけ。だけど本番中バグって時間かかってしまった。

ソースコード

const int mod = (int)1e9 + 7; 
int n; 
ll dp[1 << 18][18]; 

class PolygonTraversal { 
  public: 
  long long count(int N, vector <int> points) { 
    memset(dp, 0, sizeof(dp)); 
    int bit = 0; 
    n = N; 
     
    rep(i, points.size()) bit |= 1 << (points[i] - 1); 
    dp[bit][points.back() - 1] = 1; 
     
    rep(l, n - points.size()){ 
       
      rep(i, 1 << n) if(__builtin_popcount(i) == l + points.size()) rep(p, n) if(dp[i][p]){ 
         
        int j = p + 1, k = p + n - 1; 
        for(; j < k && !(i & 1 << j % n); j++); 
        for(; j < k && !(i & 1 << k % n); k--); 
        
        for(; j < k; j++) if(!(i & 1 << j % n)){ 
          dp[i | 1 << j % n][j % n] += dp[i][p]; 
        } 
      } 
    } 
     
    ll ans = 0; 
    rep(i, n) if(i != (points[0] - 1 + 1) % n && i != (points[0] - 1 + n - 1) % n){ 
      ans = ans + dp[(1 << n) - 1][i]; 
    } 
    return ans; 
  } 
};