mayoko’s diary

プロコンとかいろいろ。

SRM 566 div1 easy: PenguinSledding

問題

TopCoder Statistics - Problem Statement

n 頂点の無向グラフが与えられる。このグラフから辺をいくつか選ぶとき, 以下の条件を満たす選び方の場合の数を求めよ。

条件: 選んだ辺上の頂点を 2 次元平面上でどのように配置しても(ただし 3 頂点が同一直線上に来るようにはしない), 選んだ辺同士で交差しない。

解法

あり得る状況としては,

  • 単なる辺
  • ある頂点にのみたくさん辺がついた感じ(star graph とか言われる)
  • 三角形

の三通りがあります(多分三角形が一番気付きにくい)。

star graph に関しては, ある頂点 v に接続する頂点の数を num として, 2^num - 1 - num を計算すれば良いです。

class PenguinSledding {
public:
    long long countDesigns(int n, vector <int> checkpoint1, vector <int> checkpoint2) {
        ll cnt = 0;
        int m = checkpoint2.size();
        for (int i = 1; i <= n; i++) {
            ll S = 0;
            for (int j = 0; j < m; j++) {
                if (checkpoint2[j] == i || checkpoint1[j] == i) {
                    int v = (checkpoint1[j] == i ? checkpoint2[j] : checkpoint1[j]);
                    S |= 1ll<<v;
                }
            }
            int num = __builtin_popcountll(S);
            // 次数が 2 以上になるやつ
            if (num >= 2) {
                cnt += 1ll<<num;
                cnt -= 1 + num;
            }
        }
        ll ret = cnt+m+1;
        for (int i = 0; i < m; i++) for (int j = i+1; j < m; j++) for (int k = j+1; k < m; k++) {
            set<int> S;
            S.insert(checkpoint1[i]); S.insert(checkpoint2[i]);
            S.insert(checkpoint1[j]); S.insert(checkpoint2[j]);
            S.insert(checkpoint1[k]); S.insert(checkpoint2[k]);
            if (S.size() == 3) ret++;
        }
        return ret;
    }
};