Topcoder Open 2016 Marathon Match(Round 1)勉強メモ

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()が重要なところだが、難しくて理解できなかった・・・。