2018-06-26

CS Academy 081 DIV2 E - Fold Polygon

最小全域木グラフ密グラフ解空間:O(N!)通りの選択肢復元計算幾何条件の言い換え操作 CSAcademy 最小コスト操作:2つのものを1つにマージ全域木を考えるマルチテストケース問題多角形そのまま覚えたいシンプル設定の中堅以上の典型問題

$O(E \log{V})$ の Kruskal 法ではダメで、 $O(V^{2})$ な Prim 法なら OK という稀有なパターンの問題。Dijkstra 法でも

priority_queue を使ったやつは $O(E\log{V})$
愚直なやつは $O(V^{2})$

と二種類の実装があって前者の方が速いと言及されるケースも多いけど、密グラフ ( $E = O(V^{2})$ なグラフ) では後者の方が速い。Prim 法でも似た事情が成り立っている。

CS Academy 081 E - Fold Polygon

問題概要

頂点数 $N$ の凸多角形が与えられる。
この多角形において、「隣接する二頂点を選択し、その二頂点間の距離だけのコストを消費して、片方の頂点を消す」という操作を、残り 1 頂点になるまで繰り返す。

最小コストを求めよ。

制約

$1 \le T \le 5$ (テストケース数)
$2 \le N \le 2000$

解法

今考えたら、 $N \le 2000$ の密グラフに対する MST (最小全域木) を最大 5 回やらせるとか、Kruskal 法を TLE させる気満々な問題であった。

問題の操作が不思議な感じなので、何かに対応しているのではないかと考えてみると、「交差のない全域木」に対応していることがわかる:

操作において選択した二頂点を結ぶラインを残しておくと、それらは自然に元のグラフにおける「交差のない全域木」になっている (こっちは自明)
元のグラフにおける「交差のない全域木」を決めると、全域木の辺のうちの 1 つは凸多角形の辺でなければならず、しかもその両端点のうちの 1 つが全域木の葉になっていることもわかる。その葉を消す操作を行うとやはり「1 頂点少ないバージョンの凸多角形と交差のない全域木」が残るので、再帰的に葉を消して行くことができる。こうして「交差のない全域木」から「問題の操作」への対応付けができた。

というわけで「交差のない最小全域木」を求めればいいのだが、単純に通常の最小全域木を求めればよい。最小全域木の辺がもし交差していたら、それをほどいてより小さなコストの全域木を作ることができる。したがって通常の最小全域木を求めればそれは交差がない。

というわけで単純に MST を求めればいいのだが、Kruskal 法では $O(TN^{2}\log{N})$ かかって TLE する。愚直な方の Prim 法で $O(TN^{2})$ で解く。

最後の経路復元がちょっとめんどい。。。
まさに上に書いた「交差のない全域木のうち凸多角形の一辺になっている辺を見つけて、そのうちの葉を消す」を繰り返す。。。

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

const double INF = 1LL<<50;

vector<long double> x, y;
long double calc(int i, int j) {
  return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
}

int main() {
  int NUM_CASES; cin >> NUM_CASES;
  for (int CASE = 0; CASE < NUM_CASES; ++CASE) {
    int N; cin >> N;
    x.resize(N), y.resize(N);
    for (int i = 0; i < N; ++i) cin >> x[i] >> y[i];

    // naive Prim 法 O(V^2)
    long double res = 0.0; // MST の最小コスト
    vector<vector<bool> > mst(N, vector<bool>(N, false));
    vector<int> parent(N, -1); // 復元用
    vector<bool> seen(N, false);
    vector<long double> cost(N, INF); // 各頂点についての、既に MST に入っている頂点との距離の最小値
    cost[0] = 0; // 頂点 0 が最初に MST に入るようにする
    
    for (int iter = 0; iter < N; ++iter) {
      // そのノードを付け加えるコストが最小のやつを探す
      long double mincost = INF;
      int v = -1;
      for (int i = 0; i < N; ++i) {
        if (seen[i]) continue;
        if (cost[i] < mincost) mincost = cost[i], v = i;
      }

      // MST に枝追加
      seen[v] = true;
      res += mincost;
      if (parent[v] != -1) mst[v][parent[v]] = mst[parent[v]][v] = true;

      // cost, parent の更新 (通常の Prim ではここは priority_queue でよしなにやる)
      for (int i = 0; i < N; ++i) {
        if (seen[i]) continue;
        long double tmpcost = calc(i, v);
        if (tmpcost < cost[i]) cost[i] = tmpcost, parent[i] = v;
      }
    }
    
    // 復元
    vector<int> next(N), prev(N), deg(N, 0); // 操作を行った各時点での多角形状態、次数
    for (int i = 0; i < N; ++i) {
      next[i] = (i+1)%N;
      prev[i] = (i-1+N)%N;
      seen[i] = false;
      for (int j = 0; j < N; ++j) if (mst[i][j]) ++deg[i];
    }
    for (int iter = 0; iter < N; ++iter) {
      // 辺に密着したリーフを探す
      for (int v = 0; v < N; ++v) {
        if (seen[v]) continue;
        if (deg[v] != 1) continue;
        int nv = -1;
        if (mst[v][next[v]]) nv = next[v];
        else if (mst[v][prev[v]]) nv = prev[v];
        if (nv == -1) continue;

        cout << v+1 << " " << nv+1 << endl;

        seen[v] = true;
        --deg[nv];
        next[prev[v]] = next[v];
        prev[next[v]] = prev[v];
      }
    }
  }
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

CS Academy 081 DIV2 E - Fold Polygon

問題概要

制約

解法