WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM574 Div2 Hard "PolygonTraversal2"

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12478

マナ男は紙に正N角形の頂点となるようにN個の点を描いた。
彼はそれらの点に時計回りに1からNの番号を振った。

それからマナ男はいくつかの点のペアに直線を引いた。
それに使った点の番号を整数の配列pointsとし使った点の数をM個とする。
マナ男はでpoints[i] と points[i+1](0 <= i <= M-2)のそれぞれのiで、
2つの頂点を直線で結んだ。
注意:pointsの番号は互いに異なっている。

さらに、マナ男は残りの点を巡るように直線を引いていって、
最後にpoints[0]の点に戻ることにした。
言い換えれば、マナ男はpoints[M-1]の頂点からpointsに含まれていないtail[0]へと
直線を引く。それからtail[0]からpointsとtailのどちらにも含まれていない
tail[1]へと直線を引いていくことにした。
そして最後に、彼はtail[N-M-1]とpoints[0]へと直線を引いて
全ての点を巡り終えることとなる。

マナ男は線が交差する事を好むため、上記のように直線引くときに
少なくとも1つの直線と交差させる事にした。
(注意:新たに引いた直線だけでなく、pointsで引いていた直線も含む)
全ての点を巡るような直線の引き方の数を返せ。

制約

4 <= N < 13
2 <= M <= N - 1


考えた事

N < 13だと?
こいつはくせえッー!bitDPのにおいがプンプンするぜッーーーーッ!!

どうも多角形のふちを通っちゃいけないようだな(勘違い)

書き書き・・・

よし出来た!

Sample合わない・・・
・・・
・・・
・・・



やはりおれじゃあ力不足だったようだぜ!
ここは明日またあらためて出なおすとすっか!

Ekaingはクールに去るぜ

事後

xr0038さんのブログを参考にさせて頂きましたm(_ _)m
SRM 574 - どせいけいさんき

確かにbitDPでも間違ってはいない。
でもこれは全探索でも十分間に合う。

なぜかというと、
まず始めに最低でも3点使い、2本直線が引かれていなければ新たに直線は引けない。
よって残りの点は最大でも13 - 3で10本。
10!は400万程度。
それに交差判定は13 - 2で11回計算するので、
400万 * 11 = 4400万 (結果的にはいけた)

あと直線を引いた時の交差判定は
kojingharangさんのSRM 574 Div1 450 PolygonTraversal
を参考にさせて頂きましたm(_ _)m


ソースコード

const int MAX_N = 13;

bool vis[MAX_N+1]; // vis[i] 頂点iにいったか?
int ans;
int S; // 最後に巡る頂点
int N; // 頂点数

class PolygonTraversal2 {
public:

    // 次の頂点番号
    int next( int i ){
        return i == N ? 1 : i + 1;
    }

    // 前の頂点番号
    int prev( int i ){
        return i == 1 ? N : i - 1;
    }

    // from - toって交差する?
    bool isCross( int from, int to ){
        bool b1 = false;
        for( int i = next( from ); i != to; i = next( i ) ){
            if( vis[i] ) b1 = true;
        }
        bool b2 = false;
        for( int i = prev( from ); i != to; i = prev( i ) ){
            if( vis[i] ) b2 = true;
        }
        return b1 && b2;
    }

    // v - 現在いる頂点 n - 訪問した頂点数
    void dfs( int v, int n ){
        if( n == N ){
            if( v != next( S ) && v != prev( S ) ){
                ans++;
            }
            return;
        }

        // 次に向かう頂点を全探索
        for( int to = 1; to <= N; to++ ){
            if( vis[to] ) continue;
            if( !isCross( v, to ) ) continue;
            vis[to] = true;
            dfs( to, n+1 );
            vis[to] = false;
        }
    }

    int count(int n, vector <int> points){
        
        // 初期化
        N = n;
        ans = 0;
        memset( vis, false, sizeof(vis) );

        int m = points.size();
        
        // 3以下だったら作れない
        if( m < 3 ){
            return 0;
        }

        S = points[0];
        
        for( int i = 0; i < m; i++ ){
            vis[points[i]] = true;
        }
        
        dfs( points[m-1], m );

        return ans;
    }
};