最大 22 頂点のグラフの彩色数を求める問題

問題概要

$N$ 本の折れ線が与えられる。折れ線に対応した $N$ 頂点のグラフを考える。対応する折れ線同士が交差するところに辺を張る。

このグラフの彩色数を求めよ。

制約

$1 \le N \le 22$

解法

前半の幾何は虚無。実質的にグラフが与えられて彩色数を求める問題。

以後、「どの 2 点にも辺が貼られていない頂点集合」を独立集合と呼ぶこtにする。とりあえず $O(3^{n})$ の bitDP は思い浮かぶ。

dp[ $S$ ] := $S$ を独立集合に分けるときの、独立集合の個数の最小値

とする。 $O(3^{n})$ を $O(n2^{n})$ とかにしたいというよくある bitDP 高速化系。こういうのは高速ゼータ変換や高速メビウス変換のイメージがあるのだが、このままだと「最適化問題」なので厳しい。そこで、この問題を思い切って数え上げ問題にしてしまう！！！

$k$ を固定して、

g[ $S$ ] := $k$ 個の独立集合 (重複があってもいい) で集合 $S$ をちょうどぴったり被覆する場合の数

として、これが正の値となるような最小の $k$ を求めればいい。ここですごく賢いことに

f[ $S$ ] = $\sum_{T \in S}$ g[ $T$ ]

とすると、これは「独立な $S$ の部分集合 $k$ 個の組の個数」を意味している。また高速ゼータ変換・高速メビウス変換の関係、あるいは純粋に包除原理から

g[ $S$ ] = $\sum_{T \in S}$ $(-1)^{|S| - |T|}$ f[ $T$ ]

が成立している。さらに

I[ $S$ ] := 独立な $S$ の部分集合の個数

とすると、

f[ $S$ ] = I[ $S$ ] ${}^{k}$

となることがわかる。I[ $S$ ] は bitDP によって求められる。 $S$ に含まれる要素 $v$ を 1 つとって

$v$ を含まない独立集合の個数: I[ $S$ - $v$ ]
$v$ を含む独立要素の個数: I[ $S$ - $N(v)$ 　]

なので、

I[ $S$ ] = I[ $S$ - $v$ ] + I[ $S$ - $N(v)$ ]

が成立する。以上から $k$ を固定したとき、

I[ $S$ ] が計算できる
f[ $S$ ] が計算できる
g[ $S$ ] が計算できる

ことから、g[ $V$ ] の値は計算できることとなった。これが正となるような最小の $k$ が答えである。なお、最後の f から g を得るところは高速メビウス変換でもよいが、知りたい値が g[ $V$ ] だけなので高速メビウス変換までする必要はなく、包除原理の定義式を素直に計算すればいい。

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

// chmax, chmin
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

// debug stream of pair, vector
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }


////////////////////////////
// 基本要素 (点, 線分)
////////////////////////////

using DD = double;
const DD INF = 1LL<<60;      // to be set appropriately
const DD EPS = 1e-10;        // to be set appropriately
const DD PI = acos(-1.0);
DD torad(int deg) {return (DD)(deg) * PI / 180;}
DD todeg(DD ang) {return ang * 180 / PI;}

/* Point */
struct Point {
    DD x, y;
    Point(DD x = 0.0, DD y = 0.0) : x(x), y(y) {}
    friend ostream& operator << (ostream &s, const Point &p) {return s << '(' << p.x << ", " << p.y << ')';}
};
inline Point operator + (const Point &p, const Point &q) {return Point(p.x + q.x, p.y + q.y);}
inline Point operator - (const Point &p, const Point &q) {return Point(p.x - q.x, p.y - q.y);}
inline Point operator * (const Point &p, DD a) {return Point(p.x * a, p.y * a);}
inline Point operator * (DD a, const Point &p) {return Point(a * p.x, a * p.y);}
inline Point operator * (const Point &p, const Point &q) {return Point(p.x * q.x - p.y * q.y, p.x * q.y + p.y * q.x);}
inline Point operator / (const Point &p, DD a) {return Point(p.x / a, p.y / a);}
inline Point conj(const Point &p) {return Point(p.x, -p.y);}
inline Point rot(const Point &p, DD ang) {return Point(cos(ang) * p.x - sin(ang) * p.y, sin(ang) * p.x + cos(ang) * p.y);}
inline Point rot90(const Point &p) {return Point(-p.y, p.x);}
inline DD cross(const Point &p, const Point &q) {return p.x * q.y - p.y * q.x;}
inline DD dot(const Point &p, const Point &q) {return p.x * q.x + p.y * q.y;}
inline DD norm(const Point &p) {return dot(p, p);}
inline DD abs(const Point &p) {return sqrt(dot(p, p));}
inline DD amp(const Point &p) {DD res = atan2(p.y, p.x); if (res < 0) res += PI*2; return res;}
inline bool eq(const Point &p, const Point &q) {return abs(p - q) < EPS;}
inline bool operator < (const Point &p, const Point &q) {return (abs(p.x - q.x) > EPS ? p.x < q.x : p.y < q.y);}
inline bool operator > (const Point &p, const Point &q) {return (abs(p.x - q.x) > EPS ? p.x > q.x : p.y > q.y);}
inline Point operator / (const Point &p, const Point &q) {return p * conj(q) / norm(q);}

/* Line */
struct Line : vector<Point> {
    Line(Point a = Point(0.0, 0.0), Point b = Point(0.0, 0.0)) {
        this->push_back(a);
        this->push_back(b);
    }
    friend ostream& operator << (ostream &s, const Line &l) {return s << '{' << l[0] << ", " << l[1] << '}';}
};


////////////////////////////
// 円や直線の交差判定, 距離
////////////////////////////

/*
 ccw を用いている
 
 P: point
 L: Line
 S: Segment
 
 distancePL は、「点」と「直線」の距離
 distancePS は、「点」と「線分」の距離
 */

int ccw_for_dis(const Point &a, const Point &b, const Point &c) {
    if (cross(b-a, c-a) > EPS) return 1;
    if (cross(b-a, c-a) < -EPS) return -1;
    if (dot(b-a, c-a) < -EPS) return 2;
    if (norm(b-a) < norm(c-a) - EPS) return -2;
    return 0;
}
Point proj(const Point &p, const Line &l) {
    DD t = dot(p - l[0], l[1] - l[0]) / norm(l[1] - l[0]);
    return l[0] + (l[1] - l[0]) * t;
}
Point refl(const Point &p, const Line &l) {
    return p + (proj(p, l) - p) * 2;
}
bool isinterPL(const Point &p, const Line &l) {
    return (abs(p - proj(p, l)) < EPS);
}
bool isinterPS(const Point &p, const Line &s) {
    return (ccw_for_dis(s[0], s[1], p) == 0);
}
bool isinterLL(const Line &l, const Line &m) {
    return (abs(cross(l[1] - l[0], m[1] - m[0])) > EPS ||
            abs(cross(l[1] - l[0], m[0] - l[0])) < EPS);
}
bool isinterSS(const Line &s, const Line &t) {
    if (eq(s[0], s[1])) return isinterPS(s[0], t);
    if (eq(t[0], t[1])) return isinterPS(t[0], s);
    return (ccw_for_dis(s[0], s[1], t[0]) * ccw_for_dis(s[0], s[1], t[1]) <= 0 &&
            ccw_for_dis(t[0], t[1], s[0]) * ccw_for_dis(t[0], t[1], s[1]) <= 0);
}
DD distancePL(const Point &p, const Line &l) {
    return abs(p - proj(p, l));
}
DD distancePS(const Point &p, const Line &s) {
    Point h = proj(p, s);
    if (isinterPS(h, s)) return abs(p - h);
    return min(abs(p - s[0]), abs(p - s[1]));
}
DD distanceLL(const Line &l, const Line &m) {
    if (isinterLL(l, m)) return 0;
    else return distancePL(m[0], l);
}
DD distanceSS(const Line &s, const Line &t) {
    if (isinterSS(s, t)) return 0;
    else return min(min(distancePS(s[0], t), distancePS(s[1], t)), min(distancePS(t[0], s), distancePS(t[1], s)));
}

// 彩色数
const int MOD = 1000000007;
long long power(long long a, long long n) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}
int chromatic_number(const vector<vector<int> > &G) {
    int n = (int)G.size();
    vector<int> neighbor(n, 0);
    for (int i = 0; i < n; ++i) {
        int S = (1<<i);
        for (int j = 0; j < n; ++j)
            if (G[i][j])
                S |= (1<<j);
        neighbor[i] = S;
    }
    
    // I[S] := #. of inndepndet subset of S
    vector<int> I(1<<n);
    I[0] = 1;
    for (int S = 1; S < (1<<n); ++S) {
        int v = __builtin_ctz(S);
        I[S] = I[S & ~(1<<v)] + I[S & ~neighbor[v]];
    }
    int low = 0, high = n;
    while (high - low > 1) {
        int mid = (low + high) >> 1;
        
        // g[S] := #. of "k independent sets" which cover S just
        // f[S] := #. of "k independent sets" which consist of subseta of S
        // then
        //   f[S] = sum_{T in S} g(T)
        //   g[S] = sum_{T in S} (-1)^(|S|-|T|)f[T]
        long long g = 0;
        for (int S = 0; S < (1<<n); ++S) {
            if ((n - __builtin_popcount(S)) & 1) g -= power(I[S], mid);
            else g += power(I[S], mid);
            g = (g % MOD + MOD) % MOD;
        }
        if (g != 0) high = mid;
        else low = mid;
    }
    return high;
}

int main() {
    int N;
    while (cin >> N, N) {
        vector<vector<int> > G(N, vector<int>(N, 0));
        vector<vector<Line> > lines(N);
        for (int i = 0; i < N; ++i) {
            int num; cin >> num;
            double x, y; cin >> x >> y;
            for (int j = 1; j < num; ++j) {
                double nx, ny; cin >> nx >> ny;
                Line l(Point(x, y), Point(nx, ny));
                lines[i].push_back(l);
                x = nx, y = ny;
            }
        }
        for (int i = 0; i < N; ++i) {
            for (int j = i + 1; j < N; ++j) {
                bool ok = false;
                for (auto li : lines[i]) {
                    for (auto lj : lines[j]) {
                        if (isinterSS(li, lj)) ok = true;
                    }
                }
                if (ok) G[i][j] = G[j][i] = true;
            }
        }
        cout << chromatic_number(G) << endl;
    }
}

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

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

AOJ 2136 Webby Subway (JAG 夏合宿 2008 day2-F)

問題概要

制約

解法