brilliant

B: BRILLIANT STARS
原案・解説：保坂
問題概要
• 無向グラフの最大独立集合のサイズとそれが何通りある
かを求める
• グラフの制約として，辺 AB, BC, CD が存在するならば
辺 AC, BD の少なくとも一方は存在する
• 頂点数 N <= 100,000
• 辺数 M <= 200,000
サンプルを眺める (1)
サンプルを眺める (2)
サンプルを眺める (3)
考察
• 連結成分ごとに独立に考えてよい
• 次数が高い頂点を選ぶと独立集合のサイズが大きくならな
い？
• 次数最大の頂点は実は連結成分内のすべての頂点と繋がって
いるのでは？？
• その場合はその頂点を使うのは無駄
• 頂点を 1 つ取り除いたグラフに対して再帰的に解けそう
• 誘導部分グラフは同じ制約を満たす
• サイズ n のクリークになれば，最大サイズ 1 で n 通り
考察
• N(u) := { 頂点 u の隣接点 }
• N[u] := { u } ∪ N(u)
• 問題の条件は「各辺 uv に対し，N[u] ⊂ N[v] あるいは
N[u] ⊃ N[v] が成り立つ」(★) と同値
• 証明： (★) でないとすると，a ∈ N[u], a ∉ N[v], b ∈ N[v], b ∉
N[u] なる頂点 a, b が存在するが，4 点 a, u, v, b は条件に反す
る．逆も同様．
• N[u] ⊂ N[v] であるか N[u] ⊃ N[v] であるかは，次数を
比較するだけで求まる
考察
• グラフの構造
• 有向森の推移閉包
考察
• グラフの構造
• 有向森の推移閉包
解法
• 最大独立集合のサイズを求める
• 各辺に対し，次数が大きいほうは使わない
• 次数が同じときは，番号が大きいほうは使わない
• 残った頂点をすべて使える
• 何通りか求める
• 使う頂点に対して，次数が同じ頂点たちは平等 (最終的にクリー
クとして残る頂点たち) なのでその個数を数える
• すべての連結成分について積をとる
• 辺ごとに次数を比較するのみなので O(N + M)
ジャッジ解法
for (u = 0; u < N; ++u) { deg[u] = 0; del[u] = 0; sz[u] = 1; }
for (i = 0; i < M; ++i) { u = X[i]; v = Y[i]; ++deg[u]; ++deg[v]; }
for (i = 0; i < M; ++i) {
u = X[i]; v = Y[i];
if (deg[u] < deg[v] || deg[u] == deg[v] && u < v) del[v] = 1;
else del[u] = 1;
if (deg[u] == deg[v]) { ++sz[u]; ++sz[v]; }
}
int ansSum = 0; long long ansProd = 1;
for (u = 0; u < N; ++u) if (!del[u]) {
++ansSum; ansProd = ansProd * sz[u] % 1000000009;
}
別解
• 「次数最大の頂点を取り除く」を繰り返すことをそのま
ま実装する
• 次数のみに着目して Segment Tree を用いる
• O((N + M) log N)
• グラフを再帰的に作って解く
• O((N + M) √M)
• (木の深さ)2 の辺が必要なため
• 適切に実装すれば通るかも
結果
•
•
•
•
•
正解 / 提出： 2 / 9
提出チーム： 2
正解チーム： 2
最初の提出： STAFF (03:25)
最初の正解： STAFF (03:35)

Download Report