問題概要
左側、右側それぞれに 個の頂点があり、その間に合計
本の辺が存在する二部グラフが与えられる。右側の頂点にはそれぞれ正整数
が書かれている。
左側の頂点の部分集合 について、
を「右側の頂点のうち
の要素のいずれかと辺を結んでいるものについて
を合計した値」と定義する。
空でない全ての に対する
の最大公約数を求めよ。
制約
※マルチテストケースですが、記載省略します
- 辺は全て左側の頂点と右側の頂点の間に存在し、多重辺はない
解法
まず右側の頂点それぞれについて、「どの左側の頂点と隣接しているか」を隣接リストなどの形式で求めます。これが集合として等しい右側の頂点たちは、 をどのように選んでも
に算入されるかされないかの扱いが同じになるので、
の和を取ってまとめてしまって良いです。
そして実は、このように右側の頂点を隣接頂点集合で分類して の和を取り、孤立している(隣接頂点集合が空である)もの以外全てのGCDを取ると、それが答えになります。びっくりですね。証明しましょう。
証明
GCDに関する性質として、 であること、またこれは3要素以上のGCDを考える時にも適用できることを使っていきます。
説明を簡単にするため とし、左側の頂点の集合を
桁のビット列で表現します。右側の頂点を隣接頂点集合で分類して和を取り、ビット列
に分類される右側の頂点について
の和を取ったものを
と書くことにします。
これから左側の集合 として取りうるものを1つずつ考え、各時点までに登場した
のGCDの値を
として順次計算していきます。アイデアとしては、まず最大の
を考え、そこからちょっとずつ小さい
を順番に見ていきます。
まず として全ての左側頂点(ビット列で
)を考えると、これに対する
は
と計算できます。孤立点以外の全ての右側頂点が算入対象です。この値を と書くことにすると、この時点で
です。
ここで というものを考えると、
から「頂点
にしか隣接していない右側頂点」のぶんが除かれるので、
です。ここで のGCDを考えると、
となって、 が単独で出てきます。このように左側頂点を1つだけ外した集合それぞれについて同様のことを考えると、
のGCDは
と計算できます。
次は左側頂点を2つ外した集合、例えば を考えるとこれは
となります。これを の
の中に入れると、既に
が存在しているので、同様の計算で
になります。これを繰り返すと、空でないビット列 に対する
の値が全て登場し、
はそれらの和なので最後に取り除いても問題ありません。
これは が一般の正整数の場合でも同様に成り立つので、証明が完了します。
ACコード、実装、計算量
Submission #72644787 - Codeforces
全ての隣接リストをソートした状態にすることで、集合として等しいものは列としても等しくなります。そしてこのコードではこれをそのまま map<vector<int>, int64_t>
のキーに突っ込んでいます。計算量的に危険な感じがしますが、大丈夫です。
この map
の要素数は高々 であり、長さ
の
vector<int>
をキーとするときの操作計算量は1回のキー比較が になるので
です。全ての隣接リストの長さ合計が
であることから、このソート&集計操作の計算量は全体で
と評価できます。