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; } };