4位のnikaさんのコードを読んでみる。
https://community.topcoder.com/longcontest/?module=ViewProblemSolution&pm=10729&rd=16702&cr=20315020&subnum=18
Forumのご本人のポストによると、次の3つのフェーズに分かれているらしい。
パート1(30%)
rootが分割されるまでカットを足していく。足すカットは、いくつかの候補から、(コスト)/(新たに分割されるrootの数)がベストのものを選ぶ。
パート2(60%)
カットの増減を繰り返してスコアを改善する。カットをランダムに選んで取り除き、そしてrootがすべて分割されてないときは、パート1と同じ手段でカットを足す。スコアが改善するようならこれを使い、しないなら元に戻す。
パート3(10%)
カット位置を1ポイントずつ動かして改善をはかる。
カットを足す方法について。なるべく良い候補にするため①始点と終点をランダムに選ぶ②垂直・水平のどちらかを選ぶ③どちらかの方向の全パターンを見て、最も良いものを選ぶ、という処理を行っている。ここでコストの再計算を避けるため、スキャンラインテクニック(Scan Line Technique)というのを使っているらしい。
情報の持ち方
int m, n; // m: Plantの数、n: Endpointの数 int x[N], y[N] // x[], y[]: Endpointの座標 int parent[N]; // EndpointのPlant番号 int p[N]; // Endpointの親Endpoint番号 double edgeLength[N]; // Endpointとその親の距離 double edgeSum; // 距離の総合計 vector<int> plants[M]; // Plantに属するEndpoint vector<int> hull[M]; // Plantに属するEndpoint。外殻のみ。左下から時計回り // CutがPlantを切断するかどうかを判断するのに使う vector<int> ret; int separated[M][M]; // plantが分離されてるかどうか(いくつのカットで分離されたか) int phase; int minX[N], maxX[N]; int dead[N]; // 根が死んでいるかどうか int wouldKill[N]; int alive[N]; // 生きている根 int aliven; // 生きている音根の数 int wk; double aliveLength[N]; // 生きている根の長さ multiset<double> cutRatio[N]; // 根が切られた位置。multiset: sorted、重複OKのset typedef pair<Line, Mask> Cut; // Lineは始点xy・終点xyなどをもつ構造体 // Maskは120ビットのマスク。ビット位置ごとのXor、Orなどができる double bestSaved = -1e100; // 切り取られた根の長さ合計ベスト vector<Cut> bestSolution; double savedEdgeSum; vector<Cut> solution; // グループ: カットされてないPlantの集合 int group_n; // グループの総数 int group_cnt[M] // あるグループ番号に属するPlant数 int group[M][M]; // group[i][j]: グループ番号iに属する、j番目のPlant番号 int group_vis[M]; // ワーク
やはりClassを作るのは避けて、なるべく単純な配列等で保持している。
マスクは該当Cutが分割しているPlantの情報。Cut線からLeft集合とRight集合に分けている(ビット位置で保持)。この方法は汎用性がありそうだ。
メインルーチン
vector<int> makeCuts(int NP, vector<int> points, vector<int> roots) { Init(); m = NP; n = SZ(points) / 2; for (int i = 0; i < n; i++) { x[i] = points[2 * i]; y[i] = points[2 * i + 1]; } edgeSum = 0; for (int i = 0; i < n; i++) { if (i < m) { parent[i] = i; p[i] = -1; } else { p[i] = roots[2 * (i - m)]; parent[i] = parent[p[i]]; edgeLength[i] = hypot(1.0*x[i] - x[p[i]], 1.0*y[i] - y[p[i]]); edgeSum += edgeLength[i]; } plants[parent[i]].push_back(i); } F0(i, m) BuildHull(i); CL(0, separated); F0(i, m) separated[i][i] = 1; group_n = 1; group_cnt[0] = m; F0(i, m) group[0][i] = i; FirstPhase(); SecondPhase(); FinalPhase(); if (savedEdgeSum > bestSaved + 1e-4) { UpdateBestSolution(); } for (auto v : bestSolution) { v.first.AddToSolution(); } fprintf(stderr, "My score: %.2lf\n", bestSaved); c_o[9] = SZ(ret) / 4; Report(); return ret; }
BuildHullまでで必要な情報を取得したあと、フェーズ1~3を実行している。BuildHullのコードは今後の参考になりそうだった。
BuildHull
bool cmp_start(int a, int b) { int t = cw(startpoint, a, b); if (t != 0) return t>0; t = x[a] - x[b]; if (t != 0) return t<0; t = y[a] - y[b]; if (t != 0) return t<0; return 0; } int h[N+5]; void BuildHull(int k) { startpoint = plants[k][0]; for (int i : plants[k]) { if (x[i] < x[startpoint] || (x[i] == x[startpoint] && y[i] < y[startpoint])) startpoint = i; } // a[] はこのPlantに属するすべてのEndpoint // 左下のStartpointから、CWでソートされている vector<int> a; a.push_back(startpoint); for (int i : plants[k]) { // C++11の構文らしい if (x[i] != x[startpoint] || y[i] != y[startpoint]) a.push_back(i); } sort(a.begin() + 1, a.end(), cmp_start); // 外殻だけを取り出す vector<int>& h = hull[k]; h.push_back(a[0]); h.push_back(a[1]); int hn = 2; for (int i = 2; i < SZ(a); i++) { while (hn >= 2 && cw(h[hn - 2], h[hn - 1], a[i]) <= 0) { hn--; h.pop_back(); } h.push_back(a[i]); hn++; } h.push_back(a[0]); }
(1)左下を起点に、時計回りにソート(2)そのうち、cwが負になる点を除く。
パート1
void FirstPhase() { phase = 1; savedEdgeSum = edgeSum; while (1) { // カットされてないPlantの集合がなくなったら、調整してから終了 if (!group_n) { int sg = 1; while (sg) { sg = 0; // 該当カット単独でのPlant分割がなかったら、無駄なので削除 F0(i,SZ(solution)) if (!BreaksSolution(solution[i].second)) { ApplyMaskToSeparated(solution[i].second, -1); savedEdgeSum += ApplyLine(solution[i].first, -1, true);; // Lineを削除 solution.erase(solution.begin() + i); sg = 1; break; } } if (bestSaved < savedEdgeSum) { bestSaved = savedEdgeSum; bestSolution = solution; } return; } double t = Elapsed(); bestRatioFound = 1e10; int it = 0; aliven = 0; for (int i = m; i < n; i++) if (!dead[i]) { alive[aliven++] = i; aliveLength[i] = cutRatio[i].empty() ? edgeLength[i] : *cutRatio[i].begin(); } // ある程度の時間、繰り返してベストなカット(+マスク)を得る int needs = 0; F0(i,group_n) needs += group_cnt[i] - 1; while (1) { it++; FindBestStraightCut(); // まあまあ良いCutを探し出して足す // ランダムな始点終点を選び、その後xかy方向に1ビットずつスライドさせて // ベストを選んだもの c_o[8]++; double portion = (Elapsed() - t) / (LTL - t); if (pow(portion, 1) * needs >= 1 || t >= LTL) break; // なぜこの条件が良く分からない・・・ } solution.push_back(bestCutFound); savedEdgeSum += ApplyLine(bestCutFound.first); // Lineを足す ApplyMaskToSeparated(bestCutFound.second); // separated[][], group_n, // group_vis[], group[][], group_cnt[] を更新 } }
すべてのPlantが切り離されるようCutを作成。
FindBestStraightCut()だけである程度良いCutになっているはずだが、さらにしつこく時間でループしてベストな候補を選んでいる。
BreakSolution()の実装はこれ。該当カットがソロで分割してるPlantがあればTrueを返している。
bool BreaksSolution(const Mask& mask) { vector<int> leftSide, rightSide; F0(i, m) if (mask.setAt(i)) leftSide.push_back(i); else rightSide.push_back(i); for (int ls : leftSide) for (int rs : rightSide) if (separated[ls][rs] == 1) return true; return false; }
パート2
void SecondPhase() { phase = 2; for (int i = m; i < n; i++) aliveLength[i] = edgeLength[i]; // このzの使いかたがよく分からない int z = min(n, 2000); z = max(z, n / 10); while (Elapsed() < GTL) { int sg = 1; // 無駄Cutを削除 while (sg) { sg = 0; for (int i = SZ(solution) - 1; i >= 0; i--) if (!BreaksSolution(solution[i].second)) { ApplyMaskToSeparated(solution[i].second, -1); bool needDelete = true; F0(j,SZ(bestSolution)) if (bestSolution[j].first == solution[i].first) { needDelete = false; break; } savedEdgeSum += ApplyLine(solution[i].first, -1, needDelete); solution.erase(solution.begin() + i); sg = 1; break; } } // カットされてないPlantがあるのはいいが、スコア悪化は嫌う if (savedEdgeSum < bestSaved + eps && group_n) { RevertSolution(); } if (!group_n) { // 全Plantがカット済で、かつベストスコア更新 if (savedEdgeSum > bestSaved + eps) { UpdateBestSolution(); // 全Plantはカット済だが、スコア悪化 } else if (savedEdgeSum < bestSaved - eps) { RevertSolution(); } // 適当に1~4本、Cutを削除 if (SZ(solution) > 0) { int k = my.nextInt(SZ(solution)); auto v = solution[k]; savedEdgeSum += ApplyLine(v.first, -1); ApplyMaskToSeparated(v.second, -1); Mask mask = v.second; solution.erase(solution.begin() + k); int sg = my.nextInt(15); if (sg == 14) sg = 3; else if (sg >= 12) sg = 2; else if (sg >= 8) sg = 1; else sg = 0; if (sg) { F0(k,SZ(solution)) { int cnt = 0; F0(i,m) if (mask.setAt(i) != solution[k].second.setAt(i)) cnt++; if (cnt <= sg || cnt >= m - sg) { auto v = solution[k]; savedEdgeSum += ApplyLine(v.first, -1); ApplyMaskToSeparated(v.second, -1); solution.erase(solution.begin() + k); break; } } } } } bestRatioFound = 1e10; int it = 0; aliven = 0; for (int i = m; i < z; i++) if (!dead[i] && cutRatio[i].empty()) { alive[aliven++] = i; } // パート1と同じようにCutを足していく int z = 8 + my.nextInt(16); while (1) { it++; FindBestStraightCut(); c_o[7]++; if ((it >= z) || Elapsed() > GTL) break; } if (bestRatioFound > 1e9) { RevertSolution(); continue; } solution.push_back(bestCutFound); savedEdgeSum += ApplyLine(bestCutFound.first); ApplyMaskToSeparated(bestCutFound.second); } }
うまくパート1とコードを共用している。
パート3は影響が小さいので省略。
FindBestStraightCut()とApplyLine()が重要なところだが、難しくて理解できなかった・・・。