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; } };